Advent of Code '23 - day 8

Table of Contents

The first part was pretty straightforward, just follow the path and trace your steps. The second part really screamed that brute forcing isn't the way here. I knew what numbers I needed, just not how to calculate those numbers so these (LCM and GCD) I had to look up.

Input

Example

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

Example2

LR

11A = (11B, XXX)
11B = (XXX, 11Z)
11Z = (11B, XXX)
22A = (22B, XXX)
22B = (22C, 22C)
22C = (22Z, 22Z)
22Z = (22B, 22B)
XXX = (XXX, XXX)

Part 1

(defun aoc23/parse-input (string)
  (let* ((string (string-trim string))
         (segments (string-split string "\n\n"))
         (instructions (car segments))
         (instructions (mapcar 'char-to-string instructions))
         (nodes (aoc23/parse-nodes (cadr segments))))
    `((:instructions . ,instructions)
      (:nodes . ,nodes))))

(defun aoc23/parse-nodes (string)
  (let* ((string (string-trim string))
         (lines (string-split string "\n"))
         (map (make-hash-table :test 'equal)))
    (dolist (line lines)
      (let ((elems (string-split line "[=(),]+" t " ")))
        ;(error "%S" (elt elems 0))
        (puthash (elt elems 0)
                 `(,(elt elems 1) .  ,(elt elems 2))
                 map)))
       map))

(let* ((map (aoc23/parse-input input))
       (steps 0)
       (nodes (cdr (assoc :nodes map)))
       (instructions (cdr (assoc :instructions map)))
       (node "AAA"))
  (while (not (string= "ZZZ" node))
    (let ((crossroad (gethash node nodes))
          (dir (elt instructions (% steps (length instructions)))))
      (setq node (if (string= "L" dir)
                     (car crossroad)
                   (cdr crossroad))))

    (setq steps (1+ steps)))
  steps)

Part 2

(defun aoc23/parse-input (string)
  (let* ((string (string-trim string))
         (segments (string-split string "\n\n"))
         (instructions (car segments))
         (instructions (mapcar 'char-to-string instructions))
         (nodes (aoc23/parse-nodes (cadr segments)))
         (startnodes (seq-filter 'aoc23/startp
                                 (hash-table-keys nodes))))
    `((:instructions . ,instructions)
      (:nodes . ,nodes)
      (:startnodes . ,startnodes))))

(defun aoc23/startp (node)
  (= ?A (elt node 2)))

(defun aoc23/endp (node)
  (= ?Z (elt node 2)))

(defun aoc23/parse-nodes (string)
  (let* ((string (string-trim string))
         (lines (string-split string "\n"))
         (map (make-hash-table :test 'equal)))
    (dolist (line lines)
      (let ((elems (string-split line "[=(),]+" t " ")))
                                        ;(error "%S" (elt elems 0))
        (puthash (elt elems 0)
                 `(,(elt elems 1) .  ,(elt elems 2))
                 map)))
    map))
(defun gcd (n m)
  (cond ((< n m) (gcd m n))
        ((= m 0) n)
        (t (gcd m (% n m)))))

(defun lcm (n m)
  (/ (* n m) (gcd n m)))

(let* ((map (aoc23/parse-input input))
       (steps 0)
       (nodes (cdr (assoc :nodes map)))
       (instructions (cdr (assoc :instructions map)))
       (startnodes (cdr (assoc :startnodes map)))
       (num (length startnodes)))

  (setq steps (mapcar (lambda (node)
                        (let ((steps 0))
      (while (not (aoc23/endp node))
    (let ((crossroad (gethash node nodes))
          (dir (elt instructions (% steps (length instructions)))))
      (setq node (if (string= "L" dir)
                     (car crossroad)
                   (cdr crossroad))))

    (setq steps (1+ steps)))
      steps)) startnodes))
  (setq steps (sort steps '>))

  (seq-reduce 'lcm (cdr steps) (car steps)))