Advent of Code 2024

For the first day, I'll be using the good programming language, Common Lisp. Almost every code block is primarily a call to the LOOP macro, which implements a really impressive iteration DSL.

Part 1

The task is to go through two lists of integers simultaneously in order of their smallest elements to their largest, summing the absolute values of their differences. The input lists are in a random order. The problem doesn't say anything about what to do if the lists are not the same length, but the input is two lists of equal length.

The heart of it is implemented very simply by sorting both lists and then looping over both at once to sum the differences:

(defun list-difference (list1 list2)
  (loop for x in (sort list1 #'<)
        for y in (sort list2 #'<)
        summing (abs (- x y))))

Next, we can define an input routine that returns a list containing the two lists we're supposed to compare:

(defun read-lists (filespec)
  (with-open-file (input filespec)
    (loop for x = (read input nil)
          for y = (read input nil)
          while (and x y)
          collect x into list1
          collect y into list2
          finally (return (list list1 list2)))))

And finally, we can glue them together to get the answer. Because READ-LISTS returns a list of values, and we want to pass that list in that order to LIST-DIFFERENCE, we can just combine them with APPLY:

(print (apply #'list-difference (read-lists "input.txt")))

Part 2

For the second task, we need to compute the similarity differently. We get the similarity score by summing the products of each unique element in the first list and the number of times it appears in the second list.

This seems easy to implement by using a hash table to track which elements in the first list have been seen. Then we can just loop over the second list and sum the elements that were seen in the first list. This involves a linear read of both lists and constant-time hash table operations, so it's O(n) overall.

We can start with making a set out of the first list and including a simple predicate for checking membership:

(defun membership-set (list)
  (loop with seen = (make-hash-table)
        for element in list do
          (setf (gethash element seen) t)
        finally (return seen)))

(defun seenp (item membership-set)
  (gethash item membership-set))

Another simple LOOP call is all we need to calculate similarity:

(defun similarity (list1 list2)
  (loop with list1-items = (membership-set list1)
        for element in list2
        if (seenp element list1-items)
          sum element))

READ-LISTS doesn't need any changes, so all we need to do now is use it to apply SIMILARITY to the input lists:

(print (apply #'similarity (read-lists "input.txt")))