advent-of-code-2024
Advent of Code 2024
These are my solutions to AoC 2024.
Overview
- Day 1: C
- Day 2: Rust
- Day 3-4: Crystal
- Day 5: Nim
- Day 6-7: Julia
- Day 8: Python
- Day 9: F#
- Day 10: Ruby
- Day 11: OCaml
- Day 12-13: Python
Notes
Day 1
I have been working at a Ruby shop for the last 5 years, and wanted to get back to something more low-level. What's better than C?
It turns out I'm spoiled by high-level languages, so I spent most of my time implementing a (not very good) library for dynamically allocated strings, arrays, etc. Anything to avoid C strings.
Day 2
While C is pretty fun, the problems in AoC involve a bit of string manipulation (so far) and I realized I'd probably have more fun working in something with a richer standard library. I picked Rust, since it's so popular.
I can definitely see why Rust is getting so popular, especially for use-cases where C/C++ are often used. After messing around in C during Day 1, it was very nice to not worry about overflows, null pointers, double frees, etc.
The compiler messages were impressively helpful, they seem to have improved a lot since the last time I tried out Rust.
Day 3
While Rust was definitely a better fit for me and AoC than C, it's a language with a lot of features and I wasn't super productive. I really liked the safety provided by the compiler and type system though, so I decided to give Crystal a try. Crystal is a statically typed, compiled language with Ruby-like syntax that combines ease of use with the performance of native code, making it great for scripting that can seamlessly grow into scalable production systems.
Since Crystal is so close to Ruby, syntax-wise, and the docs are good so I felt pretty fluent immediately. The type inference is solid, so the types didn't really get in the way of getting things done either. One thing I like about it is that for some bugs I could just add a type annotation and the compiler would tell me what the issue was. Those type of bugs are often more annoying to track down in Ruby or Python.
I still felt the language has some rough edges; the compiler error messages are often helpful but sometimes point at the wrong thing entirely. I was stuck a while on a problem with an iterator implementation because of this.
Day 4
I decided to stick with Crystal since day 3 went so well. This day's problem was the first one this year that I felt I needed to actually problem solve a bit. I guessed a bit what part 2 would be while implementing part 1, so the solution is overly generic, but I'm happy with the idea of representing the search as projections to "rows" of the underlying grid and I only needed to implement a few primitives:
- Getting a list of rows, each containing a list of coordinates pointing to items in the underlying grid.
- Reversing the contents of each row.
- Transposing the list of rows, columns become rows. (This was already in the standard library!)
- Getting a list of "rows", diagonally.
- Mapping a coordinate system to another.
Searching in all directions could be solved using these primitives.
Day 5
Today's problems were pretty fun. The first one was straightforward, but the second took some thinking. I decided to go for a recursive solution, gradually reducing the set of possible candidates. I would have probably done it differently in Python, maybe creating some sort of graph from the rules that can be searched more efficiently. My current version solves both part 1 and part 2 in 61ms, so it's fast enough for me.
I decided to give Nim a shot. Nim is a statically typed, systems programming language that combines Python-like syntax with the performance of C, offering seamless metaprogramming, cross-platform compilation, and efficient memory management for developers looking to write elegant yet fast code.
The documentation really felt messy ("All Nim documents and modules in one place. Use Ctrl/Cmd+F."). That might be fine if you know what you're looking for, but it's not discoverable the way the Crystal or Python docs are.
The compiler errors are sometimes not very helpful. Can you guess what the problem on this line is?
solution1.nim(40, 14) Error: type mismatch
Expression: rules_set[before] = newSeq(Natural(0))
[1] rules_set: Table[system.int, seq[int]]
[2] before: int
[3] newSeq(Natural(0)): seq[int]
Expected one of (first mismatch at [position]):
[0] proc `[]=`[I: Ordinal; T, S](a: T; i: I; x: sink S)
[1] proc `[]=`(s: var string; i: BackwardsIndex; x: char)
[1] proc `[]=`[A, B](t: OrderedTableRef[A, B]; key: A; val: sink B)
[1] proc `[]=`[A, B](t: TableRef[A, B]; key: A; val: sink B)
[1] proc `[]=`[A, B](t: var OrderedTable[A, B]; key: A; val: sink B)
[1] proc `[]=`[A, B](t: var Table[A, B]; key: A; val: sink B)
expression 'rules_set' is immutable, not 'var'
[1] proc `[]=`[A](t: CountTableRef[A]; key: A; val: int)
[1] proc `[]=`[A](t: var CountTable[A]; key: A; val: int)
[1] proc `[]=`[Idx, T; U, V: Ordinal](a: var array[Idx, T]; x: HSlice[U, V];
b: openArray[T])
[1] proc `[]=`[Idx, T](a: var array[Idx, T]; i: BackwardsIndex; x: T)
[1] proc `[]=`[T, U: Ordinal](s: var string; x: HSlice[T, U]; b: string)
[1] proc `[]=`[T; U, V: Ordinal](s: var seq[T]; x: HSlice[U, V]; b: openArray[T])
[1] proc `[]=`[T](s: var openArray[T]; i: BackwardsIndex; x: T)
[1] template `[]=`(a: WideCStringObj; idx: int; val: Utf16Char)
[1] template `[]=`(s: string; i: int; val: char)
The problem is that the rules_set
variable was assigned as immutable (using let
, like in Javascript). Changing the assignment to var
solves this problem:
- let rules_set: Table[int, seq[int]] = initTable[int, seq[int]]()
+ var rules_set: Table[int, seq[int]] = initTable[int, seq[int]]()
Another solution would be to keep the let
but changing the type to TableRef
:
- let rules_set: Table[int, seq[int]] = initTable[int, seq[int]]()
+ let rules_set: TableRef[int, seq[int]] = newTable[int, seq[int]]()
I still didn't wrap my head around Nim's naming conventions. One example is initTable
vs newTable
from the issue above.
The language seems to use a lot of macros, which can be okay, but when you google using Kagi for things like "list comprehension Nim", you find references to the sugar.lc
macro (and future.lc
?) which has been removed. The current way to achieve this is to use the capture macro. Another language feature added like this is pattern matching that I found while looking for destructuring assignments.
The problem for me is that there are multiple ways of doing things, they might be removed, and you can of course even make your own. This kind of churn can lead to two issues that I've noticed in the Lisp world. The first one is that since everyone defines the language features they need, code bases can get very difficult to read even if you know the language/dialect well. What's worse is that library support will be lacking, if big language changes happen frequently, the cost of maintaining a library will be high. As a maintainer, do you make one version of the library for each version of the language, or do you target the latest version only? How much work will it be to re-write the library when the language changes? Do you limit yourself to only use "stable" language features and do you even know what they are?
There's a lot to like in Nim, but I found several things that I think would annoy me in the long run. Usually small things, like the weird slice syntax (list[0 ..< list.len]
), the limitiations in destructuring assignments, and the confusing error messages. The thing that bothered me the most was the general ergonomics of the data structures in the standard library though. I think Crystal is more to my taste, at least so far.
Day 6
Fun problems today, walking on a grid, finding loops. For part 1, my approach was to basically just save the positions I've visited in a set, then count it as soon as the guard goes out of bounds.
For part 2, I re-used the set of locations from part 1. I just checked all the visited locations and if blocking it would create a loop. It was slow, but about 30% of the time it would take to check all locations on the grid.
It's getting late, but walking backwards might save some time since about 1/3 of the locations create loops when blocked, and loops are often quite tight. Maybe some kind of memoization would be nice too, but the board changes each time so that would obviously be a problem...
Anyway, I switched to Julia today. Julia is a high-performance, dynamically-typed programming language designed for scientific computing, combining the ease of Python with the speed of C. It feels just right for me, so far. The docs are super nice. The type errors can be a bit dense, but once you get used to them it's easy to figure out what's wrong.
I'm still getting used to the multiple dispatch feature, which kind of defines the whole language. It seems like a powerful thing.
Other things I liked: the REPL, optional types, the macro system seems nice and doesn't appear to be overused, rich set of data structures such as multi-dimensional arrays and sets.
Day 7
Two more solutions in Julia. I had less fun today, but was still fairly productive. Part 2 was just a small change to part 1 in my case.
One lightly disappointing aspect of Julia's design is the piping operator |>
(which, coincidentally looks like Santa's hat <|:)
). It has the potential to really clean up some expressions that currently get pretty ugly.
First of all Julia doesn't have partial application/currying, so "a,b" |> split(",")
doesn't work. If it did, splitcommas = split(",")
would be a new function that takes a single argument and only splits on commas.
Another way to potentially solve this is with placeholders, like "a,b" |> split(_, ",")
. The Pipe.jl package implements placeholders like this, but I'm trying to stick to vanilla Julia for now (see my rant about macros that introduce new language features above).
I also experimented a bit with threading and multiprocessing. The multiprocessing feature seems very powerful, but too heavy for small programs like this.
Day 8
I didn't have much time for AoC today, so I decided to go with Python.
For small programs like this when you mostly use simple built-in data structures (dictionaries, tuples, arrays, iterators), runtime errors are not much worse than compile time errors honestly. Feels good to be home.
Day 9
F# felt well-designed, but also tainted by .NET somehow. It was pretty fun.
I decided to use F# today. It was easy to get started, and I appreciated the documentation and reasonably helpful compiler errors. The language strikes a good balance between functional and imperative paradigms, and I found it refreshing to mix approaches. For instance, I updated an array in place while looping over its indices — it felt natural despite being impure, and it worked seamlessly with the functional parts of my solution.
There were some pain points. Without lazy evaluation by default, the code got relatively verbose, with a lot of seq
expressions. F#'s compilation speed felt slow for a scripting use case, especially compared to lighter languages. I also struggled to find a good way to handle polymorphism — multiple dispatch or type classes weren't an option, and while pattern matching worked, it felt like too much effort.
Overall, F# was pretty fun but I can't decide if it's best or worst of both worlds. Perhaps it's too much of a compromise? I'm not sure if I'll come back to it.
Day 10
Today's problem was a fun opportunity to dust off the dynamic programming. Starting from a trailhead, we can reach at most 4 neighbors, and if we only go from lower to higher cells there is no way to form a loop. The trail stops when there's no reachable neighbor. This means that each trailhead forms the root of a DAG, and another (perhaps less merry) way to describe the problem is to count the paths to the leaf nodes at depth 9 for each graph, and then add them up. Since you can traverse the grid according to the height differential rules and only visit each cell once to calculate the score, the solution should be in O(n)
.
I started by calculating the score for each trailhead. And the score for a cell is 1 if it's a peak at height 9, otherwise it's sum of the scores of all reachable neighbor cells, iteratively. The score for each cell is stored in a grid of the same shape to avoid recalculations.
Since we start from the trailheads, there are some parts of the grid that we don't even have to calculate, but I assume calculating each cell would have been almost as fast.
I went with Ruby today, I needed a break from functional programming after F# yesterday.
Day 11
I went functional again, with OCaml this time. It's my favorite functional language in this year's AoC so far. It was the first time I tried OCaml, so there was a bit of learning going on even though it's recognizable if you are familiar with other functional languages in the ML family. I really enjoyed the solid docs and the manual. There's also a free text book from Cornell University, called OCaml Programming: Correct + Efficient + Beautiful (formerly "Functional Programming in OCaml") which seems like a great introduction to both OCaml and functional programming in general.
Today was also my favorite problem so far. Part 1 was suspiciously easy, almost trivial (except I was learning OCaml in parallel) — just apply some simple rules to a list of items and iterate 25 times, then count the number of items.
The fun started in part 2, which was the same as part 1 (for the first time this year) but with 75 iterations instead of 25! I tried just changing the number of iterations, but the time complexity was quadratic or worse — 33 iterations took 5 seconds, 34 iterations took 10, and 35 iterations took 20 seconds. I don't have 57,000 years — so I had to think of something.
I was hoping to not have to rewrite everything, so my first attempts at speeding up the solution were to first memoize the two most frequently called functions, and when that didn't help much I tail-call optimized the heaviest function. Slightly better, but didn't help with the overall complexity:
After a break, I realized that I could just keep track of the number of occurrences for each item, and then update them all at once. I did this with a Hashtbl in order to easily do counts and iterating over each key-value pair. I haven't done a thorough analysis of the time complexity for this version, but it's running 98 iterations in about 0.2 seconds (after that, I get an int overflow) so I'd guess it's in O(iterations * input length)
or something like that.
Day 12
I started to solve day 12 in OCaml, but realized it would take too long so I went back to Python, and probably will use it for the rest of this year's AoC.
Today was not super difficult, but it was a bit tricky to implement the algorithm I came up with correctly and I had some interesting bugs. In the end, the code got a bit ugly but does the job.
Day 13
I solved part 1 iteratively - it worked well and was easy to implement, but was quite slow. Before moving on to part 2, I tried to optimize the code a bit by calculating the upper bounds of the number of button clicks and by returning early. When I was thinking about these optimizations, I realized that each machine really represented a linear equation system so I had a hunch about what was coming up in part 2.
Part 2 was basically the same as part 1 today as well, but with much larger numbers. The iterative approach is not feasible any more, and I swapped my first solution with one that solves the equation systems instead. I could have used numpy or (sympy)[https://docs.sympy.org/latest/guides/solving/index.html] but since it was just two equations I figured I could do it manually with the standard library and brush up on my linear algebra at the same time. Each machine is now solved in O(1)
, which felt very satisfying. Solving both part 1 and part 2 is O(N)
where N is the number of machines.
advent-of-code-2024
- 0
- 0
- 0
- 0
- 0
- 26 days ago
- December 2, 2024
Fri, 10 Jan 2025 09:55:55 GMT