I did the Advent of Code this year using Common Lisp. Last year I attempted to use the series library as the primary iteration mechanism to see how it went. This year, I just wrote straightforward Common Lisp. It would be super boring to walk through the solutions in detail, so I’ve decided to just give some highlights here.

Day 2: Repeating Strings

Day 2 is easily dealt with using the Common Lisp sequence manipulation functions giving special consideration to the index arguments. Part 1 is a simple comparison of two halves of a string. We compare the string to itself, but with different start and end points:

(defun double-string? (s)
(let ((l (length s)))
(multiple-value-bind (mid rem) (floor l 2)
(and (zerop rem)
(string= s s
:start1 0 :end1 mid
:start2 mid :end2 l)))))

Part 2 asks us to find strings which are made up of some substring repeated multiple times.

(defun repeating-string? (s)
(search s (concatenate 'string s s)
:start2 1
:end2 (- (* (length s) 2) 1)
:test #'string=))

Day 3: Choosing digits

Day 3 has us maximizing a number by choosing a set of digits where we cannot change the relative position of the digits. A greed algorithm works well here. Assume we have already chosen some digits and are now looking to choose the next digit. We accumulate the digit on the right. Now if we have too many digits, we discard one. We choose to discard whatever digit gives us the maximum resulting value.

(defun omit-one-digit (n)
(map 'list #'digit-list->number (removals (number->digit-list n))))

> (omit-one-digit 314159)
(14159 34159 31159 31459 31419 31415)

(defun best-n (i digit-count)
(fold-left (lambda (answer digit)
(let ((next (+ (* answer 10) digit)))
(if (> next (expt 10 digit-count))
(fold-left #'max most-negative-fixnum (omit-one-digit next))
next)))
0
(number->digit-list i)))

(defun part-1 ()
(collect-sum
(map-fn 'integer (lambda (i) (best-n i 2))
(scan-file (input-pathname) #'read))))

(defun part-2 ()
(collect-sum
(map-fn 'integer (lambda (i) (best-n i 12))
(scan-file (input-pathname) #'read))))

Day 6: Columns of digits

Day 6 has us manipulating columns of digits. If you have a list of columns, you can transpose it to a list of rows using this one liner:

(defun transpose (matrix)
(apply #'map 'list #'list matrix))

Days 8 and 10: Memoizing

Day 8 has us counting paths through a beam splitter apparatus while Day 10 has us counting paths through a directed graph. Both problems are easily solved using a depth-first recursion, but the number of solutions grows exponentially and soon takes too long for the machine to return an answer. If you memoize the function, however, it completes in no time at all.