# 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

- Solutions at https://github.com/kunalb/AoC2021
- Daily notes / reviews

- Day 1

- Day 2

- Day 3

- Day 4

- Day 5

- Day 6

- Day 7

- Day 8

- Day 9

- Day 10

- Day 11

- Day 12

- Day 13

- Day 14

- 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

- which I'm not sure I understand

- Dial's algorithm, which uses buckets instead of a priority queue

- 1327 / 2927
- Day 16

- Day 17

- 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

- Ran across betaveros's blog on AoC today, which is excellent

- 378 / 326
- 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

- 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

- 2254 / 2108
- Day 20

- 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

- Still a nice problem today with a fairly distinct part 1 & 2
- Notes from others' solutions

- 1372 / 2301
- 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.

- 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.

- 1010 / 10372
- 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.

- 334 / 5243
- 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:

- The program is a series of 14 steps on z, which reduces to:
- 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

- Brute force with a reduced search space

- 1169 / 1113
- Day 25

- Day 1
- 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)))))

- Javascript now has Iterators & Generators!
- There are also Map objects

- 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/

- using nodejs to make it readable:
`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

- number.toString(<base>) 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.

`Deno.inspect()`

is what generates`console.log`

strings;`Deno.inspect(<val>, {depth: <depth>})`

allows manually specifying how far to expand the logged values.

- All my favorite old pieces from javascript work for the most part.
- Notes on Forth

- Other peoples' code:

- Deno typescript: https://github.com/N8Brooks/aoc_ts/tree/main/year2021
- Bluepichu: https://gist.github.com/bluepichu

- Deno typescript: https://github.com/N8Brooks/aoc_ts/tree/main/year2021
- Other references

- Getting Programming With Javascript Next was very helpful in picking up new JS concepts.
- MDN is as excellent as always.

- Getting Programming With Javascript Next was very helpful in picking up new JS concepts.