Advent of Code 2024: Day 5

For day 5, the input comes in two parts: There are rules of the form n|m, where n and m are numbers, and there are “updates” which are lists of numbers separated by commas. The rules are used to determine which updates are valid. An update is valid if it passes all applicable rules. A rule is applicable if the two numbers in the rule appear in the update. An update passes an applicable rule if the two numbers in the rule appear in the update in the same order as they appear in the rule.

To read the input, we read the lines and collect them into two lists. The rule list is all the lines that contain a pipe character, and the updates list is all the lines that contain a comma:

(defun read-input (input-file)
  (let ((lines (scan-file input-file #'read-line)))
    (let ((is-rule (#M(lambda (line) (find #\| line)) lines))
          (is-update (#M(lambda (line) (find #\, line)) lines)))
      (values (collect ’list (#M(lambda (rule)
                                  (map ’list #’parse-integer (str:split #\| rule)))
                                (choose is-rule lines)))
              (collect ’list (#M(lambda (update)
                                  (map ’list #’parse-integer (str:split #\, update)))
                                (choose is-update lines)))))))

To test a rule, we find the location of the two numbers in the update and check that they are in the same order as they appear in the rule. If either number is not found, the rule is not applicable and trivially passes.

(defun test-rule (rule update)
  (let ((left-position (position (first rule) update))
        (right-position (position (second rule) update)))
    (or (null left-position)
        (null right-position)
        (< left-position right-position))))

(defun test-rules (rules update)
  (collect-and
   (#Mtest-rule
    (scan ’list rules)
    (series update))))

Part 1 is to sum the middle numbers of all the updates that pass all the rules:

(defun middle-number (list)
  (elt list (/ (1- (length list)) 2)))

(defun part-1 ()
  (multiple-value-bind (rules updates) (read-input (input-pathname))
    (collect-sum
     (#Mmiddle-number
      (choose-if
       (lambda (update) (test-rules rules update))
       (scan ’list updates))))))

For part 2, we select the updates that fail the rules. We repair the update by sorting it using the rules as a sort predicate, then we sum the middle numbers of the repaired updates:

(defun sort-using-rules (rules list)
  (sort list (lambda (left right)
               (find (list left right) rules :test #’equal))))

(defun part-2 ()
  (multiple-value-bind (rules updates) (read-input (input-pathname))
    (collect-sum
     (#Mmiddle-number
      (#M(lambda (update) (sort-using-rules rules update))
       (choose-if
        (lambda (update) (not (test-rules rules update)))
        (scan ’list updates)))))))