Working Notes: a commonplace notebook for recording & exploring ideas.
Home. Site Map. Subscribe. More at expLog.
Advent Of Code 2021
- Trying out AoC with [[Javascript]] this year. I'd also planned to do it in [[Forth]], but that seems like it's a bit too much work.
- Daily notes / reviews
- Day 1
- 2356 / 4013
- Wasted a lot of time because Blitzen's submit isn't working correctly any more, and I haven't bothered to fix it yet.
- Day 2
- 5301 / 3850
- Double checked that submit was broken and wasted an extra minute.
- Day 3
- Day 4
- 563 / 430
- My best performance yet; getting somewhat comfortable with using Javascript. Mostly straightforward question; just needed to make sure I follow the instructions and don't make too many mistakes.
- Finally figured out how to use the Deno LSP with emacs
- Day 5
- 459 / 293
- Brute forced it quickly by storing a map representing the grid and incrementing values
- Trying to learn new pieces of javascript by cleaning up my solution.
- Day 6
- 2046 / 871
- Over thought this problem and did it with Dynamic programming instead of maintaining counters of fish.
- Day 7
- 6987 / 4539
- Greatly overthought my solution, but still submitted it within ~15 minutes or so.
- But now AoC seems to be having issues.
- Day 8
- 300 / 1090
- Reading to the end first helped me do part 1 quickly
- Expressing constraints was a little tricky, but worked out
- Javascript's sets seem unnecessarily handicapped
- Day 9
- 3435 / 1511
- Messed up a lot while writing javascript and inserting answers
- As well as < vs <=
- I really miss using Python :)
- Wrote my own javascript generator for the first time
- Day 10
- 742 / 1285
- Mostly wasted time using javascript incorrectly
- Day 11
- 1592 / 1635
- Lost a lot of time because I used a
for...in loop on an array, which gives string indexes
- Otherwise today was a modified game-of-life-like variant
- Day 12
- 2038 / 1550
- Wasted a little bit of time cloning objects incorrectly, and used a Set in the end
- Trying out profiling to see if I can make it faster
- Day 13
- 368 / 469
- Not bad, good performance across both parts
- struggled a little bit to print out values without a newline, and gave up
- wasted some more time on =Math.max.apply(, actual array)=
- Day 14
- 183 / 258
- Slowly inching towards the leaderboard, I hope I don't jinx myself
- No clever javascript today, but I was missing python a lot while counting keys, etc.
- Day 15
- 1327 / 2927
- Forgot how to do Djikstra's algorithm, and initially solved part 1 with simple dynamic programming
- ...and it worked for Part 1, but didn't for Part 2
- particularly because this can't handle loops/going backwards in a DP based solution
- implemented djikstra's without a heap (because javascript doesn't have one)
- which lead to a 3 minute solution for part 2
- Looking through reddit, 2 solutions I hadn't considered
- [[Dial's algorithm]], which uses buckets instead of a priority queue
- Repeatedly re-doing a dynamic programming-like approach till it converges
- which I'm not sure I understand
- but I'm beginning to suspect reduces to djikstra's algorithm with constant relaxation
- Wikipedia pointed me to this paper on the connection between dynamic programming & djikstra's algorithm
- Apparently this is [[Successive Approximation]]
- Solve by pulling for improvements
- or pushing improvements
- Day 16
- 1488 / 2064
- Pretty slow today, but I enjoyed myself a lot
- It was tempting to do string manipulation (.toString(2), and parseInt(...)) to avoid thinking about bits, but I persevered
- Learnt about how to use Uint8Array, BigInt for the first time
- Day 17
- 1900 / 1304
- Slow again, because I was trying hard to find a non brute force solution
- but the requirement for integer solutions finally persuaded me not to bother
- Day 18
- 378 / 326
- Not bad, this was something of a slog of tree manipulation
- I could probably do this with less code and more implicit tree manipulation
- but explicitly having a tree structure kept bugs down
- and let me do a quick in-order traversal
- Ran across betaveros's blog on AoC today, which is excellent
- Day 19
- 2254 / 2108
- Got badly stuck, because I didn't realize that axis could be completely misaligned such that x, y, z => x, z, y
- Even though this was one of the examples
- Also took a lot of effort to work with javascript's primitives, though I have a reasonably clean solution by the end
- Also wasted a lot of time with broken reduces/sorting, etc.
- Slightly embarrassed to see how small and compact others' solutions are
- Day 20
- 542 / 404
- Really simple day: just 2 catches
- it's possible for all bulbs to light up if the enhancement image is 0
- building the next image while adjusting the coordinates for the primary image
- I feel somewhat robbed by javascript because of strange array behavior that wasted 15 of the 30 minutes on the problem
- which was a really sad mistake on my part while trying to initialize a 2 dimensional array
- I did
let nextImage = new Array(4).fill(new Array(4).fill("."));
- which creates a 2-dimensional array, filled with the same array 4 times
- Day 21
- 1372 / 2301
- A little sleepy and disappointingly slow
- It took me some time to grok the rules of the game for part 1 and implement them correctly
- ... and then to realize that memoization would lead to victory for part 2
- given the values would end up repeating after a few turns
- Still a nice problem today with a fairly distinct part 1 & 2
- Notes from others' solutions
- One player treated the memoized values as "all games in progress" and kept increasing those
- Another very elegantly swapped player1/player2 values as arguments to the recursive function to show who's going first
- Day 22
- 1010 / 10372
- Looks like a range-tree/oct-tree, but I haven't implemented one in a long time.
- Didn't actually need it -- my solution was good enough, just doing unnecessary work that was trivial to fix after a good night's sleep.
- Intersected cuboids carefully to get ranges to solve.
- https://github.com/leyanlo/advent-of-code/blob/main/2021/day-22.js is an elegant solution that uses negative cuboids, and is significantly smaller than mine.
- Day 23
- 334 / 5243
- Manually solved the first one.
- Tried to manually solve the second one while writing pathfinding code to aid me at the same time.
- Working solution that takes 2 minutes
- Pretty much brute force with pruning paths and semi-clever caching.
- Looking at reddit suggests a /fast/ solution would be to treat each state as a node in a graph and do djikstra's algorithm on it by cost.
- Day 24
- 1169 / 1113
- I'm kind of impressed at how fast everyone reverse engineered everything
- Pretty proud of my constraint based solution which is pretty much O(instructions)
- The program is a series of 14 steps on z, which reduces to:
function step(p1, p2, p3) {
w = inputs.next().value;
x = z % 26 + p2;
z = Math.floor(z / p1);
if (x != w) {
z = z * 26 + w + p3;
}
// console.log({step: ++i, w, x, y, z});
}
- Expanding this a little bit leads to constraints on the inputs: 1 <= input <= 9,
- But we also want to make sure z reaches 0:
- z can only reduce when p1 != 1
- which explicitly sets up relationships on 7 values
- the constants/parameters end up giving a range on the "free" values
- setting the "free" values to their maximum & minimum possible values respectively solves the problem.
- And fairly curious about how Reddit did it:
- Brute force with a reduced search space
- Python to directly evaluate it by heavily relying on caching
- A /few/ others who derived the constraints like I did
- Using Z3 SMT Solver: https://gist.github.com/AdibSurani/c047a0f0d3d9bc294337cb58da16173e
- Day 25
- 1283 / 1009
- A nice and gentle puzzle, though with several edge cases -- all of which I felt like I managed to hit :)
- It's a relief to wrap up this year's AoC -- I learned a lot, and mostly enjoyed myself; but there's also a tinge of disappointment for not making it to the leaderboard.
- I do feel significantly more comfortable with Javascript
- And find it a little bit unhappy about the ergonomics.
- Deno makes it really convenient to run though.
- Notes on Javascript
- All my favorite old pieces from javascript work for the most part.
- [[Deno]] seems really cool and has been a pleasure to work with.
- Configuring emacs to use deno-ls (lowest priority language server)
((nil . ((lsp-disabled-clients . (jsts-ls ts-ls flow-ls)))))
- as a .dir-locals.el file in the directory of my advent of code solutions.
- Javascript now has Iterators & Generators!
- There are also Map objects
- Arrays used as keys inside a map are not treated by equality, but instead by the array object reference.
- and a strange Symbol class
- Sorting on numbers needs an explicit lambda passed in, otherwise it does it in lexical ordering =/
- Reverse is destructive and modifies the original array while returning the reversed value
for...in shouldn't be used on arrays; it will cast all keys to strings a- Triggering a profile with deno: deno run --v8-flags​=--prof js/day12.js
- using nodejs to make it readable: =node --prof-process isolate-0x5592d54298d0-11331-v8.log=
- Can also use =--preprocess= to generate a json blob, which can be passed to https://v8.github.io/tools/head/profview/
- =Object.values= to get values from an object as an array
- Immutable looks interesting, reference from bluepichu's solution
- Pre-allocate a Uint8Array for use
- BigInt is a large integer class, cannot use Math functions with it
- Suffix numbers with an =n= to mark them as Bigints
- number.toString() is super helpful in printing out binary values
- Can use =Math.min(...[array])= instead of =Math.min.apply(null, array)=
- =new Array(x)= creates an empty array with x length; which means =Array.prototype.map= becomes a no-op
- =Array.prototype.fill= is used to fill with a static value: which means filling with a complex object will simply repeat the same object multiple times.
- I keep making this mistake and should be more careful.
- =Deno.inspect()= is what generates =console.log= strings; =Deno.inspect(, {depth: })= allows manually specifying how far to expand the logged values.
- Notes on Forth
- Reading from stdin and running forth as a script seems... hard.
- Other peoples' code:
- Other references
— Kunal