2024.05.org

Day 05

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

1. Starting slime (M-x slime)
2. Typing C-c C-c in the block initialize.
3. In the repl type (in-package :aoc-2024-05)
4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(unless (find-package :priority-queue)
  (ql:quickload "priority-queue"))
(unless (find-package :cl-ppcre)
  (ql:quickload "cl-ppcre"))
(unless (find-package :parseq)
  (ql:quickload "parseq"))
(unless (find-package :lparallel)
  (ql:quickload "lparallel"))
(unless (find-package :fiveam)
  (ql:quickload "fiveam"))
(unless (find-package :series)
  (ql:quickload "series"))
(unless (find-package :cl-permutation)
  (ql:quickload "cl-permutation"))
(unless (find-package :bordeaux-threads)
  (ql:quickload "bordeaux-threads"))

Create package for this day

<<packages>>
(defpackage :aoc-2024-05
  (:use :common-lisp
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2024-05)

Input

(defun process-stream (in)
  (loop for line = (read-line in nil)
        while line
        collect line))
(defun read-input (file)
  (with-open-file (in file)
    (process-stream in)))

(defparameter *input*
  (read-input "input/05.txt"))

Part 1

The input consists first of sequences N|N then a blank line, then sequences of comma separated numbers.

(defun parse-input (lines)
  (let ((end-of-rules (position "" lines :test #'string=)))
    (list (loop for line in (subseq lines 0 end-of-rules)
                with rules = (make-hash-table)
                finally (return rules)
                do (destructuring-bind (left right)
                       (mapcar #'parse-integer (cl-ppcre:all-matches-as-strings "\\d+" line))
                     (push right (gethash left rules))))
          (loop for line in (subseq lines (1+ end-of-rules))
                collect (mapcar #'parse-integer (cl-ppcre:all-matches-as-strings "\\d+" line))))))

A print out is good if all rules are correct. I’ve collected the rules as a hash table. I’ll convert each print out into its own hash table which contains “page # -> index” mappings. Once all have been collected, I can check if all rules are valid.

(defun valid-print-out (rules print-out)
  (loop for k being the hash-key using (hash-value v) of rules
        for key-pos = (position k print-out)
        always (or (not key-pos)
                   (loop for page in v
                         for page-pos = (position page print-out)
                         always (or (not page-pos) (< key-pos page-pos))))))
(defun part-1 (rules print-outs)
  (loop for print-out in print-outs
        when (valid-print-out rules print-out)
          sum (elt print-out (truncate (length print-out) 2))))
(defun problem-a () (format t "Problem 05 A: ~a~%" (apply #'part-1 (parse-input *input*))))

Part 2

Now we have to fix all the incorrect ones, same answer for submission: Sum of middle pages (after reordering).

I’m going to try to use the bulit-in sort but with a custom comparator. We’ll see how this does.

(defun fix-print-out (rules print-out)
  (flet ((compare (a b)
           (and (gethash a rules)
                (position b (gethash a rules)))))
    (sort (copy-seq print-out) #'compare)))
(defun part-2 (rules print-outs)
  (loop for print-out in print-outs
        unless (valid-print-out rules print-out)
          sum (elt (fix-print-out rules print-out) (truncate (length print-out) 2))))
(defun problem-b () (format t "Problem 05 B: ~a~%" (apply #'part-2 (parse-input *input*))))

Putting it all together

<<read-input>>
<<input>>
<<parse-input>>

<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)

Answer

Problem 05 A: 6949
Problem 05 B: 4145

Test Cases

(def-suite aoc.2024.05)
(in-suite aoc.2024.05)

(run! 'aoc.2024.05)

Test Results

Thoughts