My solutions for Advent of Code 2024.
This year: Learning Nim!
Code in Nim 2.2.0.
- Testing, debugging:
nim compile --run day00.nim - Timing:
nim compile -d:release -d:danger day00.nim
Libraries used:
benchy(timing):nimble install benchybigints(big integers):nimble install https://github.com/nim-lang/bigintsmanu(solving matrices):
| Day | Time (ms) |
|---|---|
| Day 1 | 0.68 |
| Day 2 | 1.98 |
| Day 3 | 2.24 |
| Day 4 | 0.27 |
| Day 5 | 22.5 |
| Day 6 | 346 |
| Day 7 | 2.87 |
| Day 8 | 0.95 |
| Day 9 | 169 |
| Day 10 | 1.66 |
| Day 11 | 0.007 |
| Day 12 | 27.4 |
| Day 13 | 0.87 |
| Day 14 | 59 |
| Day 15 | 0.58 |
| Day 16 | 78.7 |
| Day 17 | 1.5 |
| Day 18 | 12.6 |
| Day 19 | 69.8 |
| Day 20 | 138 |
| Day 21 | 0.48 |
| Day 22 | 473 |
| Day 23 | 9.8 |
| Day 24 | 0.59 |
| Day 25 | 0.43 |
Ranking for all 50 stars: 2863rd place (Almost the same as last year!)
Total runtime (for all 25 days): 1420ms
First map problem, yay! Part 1 was quick, but part 2 took me much longer because I didn't properly think it through and
jumped into coding. There's an edge case (only in part 2) if you insert a blocker 0 just at a place so a right turn
isn't possible, then the guard will have to walk back from where they came from.
Guard approaching:
..->...#
......0.
Hitting the given wall, unable to turn (or turning 90°, then right again).
.....->#
......0.
Guard going back.
.....<-#
......0.
My solution is still somewhat "brute-forcy" (on the given path from part 1, try to insert a blocker 0 at any possible
place), but as it finished within a second I let it be.
Recursion ftw! Solving part 1 was fun and quick, and I started in reverse from the beginning.
With part 2 it took me a while to realize what
"reversing" the || means. After figuring out that I misunderstood the problem statement, I was able to figure it out:
7290: 6 8 6 15
* (revert: divide by 15)
486: 6 8 6
|| (revert: remove last 6 from 486)
48: 6 8
* (revert: divide by 8)
6: 6 ✅
Defragmentation of a disk, what a fun challenge. With a simple list (Nim: sequence) of integers (representing
fileIds), I could keep track of which file was placed where.
With looping around a bit (and getting rid of off by one-errors), it was possible fairly easy to check if the length of a file would allow it to be placed somewhere else.
Again a map problem today, hooray! Reading through it, it felt familiar, maybe reminding me a bit
of 2023 Day 23.
I first thought of using recursion, but after looking at the actual input decided to use a simple queue, so to start
exploring at 0s and expanding the possible paths by processing queue items. This turned out to be a very good
preparation for part 2 which only required slight changes.
Expanding stones - part 1 was implemented quickly with just following the rules, but it became clear soon enough that this approach would not work for part 2 (even with a compiled language). After thinking it through some more I gave Memoization a try, which worked surprisingly well.
Cheat day! Today when reading the problem my mind immediately jumped to equation solving, so I used Python/SymPy, ignoring the "cheapest" condition. The first solution for each equation was already the right one, and I only found out afterwards that all "vectors" were linearly independent, so I got lucky.
Re-implemented this later in Nim with the manu package to solve it
as a linear equation system as matrix, to also have it in Nim (and speed it up a bit, from around a second to below a
millisecond).
Wow, what a great puzzle today. I was expecting a big number of seconds in Part 2, but it was really something different today. Having a puzzle thrown at you which is so unclear was unexpected in AoC and really surprised me. Seeing the Christmas tree appear in the Console (after only considering solutions with enough neighbouring robots) was really satisfying.
Part 1 was okay, but after reading part 2 I wasn't motivated at all to solve it. The problem felt really tedious, especially as it could be any amount of boxes connected which have to be checked (unlike in Sokoban, where two boxes near each other are already a blocker), like this:
move: v, pos: (3, 13), map:
####################
##[]..[]......[][]##
##[]...........[].##
##...........@[][]##
##..........[].[].##
##..##[]..[].[]...##
##...[]...[]..[]..##
##.....[]..[].[][]##
##........[]......##
####################
move: >, pos: (4, 13), map:
####################
##[]..[]......[][]##
##[]...........[].##
##............[][]##
##...........@.[].##
##..##[]..[][]....##
##...[]...[].[]...##
##.....[]..[].[][]##
##........[]..[]..##
####################
I only solved this part days later, iterating (and collecting) a stack of boxes, first to check if there's enough space, then backwards to actually move them.
Again a map problem, but a very fun one. Finding the shortest path quickly reminded me of last year and I started early with a Priority Queue, with a heapqueue implementation in Nim.
As it was still running to slowly, I started skipping paths in the queue that were on positions (with direction) that we already processed, which worked out nicely. Unfortunately this was not usable for Part 2, so I had to use another lookup. Starting with the whole path didn't work ( or make sense), but keeping the lowest score for a given position+direction was the key. (If a path leading up to the position had a higher score, it could not be a solution.)
I started with an implementation in Nim but switched to Python, because I didn't want to deal with bigints.
After fixing a round/floor error, part 1 was quick.
For Part 2, after fiddling around for a bit I started outputting a values where the result matched the program at the
end (instead of the start), and the ratio was almost a perfect 8, so instead of incrementing a by 1 I started
multiplying by 8, which quickly yielded the correct result.
A bit of path finding again today. After using Dijkstra for Part 1 (with Nim's heapqueue), brute forcing part 2 was a bit slow with the same approach. After adding a bisect function it worked out really well and quite fast.
As soon as reading this I knew recursion with cutting of front parts would be perfect, and it worked out even better as expected. It reminded me a bit of 2023 Day 13, only simpler.
For Part 2, switching the cache from bool ("have we seen this yet?") to a sum ("how many combinations are possible until here?") was enough.
Today a BFS for shortest path with an interesting twist, to "cheat" and take a shortcut. For part 1 I just checked if I could break through the wall, which would allow for a shortcut.
For part 2 I couldn't wrap my head around a proper solution. I started thinking about a second BFS starting at each position of the path, but wasn't sure if taking a shortcut and then walking a bit along the path would all count as shortcuts.
After seeing this reddit post I had an idea on how to solve it:
Credit: EverybodyCodes
On my first try I kept the paths when finding the shortest path, which was kind of expensive. I later refactored and worked a bit on a proper Dijkstra, which improved runtime quite a bit.
Wow, this one was... hard. And tedious to implement - I quickly started hardcoding paths for both keypads, only to later realize that the shortest path should be found. After playing around with it for a bit I realized that some paths were just better than others in general, not specific to a certain situation.
# Numeric keypad
# +---+---+---+
# | 7 | 8 | 9 |
# +---+---+---+
# | 4 | 5 | 6 |
# +---+---+---+
# | 1 | 2 | 3 |
# +---+---+---+
# | 0 | A |
# +---+---+
# Direction keypad
# +---+---+
# | ^ | A |
# +---+---+---+
# | < | v | > |
# +---+---+---+
For example, when going from A to 0 on the numeric keypad, <^A would be better than ^<A to type, because on the
next robot level, ^ and A are already near each other, so faster to reach.
After hardcoding the (what I thought) best single possible step for part 1, I started re-doing it for part 2, to have all the possible paths and check which one was fastest. I had to go over it again as I was first ignoring the "gaps" in the keyboards. With memoization this was also quick to solve.
Part 1 was fun and easy to implement:
# Step 1
var res = secret * 64
secret = prune(mix(secret, res))
# Step 2
res = roundDown(secret / 32)
secret = prune(mix(secret, res))
# Step 3
res = secret * 2048
secret = prune(mix(secret, res))For part 2 I first struggled a bit understanding the problem, and later struggled a lot with the (only slightly!) changed example data, which gave a slightly different result.
To solve it, I collected all differences and just went through them for each buyer to search for the biggest gain. It's one of the slower days (above 4 seconds) and would be definitely possible to improve on.
Not that of a difficult problem per se, but I struggled a lot with Nim when trying to use HashSet with a custom
object. Even after implementing < and == (which turned out to be needed) it still wasn't working as I expected, so I
switched to simple a Table, which would also provide an efficient lookup.
In part 2 I learned about the maximal clique problem, and read on Wikipedia that a greedy approach would do, which really surprised me! Iterating over all nodes and iteratively adding neighbors as long as all are connected turns out to be enough:
for node in nodes:
all_connected = []
for neighbor in node.neighbors:
if still_connected(all_connected. meighbor):
all_connected.append(neighbor)Part 1 was easy with iterating over rules, and I solved it quickly.
Part 2 was not what I expected - when reading it, I had absolutely no idea on how to solve it. After generating a graph and looking a bit through the connections, which were looking like this:
I noticed some oddities at z39 (for my input), which was not the result of XOR operations. Also z10 and z17 were
odd (directly connected by x/y-inputs).
After reading a bit on the AoC Subreddit I found this very helpful thread which outlines some techniques to verify the proper wiring.
After implementing the rules I was able to get the right result, and that was it. I initially thought I had to provide which exact swaps to make, but it was enough to provide the "faulty" outputs.
An easy puzzle to finish - I just struggled with parsing the input and had some off-by-one errors. After fixing that, it worked out immediately. What a nice Story finish, I really liked it!