Advent of Code 2024: Day 24

In day 24, we are given a set of equations that decribe some combinatorical logic. The first task is to read the input and parse out the combinatoric circuit and simulate it. To do this, I hijack the lisp reader. I create a readtable this is just like the standard Lisp readtable, but with these differences:

• Case is not folded.
• The colon character is no longer a package prefix marker, but rather a terminating macro character that inserts the token :colon into the stream.
• The newline character is no longer a whitespace character, but rather a terminating macro character that inserts the token :newline into the stream.

These changes to the reader make it esay to parse the input file. We build a labels expression where each named quantity in the circuit (the wires) is a function of zero arguments. Simulating the solution is then just a matter of calling eval on the resulting expression.

(defun get-input (swaps input-pathname)
  (flet ((maybe-swap (symbol)
           (cond ((assoc symbol swaps) (cdr (assoc symbol swaps)))
                 ((rassoc symbol swaps) (car (rassoc symbol swaps)))
                 (t symbol))))

    (let ((*readtable* (copy-readtable nil)))
      (setf (readtable-case *readtable*) :preserve)
      (set-syntax-from-char #\: #\;)
      (set-macro-character #\: (lambda (stream char) (declare (ignore stream char)) :colon))
      (set-macro-character #\newline (lambda (stream char) (declare (ignore stream char)) :newline))

      (with-open-file (stream input-pathname :direction :input)
        (let iter ((token (read stream nil :eof))
                   (line '())
                   (gates '())
                   (wires '())
                   (outputs '()))
        
          (multiple-value-bind (line* gates* wires* outputs*)
              (if (or (eq token :eof) (eq token :newline))
                  (if line
                      (if (member :colon line)
                          (values '()
                                  gates
                                  (cons `(,(third line) () ,(first line)) wires)
                                  outputs)
                          (values '()
                                  (cons `(,(maybe-swap (first line)) ()
                                          (,(ecase (fourth line)
                                              (XOR 'logxor)
                                              (OR 'logior)
                                              (AND 'logand))
                                           ,@(list (list (third line)) (list (fifth line)))))
                                        gates)
                                  wires
                                  (if (and (symbolp token)
                                           (char= (char (symbol-name token) 0) #\z))
                                      (cons `(list ,(list token)) outputs)
                                      outputs)
                                  ))
                      (values '() gates wires outputs))
                  (values (cons token line) gates wires (if (and (symbolp token)
                                                                 (char= (char (symbol-name token) 0) #\z))
                                                            (cons (list token) outputs)
                                                            outputs)))
            (if (eq token :eof)
                `(labels (,@wires*
                          ,@gates*)
                   (fold-left (lambda (acc bit)
                                (+ (* 2 acc) bit))
                              0  (list ,@(sort outputs* #'string-greaterp :key (lambda (term) (symbol-name (car term)))))))
                (iter (read stream nil :eof) line* gates* wires* outputs*))))))))

For part 2, we are told that the circuit is supposed to add two binary numbers. We are also told that the circuit the circuit has four of its wires swapped. We are asked to find the swapped wires.

It is hard to understand what is going on because almost all the wires have random three-letter names. We start by renaming the wires so that they have a bit number prefixed to with them. If a gate has two numbered inputs where the numbers are equal, we propagate the number to the output of the gate.

Once the wires are numbered, we sort the wires by their numbers and print the wire list. The regular pattern of gates is instantly obvious, and the swapped wires are easy to spot. It isn't obvious how to find the swapped wires in the general case, but it is unnecessary to solve the puzzle, so there is no code for this.