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.
- Solutions at https://github.com/kunalb/AoC2021
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
  - 3027 / 2774
- 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(<val>, {depth: <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:
- Deno typescript: https://github.com/N8Brooks/aoc_ts/tree/main/year2021
- Bluepichu: https://gist.github.com/bluepichu
Other references
- Getting Programming With Javascript Next was very helpful in picking up new JS concepts.
- MDN is as excellent as always.

— Kunal