Here’s my writeup for this year’s Advent of Code. I’ve decided to put this all in one big long post instead of splitting it up, and it’s still a work in progress and will get added to as I complete more of the puzzles. You can find the repository for the code on my Github and I tackled the problems in Common Lisp.
The first part of today’s puzzle required counting the number of times an entry in a list of numbers was greater than the one before.
This was done pretty painlessly using the loop construct (which I feel I am only just using properly).
It simply sets b to the current list item, a to the previous item (and nil to begin with), then for every item but the first compares b with a.
I like the count clause, which counts the number of times the expression that follows is true.
(defun advent-01a (filename)
(loop with input = (mapcar #'parse-integer (get-file filename))
for a = nil then b
for b in input
when a
count (> b a)))
Part two was a slight modification of the previous part: now we had to keep track of a sliding window of size three and count the number of times the sum of the elements in the window exceeded the sum of the elements in the previous window.
Only a few changes were required to the code, and the on clause was very useful for assigning and working with the elements of the sliding window.
(defun advent-01b (filename)
(loop with input = (mapcar #'parse-integer (get-file filename))
for (a b c) on input
while (and a b c)
for prev-sum = nil then sum
for sum = (+ a b c)
when prev-sum
count (> sum prev-sum)))
One generalisation that could be made is the size of the sliding window, though it’s not immediately obvious how to change for (a b c) in input to reflect this.
I guess you could do this using macros, but I’m still not good enough at writing them to work it out.
Yesterday the input was the depth readings from our submarine’s sonar and we had to determine the changes in the underwater landscape in order to safely navigate it. With that done today’s puzzle has us following the route programmed into the submarine’s systems.
The input for the puzzle consists of a number of lines of the form (direction x) telling us how to move the submarine, where direction can be one of up, down, or forward and x is the number of units to move.
The first part is simply a case of starting at (0,0) and following the directions, where forward increases our horizontal position, and down and up increase and decrease our depth, respectively.
(defun advent-02a (filename)
(loop for (dir dst) in (mapcar #'str:words (get-file filename))
for direction = (read-from-string dir)
for distance = (parse-integer dst)
with (x y) = '(0 0)
do (case direction
(forward (incf x distance))
(down (incf y distance))
(up (decf y distance)))
finally (return (* x y))))
The second part again only entailed a slight modification: now we have a third value aim to keep track of and the movement rules are slightly different.
up and down now modify aim, and forward both increases our horizontal position and increases our depth by aim multiplied by x.
(defun advent-02b (filename)
(loop for (dir dst) in (mapcar #'str:words (get-file filename))
for direction = (read-from-string dir)
for distance = (parse-integer dst)
with (x y aim) = '(0 0 0)
do (case direction
(forward (incf x distance)
(incf y (* aim distance)))
(down (incf aim distance))
(up (decf aim distance)))
finally (return (* x y))))
I like the read-from-string function which converts a string into a symbol, because it means you can effectively get a switch statement for strings without numerous calls to, for example, string=.
I believe it’s also quicker to compare two symbols for equality than to compare two strings, so even though the difference is probably insignificant it does feel a bit nicer.
Two simple loops, two stars.
Looks like the submarine is making some concerning noises and we have to write some code to figure out what’s wrong with it.
We are provided with the input as a list of bitstrings that represents the submarine’s diagnostic report.
For the first part we are building up a bitstring, call it gamma, using the most common bit at each index.
That is, for each index from 0 up to the length of the input bitstrings, we must find the most common bit (0 or 1) and then write it at that index in gamma.
Nothing too hairy in this loop and there are no hidden tricks: it was useful to use a lambda in order to collect all of the bits at a given index and then pass them to Lisp’s count function.
I also considered at first using gamma as a list, then at each iteration pushing the most common bit to this list, though this would have entailed an extra reversal (since push would mean elements are stored in the reverse order) as well as a conversion from list to number.
Instead, gamma is considered a number from the get-go and at each iteration, depending on whether we found 0 or 1 to be most common at the current index, we either left-shift it once (to “write a zero” to the bitstring) or left-shift it once and add 1 (to “write a one” to the bitstring).
The answer to the puzzle was then the product of gamma and epsilon, where epsilon was obtained in exactly the same way except by finding the least common bit at each index.
Instead of executing the same loop again and flipping the inequality, this could be found from gamma by just flipping its bits.
Unfortunately I couldn’t just call (lognot gamma) since this was resulting in negative numbers,1 so instead it was found with an XOR between gamma and a bitstring of all 1s, or \(2^n-1\) where \(n\) is the number of bits in gamma (simply the length of bitstrings given in the input).
(loop with input = (get-file filename)
with n = (length (first input))
with m = (length input)
for i from 0 below n
with gamma = 0
for zeroes = (count #\0 (mapcar (lambda (bitstring) (char bitstring i)) input))
do (setf gamma (if (>= zeroes (/ m 2)) (ash gamma 1) (1+ (ash gamma 1))))
finally (return (* gamma (logxor (1- (expt 2 n)) gamma))))
Part two was a bit more complex.
We have to find two bitstrings, generator and scrubber, by successively filtering out bitstrings in the input that do not meet certain criteria.
For generator, for each index we must find the most common bit among all remaining candidates (breaking ties in favour of 1) then filter out those without that bit at that index.
For scrubber, we do the same but for the least common bit and break ties in favour of 0.
Although simple to sate, I found it took a fair bit of code to implement the first time around as I was performing the filtering for generator and scrubber all within the same loop, which meant I had to keep track of separate variables for each.
While this worked, I figured I could do better.
Since the rules for filtering out candidates for the two bitstrings differed only slightly, I decided to write a function (filter-candidates candidates filter-rule) that took a list of candidate bitstrings and repeatedly applied the function filter-rule to remove invalid elements.
Note that in the code snippet below I also use a function nth-char=, which simply determines whether the nth char of the given string is equal to the given character.
(labels ((nth-char= (string n character) ...)
(filter-candidates (candidates filter-rule)
(loop for i from 0 below (length (first candidates))
with remaining = candidates
for zeroes = (count #\0 (mapcar (lambda (bitstring) (char bitstring i)) remaining))
for ones = (- (length remaining) zeroes)
for char = (funcall filter-rule zeroes ones)
until (= 1 (length remaining))
do (setf remaining (remove-if-not (lambda (bitstring) (nth-char= bitstring i char)) remaining))
finally (return (first remaining)))))
filter-rule is a function that takes two numbers and decides whether to return the character 0 or 1.
This is then run at each iteration to determine which character we would filter the remaining candidates on (i.e., whether to look for a 0 or a 1 at the current index under consideration).
For generator this was the rule specifying that, if the number of zeroes at the given index exceeds the number of ones then we remove all candidates without a 0 at the given index; for scrubber we remove all candidates without a 1 at the given index if the number of ones exceeds the number of zeroes.
Actually filtering out all the invalid candidates is then simply a case of calling filter-candidates on the puzzle input, once for generator and once for scrubber, and a lambda function corresponding to the appropriate rule:
;; filter out invalid bitstrings for generator
(filter-candidates input (lambda (zeroes ones) (if (> zeroes ones) #\0 #\1)))
;; filter out invalid bitstrings for scrubber
(filter-candidates input (lambda (zeroes ones) (if (<= zeroes ones) #\0 #\1)))
As I mentioned, I ended up taking two attempts at this.
The first one completed the puzzle in a single loop but required extra variables to keep track of generator and scrubber candidates separately, and ended up reusing a lot of the code.
I’m much happier with my second attempt since it makes the solution more generic and about ten lines more concise.
I was also pleased to make use of higher-order functions since it isn’t something I use often and it always feels powerful when it works.
I already spent quite a bit more time on today’s puzzles than the previous two days, so I’m preparing for the steady increase in difficulty and inevitable loss of more time as the month progresses.
Having successfully deciphered the submarine’s esoteric diagnostic reports, we now find ourselves in the situation that a giant squid has attached itself to us. It is now our job to program the submarine’s bingo subsystem to win a game against the squid.
This puzzle required a lot of parsing code, or at least a fair bit more than I had used for the previous days’ puzzles.
I chose to represent a bingo card as a two-dimensional matrix in which each entry was a list containing the number in the bingo card cell and a marker that signifies whether the number has been called.2 These are all stored in the list bingo-cards.
The first part is then as simple as iterating over the numbers, marking the appropriate cards, and returning the first winning card found.
In the snippets below, mark-card simply sets the marker for the given number to t in the given card, while card-wins-p is a function that checks whether the given card has a whole line of numbers marked t.
(let (winning-card final-number)
(loop for number in numbers
do (loop for card in bingo-cards
do (mark-card number card)
if (card-wins-p card)
do (setf winning-card card
final-number number))
until winning-card)
(* (card-value winning-card) final-number))
The second part gets us to reverse our strategy against the squid and find the last bingo card to win, and finally find the last number to be called that would complete it. This only requires a slight change to the logic from the first part, and we can use all of the same functions already defined for the first part. Now, instead of looping over all cards until we find a winning one, we instead loop over all cards that have not won yet, removing newly-winning ones as we discover them.
(loop for number in numbers
with remaining-cards = (reverse bingo-cards)
do (loop for card in remaining-cards
do (mark-card number card)
(setf remaining-numbers (rest numbers))
unless (card-wins-p card)
collect card into next-remaining-cards
finally (setf remaining-cards next-remaining-cards))
until (= 1 (length remaining-cards))
finally (setf last-winning-card (first remaining-cards)))
Once the list containing the remaining non-winning cards reaches length one, we know we have found the last card to win and we can go about finding the number it will win on. To do so, we iterate over the remaining numbers in our input and simply mark the card until it is winning.
(loop for number in remaining-numbers
do (mark-card number last-winning-card)
until (card-wins-p last-winning-card)
finally (return (* (card-value last-winning-card) number)))
The hardest part about today’s puzzle was probably the parsing code, which I found I ran into trouble with a fair bit using the loop constructs that I did.
I find using Lisp’s language for loop is fine for single loops, but it becomes a bit cumbersome to structure the code to accurately carry out what you mean when you start nesting them.
No doubt this is because I am still getting accustomed to this mini DSL but nonetheless it did increase time spent debugging significantly.
Sometimes it is quite nice for a puzzle to have no hidden tricks, for there just to be a clearly defined problem and for it to just be about automating the process to solve it, and that was what Day 4 felt like.
I feel the code could be cleaned up and perhaps made more concise, but I’ll leave that until later now.
Having dealt with the lanternfish we now set to work to escape a potentially grisly encounter with a whale. For various plot reasons we have to align a collection of crab submarines – which can obviously only move horizontally – onto a single point. The submarines incur a cost for moving from its starting position to the alignment point, so we want to find such a point that minimises the total cost incurred by the crabs. I found the two problems easy to solve but noticed afterwards there were certainly better (more efficient) ways to solve them.
Our puzzle’s input is a list \(x_1,\ldots,x_n\) of the crab submarines’ (integer) starting positions. We want to find a point \(y\) on which to align the crabs, and on placing the alignment point at \(y\) crab \(i\) will incur a cost \(c_i(x_i,y)\) to move from his starting position \(x_i\) to that point. For both parts we want to find an optimal alignment point \(y^* \in \arg \min_y c(y)\), where \(c(y)\) denotes the cost of placing the alignment point at \(y\). In our case we have \(c(y) = \sum_i c_i(x_i,y)\), but this could equally have been the maximum distance a crab has to move, or the average distance, etc.
Part One. For the first part we are told that each crab incurs the cost \(c_i(x_i,y) = \| x_i-y \|\) for placing the point at \(y\), i.e., the absolute distance he must move from his starting position to the alignment point. Clearly \(y^*\) must lie between the leftmost crab position \(x_\min\) and the rightmost \(x_\max\). To find \(y^*\) we could therefore just iterate over all possible alignment positions between \(x_\min\) and \(x_\max\), keeping track of the lowest resulting cost as we go. There is however a better way.
Claim: Any point \(y \in [m_1,m_2]\), where \(m_1,m_2\) are the median crab position(s) in the input, is an optimal alignment point.
Proof: Note that placing the point at \(m_1\) or \(m_2\) results in the same cost. If \(n\) is odd since then there is only one median point, i.e., \(m_1 = m_2\), so suppose \(n\) is even. Let \(c_L(y)\) denote the sum of costs of all points in the input less than \(y\), and \(c_R(y)\) denote the sum of costs of all points greater than \(y\). The cost of aligning at \(y\) is \(c(y)=c_L(y)+c_R(y)\), and we want to show \(c(m_1)=c(m_2)\). Since \(m_1\) and \(m_2\) are both median points and \(n\) is even then the number of points to the left of \(m_1\) is equal to the number of points to the right of \(m_2\), and this is \(n/2\). Therefore, the cost for all points left of \(m_2\) of placing the alignment point at \(m_2\) is equal to the cost of placing it at \(m_1\) plus \(\frac{n}{2}\) times the distance between \(m_1\) and \(m_2\), or:
\[c_L(m_2) = c_L(m_1) + \frac{n}{2}(m_2-m_1)\]Similarly we may rewrite \(c_R(m_2)\) as \(c_R(m_1) - \frac{n}{2}(m_2-m_1)\) and thus we get the cost of placing the alignment point at \(m_2\) as:
\[\begin{align} c(m_2) & = c_L(m_2) + c_R(m_2) \\ & = c_L(m_1) + \frac{n}{2}(m_2-m_1) + c_R(m_1) - \frac{n}{2}(m_2-m_1) \\ & = c_L(m_1) + c_R(m_1) \\ & = c(m_1) \end{align}\]It turns out that placing the alignment point \(y\) anywhere in the interval \([m_1,m_2]\) has the same cost as placing it at either median point. Performing the same trick as before, for any \(y \in [m_1,m_2]\):
\[\begin{align} c(y) & = c_L(y) + c_R(y) \\ & = c_L(m_1) + \frac{n}{2}(y-m_1) + c_R(m_1) - \frac{n}{2}(m_2-y) \\ & = c(m_1) \end{align}\]It remains to show that \(c(y)\) is optimal for any \(y \in [m_1,m_2]\). Suppose for the sake of contradiction that \(y\) is an optimal alignment point outside of the interval \([m_1,m_2]\) and assume \(y > m_2\). The cost of aligning at \(y\) is:
\[\begin{align} c(y) & = c(m_2) + (1 + \frac{n}{2})(y-m_2) - \frac{n}{2}(y-m_2) \\ & = c(m_2)+(y-m_2) \\ & > c(m_2) \end{align}\]So placing the alignment point outside the interval \([m_1,m_2]\) results in a strictly larger total cost than placing it at \(m_2\), contradicting our assumption. We arrive at the same conclusion if we assume \(y < m_1\). Thus any point \(y \in [m_1,m_2]\) is optimal.
(flet ((total-cost (position numbers)
"Sum of absolute differences between POSITION and NUMBERS"
(loop for n in numbers
sum (abs (- position n)))))
(let* ((input (get-numbers filename))
(y (median input)))
(total-cost y input)))
The entire code for the first part given above. When using the median we instead take time \(O(n \log n)\), since this is the time required to order the list and find the median, followed by a single calculation of the total resulting cost.
Part Two. The second part changed the crabs’ cost functions, so instead of being the absolute difference between \(y\) and \(x_i\) it was now 1 if the crab was 1 away from \(y\), 1+2 if the crab was 2 away from \(y\), 1+2+3 if it was 3 away from \(y\), and so on. In other words, with \(d=|x_i-y|\), when placing the alignment point at \(y\) each crab \(i\) now incurs the cost:
\[c_i(x_i,y) = \sum_{k=1}^d k = \frac{d(d+1)}{2}\]I currently don’t have a better solution than the brute force one – that is, try all possible positions between the minimum and maximum starting position and return the one that results in the smallest total cost. The code implementing this is given below:
(flet ((total-cost (position numbers)
(loop for n in numbers
for difference = (abs (- position n))
sum (/ (* difference (1+ difference)) 2))))
(loop with input = (get-numbers filename)
for i from (reduce #'min input) upto (reduce #'max input)
minimize (total-cost i input)))
There is probably a better solution out there, and it’s probably been documented to death on the subreddit, but I refuse to look before I’ve had a longer think.