โ›… Coming soon: create Unison Cloud clusters in minutes on your own infrastructure. Learn more
highlights
Jan 21, 2025

๐ŸŽ„ Advent of Code 2024 mega-writeup

Rebecca Mark

This year's Advent of Code season was a festive one! It was the tenth anniversary of Advent of Code and Unison joined the ranks of official Advent of Code sponsors.

We've selected a few of our favorite solutions, along with some choice quotes from the solution write-ups, and added some notes about what makes them exceptional. Together they constitute a masterclass in writing Unison code, and explore everything from the power of algebraic effects, to lesser known parts of the standard lib, to insights about algorithms and the design of efficient programs.

Take a peek. ๐ŸŽ

๐Ÿง“๐Ÿผ Day 1: Historian Hysteria

    • @kylegoetz
      • The Set type makes its first appearance this year: "We don't actually need to count the number of occurrences. Just build a fast way of determining if something in the right column is in the left column (use a set for this)"
    • @kaychaks
      • @kaychaks uses NatSet: a specalized form of Set in the standard lib that has been optimized for storing Nats.
      • The implementation also features the operator, >> : (a ->{๐•–} b) -> (b ->{๐•–} c) -> a ->{๐•–} c, for folks who like composing together functions.

๐Ÿ‘ƒ Day 2: Red-Nosed Reports

    • @kaychaks
      • This solution pipes together a bunch of List operations from the standard lib. For example, there's a clever use of subsequences, in case you're looking for a way to generate all possible subsequences of a list.
    • @stew
      • Stew's excellent recursive list-based solution features inline Doc notes and also proves that Greek letters are valid variables in Unison: ฮด = h - last

๐Ÿค” Day 3: Mull It Over

    • @rlmark
      • @rlmark's write-up includes a deep dive into writing a parser which uses backtracking for the input data.
    • @naufalauddin
      • @naufalauddin introduces the trend of using both the Each and Store abilities to solve problems this year. The Each ability is a way to lazily create all values in a list or range. (Handy, for many of these puzzles, because it can be used to create (x,y) values in combination.) We can also abort the computation with Each.guard if a condition is not met for one or more of those values.
Each.toList do use Each range use Nat isEven x = range 0 5 y = range 0 5 guard (isEven x && isEven y) (x, y)

๐Ÿ›ฐ๏ธ Day 4: Ceres Search

    • @dfreeman
      • @dfreeman wrote a custom Grid ability, and that decision might have been prescient. The Each ability and calls to Each.guard for filtering out data abound in this solution.
    • @rlmark
      • This solution represents the grid as a Map (Int, Int) Char instead of nested lists. A Map based representation can be a nice option if you don't prefer the list indexing management entailed by a [[Char]] representation.

๐Ÿ–จ๏ธ Day 5: Print Queue

    • @chrispenner
      • Chris's write up also reveals something about how Unison code is synced with Unison Share, "Interestingly I ended up solving this one using a trick for easy topological sorting that I discovered when designing a new faster sync algorithm for Unison code itself!"
    • @dvberkel
      • "This is the first time this year that I wanted to introduce some types to keep track of the various concepts that this puzzle brings." Types make for very elegant code!
    • @dfreeman
      • In which @dfreeman asks, "How have I never needed a topological sort in Unison before?" ๐Ÿค” There's a first time for everything in Unison!
    • @stew
      • Not a fan of topological sorting? Stew's writeup uses a reverse mapping strategy with multiple maps to solve part 2 of the problem.

๐Ÿ’‚โ€โ™€๏ธ Day 6: Guard Gallivant

    • @dvberkel
      • @dvberkel talks about using Floyd's cycle-finding algorithm in his solution. It contains a lovely narration of figuring out an optimization for one of the parts of the problem. "So while making breakfast, I started thinking about improvements. Thinking hard about the problem, it became clear that not all Locations in the BoundingBox are candidates to place an obstacle." ๐Ÿณ
    • @systemfw
      • "This problem deserves a proper writeup, I managed to have Part 2 run in around 2.5 seconds despite the slowness of the current interpreter." @systemfw's writeup includes 3 ideas for tackling the problem, commentary about how the problem relates to his day job as Unison's own distributed systems expert, and one beautiful svg drawing.
    • @vtomilin
      • @vtomilin used Unison's concurrent.Promise API to speed things up: "I added a parallel version for part 2 solution, which runs concurrently about 10 times faster that the original day6.solution2"

๐ŸŒ‰ Day 7: Bridge Repair

    • @dvberkel
      • @dvberkel's solution uses the Each ability and some tidy custom types for Operators and Equations. He also adds some historical commentary about reverse polish notation and stack-based HP calculators for the curious technologist in all of us. ๐Ÿงฎ
    • @vtomilin
      • "My point for this challenge was to build a syntax tree for each equation with all possible permutations of given operators: + and * in part 1 and that plus || in part 2, then solve the equations that can be solved. Permutations are generated with permutationsOf function."
    • @systemfw
      • "The key idea is to build a tail recursive function that operates over a list of candidate results. Each iteration evaluates the next generation of results by applying all operators to the previous generation."

๐Ÿ“ก Day 8: Resonant Collinearity

    • @vtomilin
      • "The key to solving day 8 was to use vector form for line equations, which avoids floating point arithmetics and makes points projection calculations much simpler." ๐Ÿ“
      • Kudos to @vtomilin for prompting us to remember (or google) the vector form for line equations.
    • @systemfw
      • This solution includes a nice explanation of the key points of the algorithm, which features a slew of List and Map translations. groupMapReduce makes an appearance, which is a helpful function to bookmark if you need to turn a list into a map with some kind of aggregation logic.

๐Ÿ’ฟ Day 9: Disk Fragmenter

    • @systemfw
      • "The algorithm uses two tricks from my day job in distributed systems: not doing compaction in place and keeping a separate free list. Copying to a separate location means compaction can proceed without affecting concurrent reads to the same storage blocks, and keeping a separate free list means we only have to linearly scan the free slots to find a suitable one, rather than all of the data."
    • @dvberkel
      • "When there are a lot of moving parts, I like to introduce types. It allows me let the compiler help me keep my ps and qs straight. The types that I introduced are DiskMap,Segment and Identifier". Indeed, what we love about this solution is how legible it is. It includes a tail-recursive function in part 1 and mutually recursive functions in part 2.
    • @ceedubs
      • This is a fantastic walkthrough that explores the tradeoffs of different data types along the way. "I spent way too long trying to think of clever ways to implement the compaction for part 2. I started down paths of using heaps and NatMap, and even briefly considered building my own interval map. (...) But in the end I decided that I didn't need to be fancy and I could handle this with 3 lists"

๐ŸŽ Day 10: Hoof It

    • @dfreeman
      • "Both parts of today's solution involve explore-ing each location on the given grid to see if it represents a valid trailhead, and if so, where it leads." @dfreeman's explore function makes use of the Each ability and his custom Grid ability.
    • @vtomilin
      • "Anyhow, solved the goode-olde boring fashion way: part 1 kinda simple, part 2 a bit more involved but just had to keep track of trail paths with a cumulative hash per path using murmurHash." If there's anything we at Unison love, it's the power of hashing things. #๏ธโƒฃ
    • @benwaffle
      • @benwaffle used Each, with guard when walking the grid, which made for an excellent, very clean solution. guard : Boolean ->{Each} () aborts the current iteration of the computation if the condition is not met.

๐Ÿชจ Day 11: Plutonian Pebbles

    • @kaychaks
      • ๐Ÿ”ข "Order is a lie, frequency is the truth", thus spake @kaychaks.
    • @dvberkel
      • @dvberkel's writeup includes an interlude where the UCM turns into a space heater during breakfast and runs out of memory. ๐Ÿฅž Then he uses memoization as an optimization technique. Read about it if you're curious about how to memoize Unison values with the Store ability.
    • @systemfw
      • We love this writeup because @systemfw takes the time to indicate what elements of the computation are repeated work, and are therefore good targets for optimization, "The same number may appear more than once in one iteration, which is very similar to the issue in Day 10. The same number may appear more than once across iterations, i.e. we have a cycle in our generation process."

๐Ÿง‘โ€๐ŸŒพ Day 12: Garden Groups

    • @dvberkel
      • This solution models the domain such that the moving parts of the problem are expressed in terms of their types, for example a Component has a cost which is based on its permiter and area etc.
    • @kaychaks
      • Here's a classic floodfill algorithm for finding contiguous spaces by @kaychaks.
    • @systemfw
      • "A sparse representation like Map Point Char is really useful here, because we have to model regions of arbitrary shape, and we can actually start by computing the perimeter of such a region."
    • @benwaffle
      • "About time I wrote a proper grid library." In addition to featuring a nice Grid api, @benwaffle's writeup also includes some beautiful ascii art in explaining this algorithm.

๐Ÿ•น๏ธ Day 13: Claw Contraption

    • @dvberkel
      • Ah, to have the beautiful mind of @dvberkel: "You can solve this problem by doing linear algebra."
    • @benwaffle
      • @benwaffle also broke out the linear algebra and even included LaTeX snippets in Unison's doc format. By the way, did you know Unison's Doc format supports rendering LaTeX?
  aX * a + bX * b = prizeX \\
  aY * a + bY * b = prizeY

๐Ÿšพ Day 14: Restroom Redoubt

    • @systemfw
      • Buckle up folks, when @systemfw's curiosity is piqued we're in for one hell of a trip: "An absolutely wild ride, and I still haven't decided if this problem was more brilliant or frustrating. It did grant me some interesting insight though, let's dive in."

๐Ÿ“ฆ Day 15: Warehouse Woes

    • @systemfw
      • "The basic strategy is to compute the region of boxes to move, then delete that region from the warehouse, and re-add it after shifting it in the desired direction." @systemfw further jots down the basic frontier search logic for this problem in his explanation.
    • @benwaffle
      • There's a nice show function in this implementation. Quoth @benwaffle, "It's fun to watch the robot push boxes around" ๐Ÿค–

๐Ÿ—บ๏ธ Day 16: Reindeer Maze

    • @benwaffle
      • Yes, it's that time of the Advent of Code season where someone implements Dijkstra's algorithm in Unison! You'll see the gist of it in day16.dijkstras in the project repo. Spoiler alert, we'll likely be seeing Dijkstra's algorithm again.

๐Ÿ–ฅ๏ธ Day 17: Chronospatial Computer

    • @benwaffle
      • There's always an Advent of Code puzzle which is something along the lines of "write a mini computer" This year is no different. Here's @benwaffle writing a bytecode interpreter.

๐Ÿƒโ€โ™‚๏ธโ€โžก๏ธ Day 18: RAM Run

    • @benwaffle
      • As promised, here's more Dijkstra's algorithm from @benwaffle.
    • @systemfw
      • If you ever need inspiration for a shortest path algorithm, there's findShortestPathAt in this repo. "I decided to code it again in a more standalone style without additional datatypes. Even though we don't actually need the set of all paths for this problem, it's useful for debugging, with the help of render"

๐Ÿ› Day 19: Linen Layout

    • @dvberkel
      • @dvberkel explores using the Each ability and the Store ability in this solution. In the end, he uses the Store ability to memoize a Map k v to significantly improve the runtime of the program.
    • @benwaffle
      • Here's another tidy example of using the Store ability to memoize results and thereby reduce repeated work.

๐ŸŽ๏ธ Day 20: Race Condition

    • @benwaffle
      • Dijkstra strikes again! This solution finds the shortest paths to every node from the start and the end. Here @benwaffle, as the longest running Advent-of-Code contributor this year, you dropped this ๐Ÿ‘‘.