Advent of Code, Day Two2018-12-10
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.
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 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
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
(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.
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