Published on Jan 10th, 2022
Ho-ho-hope you like puns
For many of us, December sparks the beginning of a very special time of the year. Folks from all around the world gather together to share in the most incredible of human experiences: computer science homework.
This year, I wanted in on the fun! That’s why I chose to solve some of the world’s most fictional problems with Advent of Code 2021.
For those of you who are new to Advent of Code, I’ll give you the TLDR. Each day (going from December 1st to December 25th) a programming problem is released at midnight. These problems all relate to a silly story, usually involving something Christmas-like. This year, we saw the compelling tale of elves in a submarine, desperately trying to find keys at the bottom of the ocean.
I really wanted to make some Elm content, and I know that videos are how I learn best. I thought it would be fun to record a week’s worth of YouTube videos showing how to solve these problems in Elm!
This blog post breaks down each of the videos in my Advent of Code 2021 playlist, and what techniques helped me out each day.
Day 1
For day one, I introduced the series and showed how we can use Ellie to create Elm programs in the browser. This is the technique I used throughout the series so you can run the solutions for yourself from the video description.
Because the inputs for Advent of Code all use raw strings, I also needed to demonstrate how you can go from text to data structures you can actually work with. Additionally, I wanted to show how to use Elm’s pipe operator (|>) to incrementally check our progress as we work through the problem.
This is where we relied on a few functions from Elm’s core library:
String.lines- Split our multiline text input into a list of stringsString.fromInt- Attempts to convert a string like"123"into an integerList.filterMap– turns a list of maybes into a list of normal things
rawTextInput : String
rawTextInput =
"""
123
456
789
"""
Step 1. Lines of text
result : List String
result =
rawTextInput
|> String.lines
|> List.map String.trim
[ "123", "456", "789" ]
Step 2. List of possible numbers
result : List String
result =
rawTextInput
|> String.lines
|> List.map String.trim
|> List.map String.toInt -- ADDED
[ Just 123, Just 456, Just 789 ]
Step 3. List of numbers
result : List String
result =
rawTextInput
|> String.lines
|> List.map String.trim
|> List.filterMap String.toInt -- CHANGED
[ 123, 456, 789 ]
Using List.filterMap here is a great way to throw out invalid lines of input. Fortunately, the actual input for Advent of Code didn’t have any issues. If it did, Elm prevents our program from crashing by making us handle the Maybe Int conversion in a safe way.
Day 2
Things went much better for me in day two! We were able to zoom through part one of the problem, and part two reused everything but a single function.
The cool new thing we did here was convert our raw input into a custom type. In Elm, a “custom type” is basically like an enum except it let’s us:
- Hold onto data in each variant
- Makes sure we don’t forget to handle a case
- Is a distinct kind of value from string or int
Here’s what we created to solve the day’s problem:
type Command
= Forward Int
| Up Int
| Down Int
Our raw input looked something like this, so we used List.filterMap with a function to convert from a string of text into a Maybe Command:
rawInput : String
rawInput =
"""
forward 15
up 10
down 30
"""
commands : List Command
commands =
rawInput
|> String.lines
|> List.map String.trim
|> List.filterMap toCommand
toCommand : String -> Maybe Command
toCommand line =
case String.split " " line of
"forward" :: numberText :: [] ->
String.toInt numberText
|> Maybe.map (\num -> Forward num)
"up" :: numberText :: [] ->
String.toInt numberText
|> Maybe.map (\num -> Up num)
"down" :: numberText :: [] ->
String.toInt numberText
|> Maybe.map (\num -> Down num)
_ ->
Nothing
-- commands
[ Forward 15, Up 10, Down 30 ]
By using String.split " ", we were able to break apart the raw text into segments and use Elm’s pattern matching to convert the lines of text into actual commands.
Once we had a custom type, our Elm program allowed us to perform updates for any of the three commands we received (either Forward, Up, or Down).
Day 3
On day three, I may have accidentally recorded the whole thing with the microphone unplugged. Being a YouTube amateur is hard, ya know?
Anyway, this video was fun because we were able to install a package from Elm’s official package website to help with the binary numbers. The package we chose was icidasset/elm-binary and it came along with great docs!
With this package, we were able to import a new module into our app to help turn a list of binary digits (1 or 0) into real numbers:
import Binary
fromBitsToDecimal : List Int -> Int
fromBitsToDecimal bits =
bits
|> Binary.fromIntegers
|> Binary.toDecimal
fromBitsToDecimal [ 0, 0, 0 ] == 0
fromBitsToDecimal [ 0, 1, 0 ] == 2
fromBitsToDecimal [ 1, 0, 1 ] == 5
This was a huge help for solving the problem– and it allowed us to pass in binary digits without needing to convert them to a decimal number by hand. Shout out to Steven (@icidasset on GitHub) for their wonderful package!
Day 4
Naturally, day four involved helping a squid win bingo, which is definitely a problem we have all experienced in our day-to-day lives. This required us to take a string like this:
rawInput : String
rawInput =
"""
25 10 7 4 15
6 14 3 11 16
19 21 17 2 1
5 18 24 9 8
22 13 23 20 12
"""
And convert this into a bingo board. As numbers are called out one-by-one, we needed something to be able to mark tiles on our board. After marking a number, we also needed to check if our board was a winner or not.
I enjoyed recording this video, because it was a great example for how to create your own data structure in Elm. The core language comes with generic things like List, Array, Set, Dict– but we designed our own Board type to make it easy to mark numbers and check for a win:
-- Stores the mapping of values to coordinates,
-- and which numbers have been marked so far
type alias Board =
{ dict : Dict Int Coordinate
, marked : Set Int
}
-- A coordinate on the board
type alias Coordinate =
{ x : Int
, y : Int
}
-- Creates a board from raw input above
fromString : String -> Board
-- Marks a number on our board
markNumber : Int -> Board -> Board
-- Returns `True` if we have 5-in-a-row!
isWinner : Board -> Bool
Both Dict and Set support an easy way to insert values. Dict.insert was great for implementing the toString function– because we could add squares as we looped through the raw text input.
Set.insert came in handy when implementing markNumber, which was a breeze to implement:
-- Marks a number on our board
markNumber : Int -> Board -> Board
markNumber number board =
{ board | marked = Set.insert number board.marked }
Day 5
Day five had us take a start and end position for a line, and generate a list of all the coordinates that line passed through. For example:
getCoordinates : String -> List ( Int, Int )
getCoordinates "0,1->0,1" == [ ( 0, 1 ) ]
getCoordinates "0,1->0,2" == [ ( 0, 1 ), ( 0, 2 ) ]
getCoordinates "0,1->0,3" == [ ( 0, 1 ), ( 0, 2 ), ( 0, 3 ) ]
At first, the problem told us to ignore diagonal lines and only worry about horizontal and vertical ones. Due to my incredible ability to be a paranoid, I was able to predict that part 2 would make us handle diagonals, which saved me a bit of time. Impressed?
We wrote a series of functions to transform the raw string into a list of coordinates. The interesting stuff was in expanding a start/end coordinate into a list like this:
toCoordinateList :
{ start : ( Int, Int )
, end : ( Int, Int )
}
-> List ( Int, Int )
toCoordinateList { start, end } =
if start.x == end.x then
-- loop from start.y to end.y
range start.y end.y
|> List.map (\y -> ( start.x, y ))
else if start.y == end.y then
-- loop from start.x to end.x
range start.x end.x
|> List.map (\x -> ( x, start.y ))
else
-- delegate diagnonals to another function
handleDiagonals start
Creating the handleDiagonals function was cool, because we had to determine the right direction to loop through. Here, I’d recommend watching the actual video– it does a better job of walking through the process than reading a big wall of blog post paragraphs.
Day 6
Performance matters in day six– and the cost of the naive approach bites me in the butt. This problem involved simulating a fish population as it exponentially grows. My initial design created thousands of lists from scratch over and over again.
This was enough to get me through part one, but when attempting part two I froze up my web browser!
To give some context to the problem, each fish ages by decrementing a number. They continue decrementing until they reach “age 0”, at which point they “give birth”. When a fish gives birth, it creates a new “baby fish” at age 8, and resets its own age to 6.
For the problem input, we have the fish ages are represented like this:
[ 0, 2, 2, 5, 6 ]
My first approach mapped through each age and returned either a list containing the new ages it would create:
simulate 0 == [ 6, 8 ]
simulate 2 == [ 1 ]
simulate 2 == [ 1 ]
simulate 5 == [ 4 ]
simulate 6 == [ 5 ]
The resulting lists would be merged together with List.concat to get the new fish population:
[ 6, 8, 1, 1, 4, 5 ]
As you can imagine, as we get thousands and thousands of fish, this list grows with it. That’s a lot of memory! The big realization in the video was when we started storing fish with a Dict this:
-- Represents how many fish are a certain age
fishAges : Dict Age Count
fishAges =
Dict.fromList
[ ( 6, 1 )
, ( 8, 1 )
, ( 1, 2 )
, ( 4, 1 )
, ( 5, 1 )
]
Now, we only have a maximum of 8 items in our list, because fish never age beyond that number. This led to a huge performance increase and we were suddenly able to run the calculation for millions of baby fish without exploding!
Day 7
Ah, the last video. And naturally it involved crabs shooting lasers. This problem involved crabs finding the easiest way for the crabs to line up with one another.
There were a few cool functions we had to implement, but I enjoyed being able to using List.foldl to track of the cheapest square was:
maybeCheapestPosition : Maybe Cost
maybeCheapestPosition =
[ ( 1, 35 )
, ( 2, 50 )
, ( 3, 15 )
]
|> List.foldl findMinimumPosition Nothing
findMinimumPosition :
( Position, Cost )
-> Maybe Cost
-> Maybe Cost
findMinimumPosition ( position, cost ) maybeCheapestCost =
case maybeCheapestCost of
Just cheapestCostSoFar ->
if cost < cheapestCostSoFar then
Just cost
else
maybeCheapestCost
Nothing ->
Just cost
The code above loops through each item in the list, and holds onto the minimum. cost. In this example, the minimum is position 3 with a cost of 15.
Hindsight is 2022?
After writing this blog post, I realized this fancy findMinimumPosition was completely unnecessary.
I totally could have used the built-in List.minimum function for this problem instead. Here is what that changed would look like:
-- BEFORE
maybeCheapestPosition : Maybe Cost
maybeCheapestPosition =
[ ( 1, 35 )
, ( 2, 50 )
, ( 3, 15 )
]
|> List.foldl findMinimumPosition Nothing
-- AFTER
maybeCheapestPosition : Maybe Cost
maybeCheapestPosition =
[ ( 1, 35 )
, ( 2, 50 )
, ( 3, 15 )
]
|> List.map Tuple.second
|> List.minimum
Using Tuple.second discards the first element of the tuple, so we can call `List.minimum on the costs directly. Whichever approach you prefer, we will get the same answer for either example.
That’s a wrap!
Hope you had a good time learning more about Elm through these Advent of Code videos. I had a blast making them, but mostly because of those YouTube thumbnails.
It turns out you just have to take ~12 pictures of yourself looking surprised and slap a vibrant gradient on that thing and you’re all set. Pair it with some clickbait-ish title like “Day 8 ruined my marriage!” and you’re on the road to fame and glory.
If you’d like to watch the series from start to finish, I’ve put together a playlist for you below. Thanks for taking the time to stop by, and I hope you have a happy new year!