Advent of Code, Day Two

Yikes! I am getting severely behind on my Advent of Code "puzzle-a-day" challenges. I've just wrapped up puzzle number two on day 10! This one will be brief.

Part One

The First challenge is not entirely unlike day one, search a list of something for "alike" items. The "likeness" is the one complicating factor so far, so we can largely re-use a read function, slurping up all of the input into a single long list:

(defun read-lines (filename)
  "read lines as some lisp-y thing"
  (with-open-file (stream filename)
    (loop for line = (read-line stream nil)
       while line
       collect line)))

In order to count those list elements for which a member character appears two or three times I return to a hashing-based solution, this time actually using a bit more of the built-in hash-tables.

(defun count-chars (str)
  (let ((character-map (make-hash-table)))
    (loop for c across str
       do (incf (gethash c character-map 0)))
    (list
     (loop for k being the hash-keys in character-map using (hash-value v)
        when (equal v 2) collect k)
     (loop for k being the hash-keys in character-map using (hash-value v)
        when (equal v 3) collect k))))

I think there is the potential to eliminate the second loop in order to test only once, rather than once for twos and again for threes, but I'm falling behind here! This is working to collect strings appropriately. The next step is to do so for all of the strings in the input file:

(defun aggregate (lines)
  (loop for line in lines
     collect (count-chars line)))

In retrospect I think this is needless and could be factored it into a top-level loop in the count-chars function with a bit more thought. But with it, I've got a list of twos and threes that can be check-summed with a bit of arithmetic:

(defun checksum (filename)
  (loop for (twos threes) in (aggregate (read-lines filename))
     counting twos into -twos
     counting threes into -threes
     finally (return (* -twos -threes))))

Part Two

Part two was a more interesting problem to me than several of the others. I'm not sure if it simply easier but I didn't suffer any serious performance issues like day one. The goal is to find the strings that differ by only one character, so for me the obvious first step is to define a function to count the differences between two strings:

(defun differences (string1 string2)
  (let ((counter 0))
    (loop for char across string1 and index from 0
       do
         (if (not (equal char (aref string2 index)))
             (incf counter)))
    (list counter string1 string2)))

Once again, more looping! It's pretty straight-forward, although finding an enumerate-like keyword was a nifty thing. I think I could have come up with something better than returning a list of everything, that feels a bit hack-y, though I'm not sure multiple-value returns are the answer either.

Similar to the aggregate function above, I've wrapped the iteration of differences into a list-builder below. The %test function is a helper used later to pick out a pair of strings that have only 1 difference between them. I read somewhere that "private" functions are sometimes denoted with a prefixed %, not sure I agree with that yet.

(defun check-string (candidate inventory)
  (loop for item in inventory
     collect (differences candidate item)))

(defun %test (results)
  (member 1 results :key #'car))

Because there are only 250 strings to check against each other, I simply group each check into batches of the remaining list (250, then 249, 248, etc.) and use the helper function to pick out the right one. I accomplish this recursively with the find-alike function:

(defun find-alike (strings-list)
  (let ((tmp (%test (check-string (car strings-list) (cdr strings-list)))))
    (cond ((null strings-list) nil)
    (tmp (cdar tmp))
    (t (find-alike (cdr strings-list))))))

This is where it starts to really get ugly, the temporary variable is used to hold the return value of the member function, which is really the remainder of the list from the point of the positive/matched "member". To hide that detail, I'm returning cdar, which similarly strips off the leading 1 from the list.

At this point I've got the two "alike" strings and have to strip out the one character that isn't shared between them. Once more, a loop across the strings:

(defun shared-chars (results-list)
  (coerce (loop for c across (first results-list) and index from 0
         if (equal c (aref (second results-list) index))
         collecting c) 'string))

(shared-chars (find-alike (read-lines "input.txt")))

I'm not sure if coercing the looped-list is really very good, any kind of coercion tends to feel like a code smell to me, but it gets the job done — and quickly.

Thoughts

While I'm glad that I can put myself under some pressure and knock a puzzle out quickly if I need to, I'm a little nonplussed with the extent to which I've relied on the loop macro. I think if I continue to do these puzzles I may impose an arbitrary limitation like "no more loop". The chances of my finishing all of these looks pretty slim though.