Solving Advent of Code 2020, days 1-4

The first day was actually asking for the solution of a subset sum problem, or else the problem of finding pairs or triplets of numbers that add up to a certain value. First we parse our input as list:

(defun get-file (filename)
  (with-open-file (stream filename)
    (loop for line = (read-line stream nil)
       while line
       collect line)))

(defvar expenses
  (mapcar #'parse-integer (get-file "input1.txt")))

Then for the first part we think as follows:

1. Put every value as a key to a hash table, with a value t
2. Check recursively if the difference of a list element and the target sum is in the hash table
3. Collect the values that do confirm the check at two.

These can be expressed somewhat like this:

(defun two-sum (list sum)
  (let ((hash (make-hash-table)))
    (loop :for x :in list
          :do (setf (gethash x hash) t))
   (labels ((recur (list acc)
              (if (endp list)
                  acc
                  (let* ((current (car list))
                         (target (- sum current)))
                    (if (gethash target hash)
                        (recur (cdr list) (cons (list target current) acc))
                        (recur (cdr list) acc))))))
     (recur list '()))))

The second problem can't be as easily expressed recursively, so I employed the mighty loop macro. Here the chain of thinking is that we can add the values into a hash table as before and loop for every subset of two elements in order to see whether the difference of the target sum and them exists in the hash table.

(defun three-sum (list sum)
  (let ((hash (make-hash-table)))
    (loop :for x :in list
          :do (setf (gethash x hash) t))
    (loop :named main :for x :in list :do
      (loop :for y :in list :do
        (if (gethash (- sum x y) hash)
            (return-from main `(,x ,y ,(- sum x y))))))))

Since in the problem it was implied that there exists only one such triplet, we omitted to look for the solutions and just return when we find one.

Then we just have to multiply the pair and triplets and to find the solutions. All in all it was a pretty easy day, and a good warm-up for my rusty programming skills.

Day presented the problem of parsing lines in the form of "1-3 a: abvcd". We parse the input as before so not much to say here.

For the first part we had to assume that the first two numbers represent a position, the second a target that must be included in the previous range and the string at the end a password that needs to be validated with this rule. Given the above we have to calculate the number of valid passwords in our input files.

To easily parse this input, we can use regex. In Common Lisp one of the most used regex libraries is cl-ppcre, which supports perl like syntax for them.

Don't try to parse HTML with regex. The results are not worth it.

The regex to match our expression can be written as follows:

(defvar scanner (ppcre:create-scanner "(\\d+)\\-(\\d+)\\s([a-z]\)\:\\s([a-z]+)"))

In essence we create four groups of interest: the two digits divided by the dash, the character before the : and the characters at the end. Now we can write our validators, using the ppcre:register-groups-bind commands, to destrucure the groups.

(defun validate-password-1 (string)
  (ppcre:register-groups-bind ((#'parse-integer start end)
                               ((lambda (x) (coerce x 'character)) target)
                               password)
    (scanner string)
    (let ((count (count target password)))
      (and (>= count start)
           (<= count end)))))

To finally count the valid passwords we just use reduce:

(reduce (lambda (acc x)
          (if (validate-line-1 x)
              (1+ acc)
              acc))
        password-input :initial-value 0)

Part 2 is quite similar. The only change is that we the now we have to check the first two digits (the ones we treated as a position range) as positions for the target character and verify that just one of them has it. So it is just a simple modification of the above validation function and is left as an exercise for the reader 🤣.

This day we had the problem of checking for collisions by movement on map represented by lines like "….#…#..". Each hash represented a tree, so we need to count how many trees we would crash on by following a certain pattern of movement. Another issue is that the lines represented a pattern themselves: they were repeating infinitely to the right.

To solve this problem I first counted the length of the lines, which happened to be 31. This way I could find the correct position by using mod31 arithmetic. Then I defined the following function:

(defun count-collisions (map right down)
  (labels ((iter (list acc pos)
             (if (endp list)
                 acc
                 (if (char= (aref (car list) pos) #\#)
                     (iter (funcall down list) (1+ acc) (rem (+ pos right) line-length))
                     (iter (funcall down list) acc (rem (+ pos right) line-length))))))
    (iter map 0 0)))

It's an recursive function that gets downwards on the list by the speed defined in right and down, ie how many blocks we travel to the right and downwards in each step. Right needs a number, but since downwards is in fact how many lines we skip at each recursion step, it's expressed as a function of the cdr family. With cdr we check each line (1 downwards step), with cddr we check every other line (2 downwards steps) and so on.

To get the solution for the first part I just needed to run (count-collisions my-input 3 #'cdr), and for the second part I just had to calculate the product of several speeds.

Finally at the most recent fourth day (whoa this post took longer than I thought to write), we had to validate imaginary passport data. The data where in blocks of key value pairs separated by :. The problem is that they were not presented in a standard sequence.

This challenge needed different parsing of the file since each block was separated by a blank line and a block could exist in several lines. To have my data better organized I used this function to parse the input:

(defun get-file-per-paragraph (filename)
  (with-open-file (stream filename)
    (loop :for line = (read-line stream nil)
          :while line
          :with temp = ""
          :if (string= line "")
            :collect temp
            :and :do (setf temp "")
          :else
            :do (setf temp (concatenate 'string temp " " line)))))

(defvar passport-tests (get-file-per-paragraph "input4.txt"))

The first part of the problem was to check if all the needed key values where present. To check so we can loop over and search the needed strings. Then we just count the valid ones to get our answer.

(defvar passport-codes '("byr:" "iyr:" "eyr:" "hgt:" "hcl:" "ecl:" "pid:"))

(defun passport-validate (passport-data)
  (not (member nil
               (loop :for code :in passport-codes
                     :collect (search code passport-data)))))

(reduce (lambda (acc x) (if (passport-validate x) (1+ acc) acc))
        passport-tests :initial-value 0)

The second parted wanted us to validate the data according to some rules. To do so I used cl-ppcre again to create patterns of the correct data. Then I wrote several validator functions, one for each kind. It was boring to be honest and reminded me of writing business code: not challenging and repetitive. This left me with the feeling that there might be a better solution to this. If you, kind reader, know of such a solution, please, inform me through any means of contact. Thanks.

The boring but working code is:

(defvar byr-code-scanner (ppcre:create-scanner "byr:(\\d{4})(?:\\s|$)"))
(defun validate-byr (input)
  (ppcre:register-groups-bind ((#'parse-integer value))
      (byr-code-scanner input)
    (and (>= value 1920)
         (<= value 2002))))

(defvar iyr-code-scanner (ppcre:create-scanner "iyr:(\\d{4})(?:\\s|$)"))
(defun validate-iyr (input)
  (ppcre:register-groups-bind ((#'parse-integer value))
      (iyr-code-scanner input)
    (and (>= value 2010)
         (<= value 2020))))

(defvar eyr-code-scanner (ppcre:create-scanner "eyr:(\\d{4})(?:\\s|$)"))
(defun validate-eyr (input)
  (ppcre:register-groups-bind ((#'parse-integer value))
      (eyr-code-scanner input)
    (and (>= value 2020)
         (<= value 2030))))

(defvar hgt-code-scanner (ppcre:create-scanner "hgt:(\\d{2,3})(cm|in)(?:\\s|$)"))
(defun validate-hgt (input)
  (ppcre:register-groups-bind ((#'parse-integer value)
                               type)
      (hgt-code-scanner input)
    (if (string= type "cm")
        (and (>= value 150)
             (<= value 193))
        (and (>= value 59)
             (<= value 76)))))

(defvar hcl-code-scanner (ppcre:create-scanner "hcl:#([0-9a-f]{6})(?:\\s|$)"))
(defun validate-hcl (input)
  (ppcre:scan hcl-code-scanner input))

(defvar ecl-code-scanner (ppcre:create-scanner "ecl:([a-z]{3})(?:\\s|$)"))
(defvar eye-color-codes '("amb" "blu" "brn" "gry" "grn" "hzl" "oth"))
(defun validate-ecl (input)
  (ppcre:register-groups-bind (color)
      (ecl-code-scanner input)
    (member color eye-color-codes :test #'string=)))

(defvar pid-code-scanner (ppcre:create-scanner "pid:(\\d{9})(?:\\s|$)"))
(defun validate-pid (input)
  (ppcre:scan pid-code-scanner input))

(defun passport-validate-2 (passport)
  (and (validate-byr passport)
       (validate-iyr passport)
       (validate-eyr passport)
       (validate-hgt passport)
       (validate-hcl passport)
       (validate-ecl passport)
       (validate-pid passport)))

(reduce (lambda (acc x) (if (passport-validate-2 x) (1+ acc) acc)) passport-tests :initial-value 0)

One thought I had was that, since the validator functions shared a similar pattern, it could be nice to have a generator function for them. The means to abstract them so eluded me, and since this is a challenge that was solved I didn't push too much. I will return though (I hope).

So this is my experience so far. Dusting out my Common Lisp skills is a reason I use to work on these challenges and don't work on my other projects (professional or not). At least it may help to motivate me to work on the backend of discordia-chan. At the very least it's fun. And as a final word, that's all that matters.

Have fun everyone!