Advent of Code 2023 Day 8

Let's solve today's challenge using Clojure.

Parsing


            LLR

            AAA = (BBB, BBB)
            BBB = (AAA, ZZZ)
            ZZZ = (ZZZ, ZZZ)

sample input

We will try to be expressive and going to parse the input into a semantic form. We are mapping node directions to :left and :right keys and parsing out the directions using same keywords, so later we would be able to query our structure with ease.


              (defn parse [input]
                (let [[directions maps] (str/split input #"\n\n")
                      maps (reduce #(conj %1 (read-direction %2)) {} (str/split-lines maps))
                      directions (map (fn [itm] (case itm
                                                  "L" :left
                                                  "R" :right)) (str/split directions #""))]
                  {:directions directions, :maps maps}))

parse


              (defn read-direction [line]
                (let [[key left right] (re-seq #"[A-Z0-9][A-Z0-9][A-Z0-9]" line)]
                  {key {:left left :right right}}))

read-direction

And voila, our resulting map:


             {:directions (:left :left :right),
              :maps
                {"AAA" {:left "BBB", :right "BBB"},
                 "BBB" {:left "AAA", :right "ZZZ"},
                 "ZZZ" {:left "ZZZ", :right "ZZZ"}}}

semantic input

Part one

Part one is pretty straightforward, we just loop increasing the counter until "ZZZ" is found.


            (defn count-steps [{directions :directions maps :maps}]
              (loop [cnt 0
                     [direction & more] (flatten (repeat directions))
                     location "AAA"] ; Starting at AAA
                (if (= location "ZZZ")
                  cnt
                  (recur (inc cnt) more (get-in maps [location direction])))))

count-steps

Neat part is how we can leverage infinite sequence to repeat our directions list:


            (flatten (repeat directions))

infinite directions

Assemble parsing and solving together:


            (defn part-one [input]
              (-> input parse count-steps))

            (part-one test-input) ;; => 6

part one

Part two

Now part two is a bit more tricky. Unless you have an access to a quantum computer, brute-forcing the solution might finish just after the heat death of the universe.

As an experiment we can check how far apart are subsequent exit nodes on a single path. Here we use real input and start from "DVA" node. We halt after 5 nodes are found.


  (defn find-repetitions [{directions :directions maps :maps} start]
    (loop [reps-cnt 0
           reps-acc []
           cnt 0
           [direction & more] (flatten (repeat directions))
           location start]
      (cond
        (< 5 reps-cnt) reps-acc
        (str/ends-with? location "Z")
        (recur
         (inc reps-cnt)
         (conj reps-acc cnt)
         0
         more
         (get-in maps [location direction]))
        :else
        (recur
         reps-cnt
         reps-acc
         (inc cnt)
         more
         (get-in maps [location direction])))))

  (find-repetitions (parse real-input) "DVA")
      ;; => [13939 13938 13938 13938 13938 13938]

experiment

The distances are identical — the paths are endless circles!

Repeating integer sequences' converging point is their lowest common multiple (LCM). With newly acquired information, we calculate all paths' lengths and LCM of all of them.


             (defn find-repetition [{directions :directions maps :maps} start]
              (loop [cnt 0
                     [direction & tail] (flatten (repeat directions))
                     location start]
                (if (str/ends-with? location "Z")
                  cnt
                  (recur (inc cnt) tail (get-in maps [location direction])))))

            (defn gcd [a b]
              (if (zero? b) a (recur b, (mod a b))))

            (defn lcm [a b]
              (/ (* a b) (gcd a b)))

            (defn part-two [input]
              (let [parsed (parse input)]
                (->> (parsed :maps)
                     keys
                     (filter #(str/ends-with? % "A"))
                     (map #(find-repetition parsed %))
                     (reduce lcm)))

part two

And we get our answer. Good luck next day!


              (part-2 real-input) ;; => 13740108158591

answer