That time of year again, it’s time for Advent of Code. Again I will be writing my solutions in Common Lisp and writing about them here.
For the first part you are given a bunch of lines containing letters and numbers. Each line will always contain at least one digit. For each line we have to combine the digit that appears first (the leftmost digit) with the digit that appears last (the rightmost digit) into a single number, and then sum all these numbers together over each line. Not too bad, I used the following simple loop:
(loop for line in (read-from-file filename)
for digits = (mapcar #'digit-char-p (remove-if-not #'digit-char-p (coerce line 'list)))
for ldigit = (first digits) and rdigit = (first (last digits))
sum (+ (* 10 ldigit) rdigit))
Now for the second part it turns out that each line contains descriptions of digits, where this description can either be the digit itself or the word, i.e., “one”, “two”, “three”, etc.
Again we have to combine the leftmost digit with the rightmost in each line and sum these together.
I defined an association list mapping strings to numerical values, so for example values["six"] == values["6"] == 6, and then for each line I checked if each digit description (“one”, “1”, “two”, “2”, “three”, “3”, …) appeared in the line.
Something that caught me out was that (search digit-description line) only return the index of the first match in the line, meaning descriptions that appeared multiple times in the same line were being ignored, which was important to find the rightmost description in the line.
I fixed this by simply searching, for each line, the original line for the earliest description of a digit to obtain the leftmost digit, and then reversing the line and searching for the reversal of each number description to obtain the rightmost digit.
Here is the code.
It uses search-leftmost-description to find the leftmost digit description, and search-rightmost-description is implemented by simply reversing the line and descriptions parameters and calling search-leftmost-description.
We are then left with a string description for a number, which we convert to a number using the helper function description->digit, which simply uses the association list (dictionary) to convert a string description to a number.
(let ((descriptions '("one" "two" "three" "four" "five" "six" "seven" "eight" "nine" "1" "2" "3" "4" "5" "6" "7" "8" "9")))
(loop for line in (read-from-file filename)
for ldigit = (description->digit (search-leftmost-description line descriptions))
for rdigit = (description->digit (reverse (search-rightmost-description line descriptions)))
for number = (+ (* 10 ldigit) rdigit)
sum number))
Today’s puzzle has us talking to an elf that is pulling some coloured balls out a bag.
The balls can be red, green, or blue, and the puzzle’s input details how many balls of each colour the elf pulls out each round for a number of rounds.
The elf wants to know which rounds would have been possible if the bag contained only 12 red, 13 green, and 14 blue balls to begin with.
Here, a game is possible if the number of balls of each colour that are pulled out of the bag in a round never exceed the number of balls in the bag (12 for red, 13 for green, 14 for blue).
The approach is simple, just iterate over the rounds and check which games are possible.
I first wrote a helper function (subgame-total-color-balls subgame color) which counts the number of colour balls in subgame.
Really this just hides an association list access, where the value associated with a given key color is the number of balls of type color removed from the bag in the given round of the game.
I then used this to write another helper function (game-possible-for-color-p subgames color totals) which simply checks that for each round in a game the number of color balls removed from the bag does not exceed the maximum in totals.
(defun game-possible-for-color-p (subgames color totals)
(every (lambda (subgame)
(<= (subgame-total-color-balls subgame color)
(subgame-total-color-balls totals color)))
subgames))
Then it is simply a case of going over each game and checking that the game is possible for each colour ball. The final answer is to sum the game ID for each game that is possible for all colours.
(loop with totals = '(("red" . 12) ("green" . 13) ("blue" . 14))
with colors = '("red" "green" "blue")
for line in (read-from-file filename)
for subgames = (mapcar #'parse-subgame (ppcre:split ";" line))
for i from 1
if (every (lambda (color) (game-possible-for-color-p subgames color totals)) colors)
sum i)
For the second part we want to find the minimum number of balls required of each colour that would make each game possible. To tackle this we can simply take the maximum number of balls removed taken out of the bag for each colour (since we know we need at least this many balls in the bag of this colour for the game to be possible). As per the puzzle we then have to multiply these minimums together for each colour per game and sum the resulting value over all games given in the input.
(loop with colors = '("red" "green" "blue")
for line in (read-from-file filename)
for subgames = (mapcar #'parse-subgame (ppcre:split ";" line))
for minimums = (mapcar (lambda (color)
(reduce #'max (mapcar (lambda (subgame)
(subgame-total-color-balls subgame color))
subgames)))
colors)
sum (reduce #'* minimums))
I faffed about on this with the helper functions but hopefully it ended up in slightly more readable code.
I learned that using (assoc key alist) to access the value corresponding to the key in the association list will return the entire entry/dotted pair upon success, so to get the actual value you have to use (rest (assoc key alist)), which tripped me up a few times.
Today we are trying to break distance records in boats. Our boat has a button that we may press to chareg up the motors, and once we release the button we will be propelled forward at a speed proportional to the amount of time that we held the button for. Each race lasts a specific duration and has with it an associated distance. Our goal is to determine the amount of time to hold down the button in order to break the distance record for the race, given its duration. It turns out that for every second we hold the button the speed at which we are propelled upon its release increases by one unit, and note that we only move once we release the button. The first part of the puzzle asks, for each race: how many ways are there for us to hold down the button that will result in a record-breaking distance?
Focus on some given race with duration \(\delta\) and distance record \(r\). Let \(t\) denote the amount of time that we hold down the boat’s button. The total distance we travel will be equal to our final speed \(v\) multiplied by the time remaining (since we do not move while holding the button), which is given by \((\delta - t)\). Since our final speed is equal to the amount of time we hold the button down for then our distance travelled given \(t\) can be written as \(f(t) = t (\delta - t)\).
Denote the distance record of this race by \(r\). We therefore wish to find all integer values of \(t\) with \(0 \le t \le \delta\) such that \(f(t) > r\). We can start by finding a value \(t^*\) that maximises \(f\) by finding where the gradient of \(f\) is zero. Differentiating \(f\) we have \(f'(t) = \delta - 2t\), and setting this to zero we get \(t^* = \delta / 2\). In words, this means we hold down the button for half the race’s duration. We can then count the number of ways to break the record by incrementing and decrementing \(t^*\) by 1 unit until the distance travelled using this value of \(t\) falls below \(r\). This is done with the following loop.
(defun number-of-feasible-solutions (duration record)
(flet ((distance-travelled (time)
(* time (- duration time))))
(loop with t* = (floor duration 2)
for i from 1
for t- = (- t* i) and t+ = (+ t* i)
for d- = (distance-travelled t-) and d+ = (distance-travelled t+)
count (> d- record) into left
count (> d+ record) into right
until (and (<= d- record) (<= d+ record))
finally (return (+ left right 1)))))
This suffices to solve both parts of the day’s puzzle. There is a more analytical solution which worked for the first part but failed on the second, I imagine due to rounding errors. Since the function \(f(t) = t (\delta - t)\) is quadratic the equation \(f(t) = r\) will have (at most) two roots, and these roots will correspond to values of \(t\) for which we can hold the button and equal the distance record.
Let \(t_1,t_2\) be the roots of the equation \(t^2 - \delta t + r\) and let \(t_1 \le t_2\). These roots are given by \(t_1, t_2 = \frac{1}{2} (\delta \pm \sqrt{\delta^2 - 4r})\). If \(t_1\) and \(t_2\) are both integers then the number of integers strictly between \(t_1\) and \(t_2\) is given by \(1 + (t_2-1) - (t_1 + 1) = t_2 - t_1 - 1\). Now if either root is not an integer then for \(t_1\) we want to take the smallest integer that is strictly larger than \(t_1\) and for \(t_2\) we want to take the largest integer that is strictly less than \(t_2\). For the former we can take \(\lfloor t_1 \rfloor + 1\) and for the latter we take \(\lceil t_2 \rceil - 1\), and verify that this gives the correct value of \(t\) when \(t_1\) and \(t_2\) are integers. The number of integers strictly between these two roots is therefore given by \(\lceil t_2 \rceil - \lfloor t_1 \rfloor - 1\), which is our final answer.
As I’ve said, this worked for part one but got an answer which was slightly too low for part two, so probably had some issues to do with rounding errors.