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)"
- The
- @kaychaks
- This solution pipes together a bunch of
List
operations from the standard lib. For example, there's a clever use ofsubsequences
, in case you're looking for a way to generate all possible subsequences of a list.
- This solution pipes together a bunch of
- @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
andStore
abilities to solve problems this year. TheEach
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 withEach.guard
if a condition is not met for one or more of those values.
- @naufalauddin introduces the trend of using both the
- @dfreeman
- @dfreeman wrote a custom
Grid
ability, and that decision might have been prescient. TheEach
ability and calls toEach.guard
for filtering out data abound in this solution.
- @dfreeman wrote a custom
- @stew
- Stew's writeup includes a helpful discussion of two's compliment since he's using
Int.fromRepresentation
andInt.toRepresentation
to convert between Unison'sNat
(64 bit unsigned integers) andInt
(64 bit signed integers) types.
- Stew's writeup includes a helpful discussion of two's compliment since he's using
- @rlmark
- This solution represents the grid as a
Map (Int, Int) Char
instead of nested lists. AMap
based representation can be a nice option if you don't prefer the list indexing management entailed by a[[Char]]
representation.
- This solution represents the grid as a
- @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
Location
s in theBoundingBox
are candidates to place an obstacle." ๐ณ
- @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
- @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"
- @vtomilin used Unison's
- @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."
- "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
- @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
andMap
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.
- This solution includes a nice explanation of the key points of the algorithm, which features a slew of
- @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"
- 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
- @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. #๏ธโฃ
- "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
๐ชจ Day 11: Plutonian Pebbles
- @kaychaks
- ๐ข "Order is a lie, frequency is the truth", thus spake @kaychaks.
- @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 acost
which is based on itspermiter
andarea
etc.
- This solution models the domain such that the moving parts of the problem are expressed in terms of their types, for example a
- @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."
- "A sparse representation like
- @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.
- "About time I wrote a proper grid library." In addition to featuring a nice
๐น๏ธ 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?
- @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
aX * a + bX * b = prizeX \\
aY * a + bY * b = prizeY
- @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."
- @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" ๐ค
- There's a nice
- @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.
- 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
๐ฅ๏ธ 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 ofrender
"
- If you ever need inspiration for a shortest path algorithm, there's
- @benwaffle
- Here's another tidy example of using the
Store
ability to memoize results and thereby reduce repeated work.
- Here's another tidy example of using the
๐๏ธ 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 ๐.