+merlan #flirora

Advent of Code 2024 in 24 + 1 programming languages

 code

There’s a yearly series of code challenges called Advent of Code. I participated in the first one in 2015 but didn’t do any since then – at least, until this year. I decided to give this year’s one a try, but with a twist: I would use a different programming language for each day’s challenge.

The rules:

I split the challenge into three legs:

Repository for my solutions.

Day 1 (Historian Hysteria) – Raku

Difficulty: Easy

Starting off with an easy challenge in one of my favorite languages! Part 1 was a one-liner, while Part 2 was a four-liner. Look, I can even paste it here:

# Part 1
say [+] map &abs, [Z-] map &sort, [Z,] "01/input".IO.lines.map(*.words);
# Part 2
my $ls = [Z,] "01/input".IO.lines.map(*.words);
my @l = $ls[0];
my $r = bag $ls[1];
say @l.map({$_*$r{$_}}).sum;

The only reason it took 4 hours is because I forgot about Advent of Code until almost 4 hours into the first day.

Day 2 (Red-Nosed Reports) – Ruby

Difficulty: Easy

Another easy challenge, but in a language I’m unfamiliar with.

Day 3 (Mull It Over) – Racket

Difficulty: Easy

Took some effort to find out how to use regexps in Racket, but overall, not a hard problem.

Day 4 (Ceres Search) – Setanta

Difficulty: Easy

Again, this is conceptually easy, though I ran into quite a few off-by-one errors with this one.

Day 5 (Print Queue) – Lua

Difficulty: Easy

Part 1 is a matter of checking that no pair of pages has a rule with the pages in the opposite order. You might think that Part 2 needs a topological sort, but I managed to do it with the built-in table.sort function: if there’s a rule prescribing an order for two pages, then return that for the ordering; otherwise, return the order they were in. The rest is dealing with Lua itself: it doesn’t have a string-splitting function, so I had to write one myself. Why does anyone use this language?

Day 6 (Guard Gallivant) – JavaScript

Difficulty: Hard

I personally had trouble with Part 2: my solution would give the correct answer for the example input but not my actual one. I frantically tried to debug my program until I realized that it didn’t properly handle the case when the guard turned twice in a row. So this:

if ((map[row2][col2] == '#' || (row2 == obrow && col2 == obcol))) {
    let dx2 = -dy;
    dy = dx;
    dx = dx2;
}

turned into this:

if ((map[row2][col2] == '#' || (row2 == obrow && col2 == obcol))) {
    let dx2 = -dy;
    dy = dx;
    dx = dx2;
    continue;
}

My Part 2 solution still took 38 seconds, but that was good enough to solve the problem.

Day 7 (Bridge Repair) – Common Lisp

Difficulty: Easy

Another unfamiliar language today (hi, Iso!). The parsing code took me a while to figure out, especially as I was reading this page to find out how to use loop. At first, I thought that I would have to write all the string-handling functions myself, before I realized that they were there, but as sequence functions. (One of the pages on The Common Lisp Cookbook led me in the right direction.) Common Lisp also lacks a built-in string-splitting function, but for my use case, I can wrap the string in parentheses and read it as a list.

Aside from that, the problem itself was an easy recursion.

Day 8 (Resonant Collinearity) – Uiua

Difficulty: Medium

Part 1’s solution involved finding all pairs of antennae (a,b)(a, b) with the same frequency, getting the antinodes, and removing duplicate elements. Part 2 was largely the same, except that I calculated the bounds for the indices ii for which a+i(b−a)a + i(b - a) was in bounds. This took a lot of finagling with the stack but produced the correct answer in the end.

I thought that my Part 2 solution could get some improvement to be more idiomatic. My new solution started from 2a−b2a - b and stepped by a−ba - b until the coordinates were out of bounds. The revised solution is in 08/08b_v1.ua; the vs are zero-indexed, so any _v1 file is newer than the corresponding file without _v1.

(Technically, I handled the case when the offset between the antennae was reducible, but this might not have been necessary?)

Day 9 (Disk Fragmenter) – Python

Difficulty: Medium

Part 1 was easy (modulo edge cases); part 2 required a lot of thinking to find a reasonably efficient approach. I initially tried explicitly representing gaps, but that would have required logic for merging them. In the end, I only represented the files explicitly, with the gaps being implicit.

Still, my initial part 2 solution took 15 seconds, so six days later, I revisited the problem. I noticed that merging gaps was unnecessary since the space a file is moved from is never repurposed, so it sufficed to keep a list of gaps for each length (from 1 to 9). My new solution finishes in under 100 milliseconds.

Day 10 (Hoof It) – Perl

Difficulty: Easy

We finish our first leg with Raku’s ancestor and the language that Raku was originally named after: Perl!

Initially, I misread Part 1 and calculated the number of distinct hiking trails from each trailhead. After I fixed my code, I noticed that this was what Part 2 called for! Less than two minutes later, I had a solution for that.

Day 11 (Plutonian Pebbles) – Java

Difficulty: Easy

Part 1 was straightforward. Since Part 2 replaces the number 25 with 75, it should be easy as well, right? Turns out that even with an optimized LongList implementation, my code couldn’t get past 42. I initially thought that the list of stones might have some kind of redundancy in them, but the key insight is a lot simpler: since the order doesn’t matter, you can store the stones as a HashMap<Long, Long>.

Day 12 (Garden Groups) – Haskell

Difficulty: Medium

Ordinarily, I would use a mutable array to represent the regions during flood filling, but we can’t have that in Haskell (at least, not without a lot of trouble), so I used sets instead. (I could still use an immutable array for the garden itself, though.) Part 2 checks whether each fence is the leftmost (or rightmost, depending on the orientation) fence of the side. The rest is a matter of relearning Haskell.

Day 13 (Claw Contraption) – Nim

Difficulty: Medium

Part 2 is a matter of solving systems of linear equations (nothing is degenerate). For some reason, I solved them in a roundabout way using an extended Euclidean algorithm, but this was unnecessary.

Day 14 (Restroom Redoubt) – Kotlin

Difficulty: Hard

Part 2 required finding the first time when a group of robots form picture of a “Christmas tree”. When I read the statement, I panicked and looked through the Advent of Code thread on a Discord server. Some people managed to find the answer by finding the first time that all the robots had unique positions, but as my frame was late in the sequence, this didn’t work for me. Eventually, I decided to print the first 1,000 frames out for inspection, then 3,000, then eventually all WIDTH * HEIGHT frames. Since this took too long to inspect by hand, I searched for a row with enough @ signs and found the right frame (no pun intended).

While I initially disliked this problem, I’ve found it fun in retrospect.

Day 15 (Warehouse Woes) – Gleam

Difficulty: Medium

Another problem made harder by working in a purely functional language, in my opinion.

Day 16 (Reindeer Maze) – Scala

Difficulty: Medium

Part 1 is a straightforward implementation of Djikstra’s algorithm; Part 2 runs the search to completion while storing the predecessors to each node.

Day 17 (Chronospatial Computer) – Go

Difficulty: Extreme

Part 2 can feasibly be brute-forced with enough attention to performance and use of multithreading, but I didn’t think that was a viable option for Go, especially since I was unfamiliar with the language. I didn’t do much to inspect the structure of the program I was given, so I turned to expressing the problem as a Boolean satisfiability problem and writing a simple SAT solver to solve it. This was extremely error-prone, so I took a few measures to ease debugging:

In the end, this took almost six hours to complete.

Day 18 (RAM Run) – C#

Difficulty: Easy

An easier maze-based problem; for Part 2, a straightforward linear search works well enough.

Day 19 (Linen Layout) – F#

Difficulty: Easy

For Part 1, a recursive solution performs well enough. This poses a problem for Part 2, though, so I slapped some memoization on it to make it run faster.

Day 20 (Race Condition) – OCaml

Difficulty: Hard

Initially, I tried storing the cheat state of each node (either not having cheated yet, currently using a cheat, or having cheated). After a lot of debugging to weed out edge cases, this produced the correct answer for the example input but took too long for the real input. After unsuccessfully trying a few other approaches, I had the insight of running BFS twice: first to find the time needed to reach the end from each position and second to find each route in a real run. In particular, the latter step involves jumping from each visited node to a node 2 blocks away and finding [cost of current node]+2+[stored cost from new node to finish]\text{[cost of current node]} + 2 + \text{[stored cost from new node to finish]}. Part 2 is then straightforward, instead iterating through a neighborhood with a radius of 20 (and using the L₁ distance from the current node to the new one instead of 2).

Day 21 (Keypad Conundrum) – Swift

Difficulty: Hard

I initially tried a top-down approach for Part 1, but it’s not clear which order of movements is optimal for moving through the numeric keypad. Instead, I worked from the bottom up:

The advantage of storing only the lengths is that you get Part 2 for (almost) free.

Day 22 (Monkey Market) – D

Difficulty: Easy

Part 1 is strightforward programming. For Part 2, scan each monkey’s sequence and tabulate the price for each sequence of four changes (stored as a uint in my code). The result for each monkey can be added together, and the maximum value of the result is the answer.

Day 23 (LAN Party) – C++

Difficulty: Medium

Part 1 involves finding 3-cliques (with some logic to avoid duplicates in my solution). For Part 2, I used a dynamic programming-ish solution, starting with 3-cliques and then growing each clique by 1 until no cliques remain.

Day 24 (Crossed Wires) – Zig

Difficulty: Extreme

Part 1 is easy enough. I wasn’t feeling like implementing another SAT solver for Part 2, so I decided to search for the carry wires for each place. Since for each place, we only have to worry about three inputs, we can store the behavior of each output with 8 bits. Unfortunately, trying all permutations of 8 distinct wires will take too long. Instead, we perform a backtracking search: if we can’t find the carry wire or the output wire doesn’t have the expected behavior, then try all swaps of two wires (if you haven’t already swapped four pairs of wires). (I didn’t happen to have an input that requires multiple wire swaps within a place.)

I found writing Zig code painful – the compiler doesn’t typecheck a function unless it’s called from main. At least C++ does that for functions that don’t use templates. Also, needing parentheses after an if or while was annoying after years of writing Rust. Speaking of Rust, I’ve saved it for the last day. With the fiendish Day 24 challenge out of the way, there’s just one more problem to go.

Day 25 (Code Chronicle) – Rust

Difficulty: Easy

Trying all lock–key combinations is fast enough here. Part 2, of course, is trivial.