AoC 2024

My solutions for Advent of Code 2024

Author

Rens Oliemans

Welcome to my solution page for Advent of Code 2024. You can find the git repo here.

Day 1: Historian Hysteria

Part 1

We have a list of pairs of numbers, and we need to pair the smallest left number with the smallest right number, second-smallest left with second-smallest right, etc. Idea: transpose, sort both lists, transpose again, and compute.

(defn part1 [input]
  (->> (s/parse-lines input)
       (map s/parse-ints)
       v/transpose
       (map sort)
       v/transpose
       (map #(abs (- (first %) (second %))))
       (reduce +)))

Part 2

This is easy with the fn frequencies:

(defn part2 [input]
  (let [input (v/transpose (map s/parse-ints (s/parse-lines input)))
        one (first input)
        freqs (frequencies (second input))]
    (->> one
         (map #(* % (freqs % 0)))
         (reduce +))))

Day 2: Red-Nosed Reports

Part 1

(partition 2 1) finds all pairs, and then we can just compute the difference and return whether each difference is between 1 and 3 (inclusive), and each difference has the same parity.

(defn diffs [record]
  (->> record
       (partition 2 1)
       (mapv (fn [[a b]] (- b a)))))

(defn is-safe? [record]
  (let [differences (diffs record)]
    (and (every? #(<= 1 (abs %) 3) differences)
         (apply = (map pos? differences)))))

(defn part1 [input]
  (->> (s/parse-lines input s/parse-ints)
       (filter is-safe?)
       (count)))

Part 2

Remove each level one by one and check if the record is safe then. Not the most efficient, but simple and fast enough (~50msec):

(defn drop-nth [coll n]
  (keep-indexed #(if (not= %1 n) %2) coll))

(defn dampened-is-safe? [record]
  (some is-safe? (map #(drop-nth record %)
                      (range (count record)))))

(defn part2 [input]
  (->> (s/parse-lines input s/parse-ints)
       (filter dampened-is-safe?)
       (count)))

Day 3: Mull It Over

Part 1

regex on "mul$(\d+),(\d+)$", multiply each result and sum.

(defn part1 [input]
  (->> (re-seq #"mul\((\d+),(\d+)\)" input)
       (map (fn [[_ a b]] (* (Long/parseLong a)
                             (Long/parseLong b))))
       (reduce +)))

Part 2

do() enables instructions, don't() disables them. I started out doing a more complicated loop where I keep track of the current state (enabled/disabled). Instead, we just remove all text in between don't() and do() and re-run part one on this smaller input. In order to replace everything, don’t forget to remove the newlines as well, as some don't()/do() pairs have newlines between them.

(defn part2 [input]
  (let [inp (-> input
                (str/replace #"\n" "")
                (str/replace #"don't\(\).+?do\(\)" ""))]
    (part1 inp)))

Day 4: Ceres Search

Part 1

(defn is-xmas? "Does the grid `grid` contain the string \"XMAS\",
   starting at `start` and going in `direction`?"
  [grid start direction]
  (loop [location start
         chars (seq "XMAS")]
    (if (empty? chars)
      true
      (if (not= (get-in grid location) (first chars))
        false
        (recur 
         (mapv + location direction)
         (rest chars))))))

This function does all the heavy lifting, for a given location and direction, finds whether the grid contains XMAS there.

(defn is-xmas? "Does the grid `grid` contain the string \"XMAS\",
 starting at `start` and going in `direction`?"
  [grid start direction]
  (loop [location start
         chars (seq "XMAS")]
    (if (empty? chars)
      true
      (if (not= (get grid location) (first chars))
        false
        (recur 
         (mapv + location direction)
         (rest chars))))))

All that remains is to do this for each X and for each direction (v/adjacent-dirs):

(defn count-xmases-at [grid start directions]
  (count (filter #(is-xmas? grid start %) directions)))

(defn part1 [input]
  (let [grid (g/to-matrix input)
        xs (g/locs-where grid #(= % \X))]
    (->> xs
         (map #(count-xmases-at grid % v/adjacent-dirs))
         (reduce +))))

Part 2

For each A and for each diagonal direction, check whether there are exactly two MAS-es.

(defn is-mas? [grid middle direction]
  (let [opposite-direction (mapv #(* -1 %) direction)]
    (and (= \M (get-in grid (mapv + middle direction)))
         (= \S (get-in grid (mapv + middle opposite-direction))))))

(defn count-mases-at [grid middle directions]
  (count (filter #(is-mas? grid middle %) directions)))

(defn part2 [input]
  (let [grid (g/to-matrix input)
        as (g/locs-where grid #(= % \A))]
    (->> as
         (map #(count-mases-at grid % v/diagonal-dirs))
         (filter #(= % 2))
         (count))))

Day 5: Print Queue

Part 1

We can think of the input as a directed graph, where 29|13 leads to a vertex from 29 to 13. We parse the input to obtain the orderings, updates and a dependency graph. Our solution requires us to find the middle number of all updates that are correctly-ordered. Here’s the parsing and the shell of part 1:

(defn parse-input
  "Parses an input string and returns three useful objects.
    The first obj is a list of orderings, strings of type \"A|B\".
    The second obj is a list of updates, each one a list of strings.
    The third obj is a dependency graph, a map."
  [input]
  (let [[orderings updates] (->> (s/parse-blocks input) (map s/parse-lines))]
    [orderings
     (map #(str/split % #",") updates)
     (build-dependency-graph orderings)]))

(defn part1 [input]
  (let [[orderings updates dep-graph] (parse-input input)
        dep-sorted? (partial dep-sorted? dep-graph)]
    (->> updates
         (pmap #(list % (dep-sorted? %)))
         (filter last)
         (pmap first)
         (pmap middle-num)
         (reduce +))))

The above code relies on three functions not yet defined: middle-num, dep-sorted? and build-dependency-graph. build-dependency-graph and middle-num are relatively straightforward:

(defn build-dependency-graph
  [orderings]
  (let [order-pairs (->> orderings
                         (map #(str/split % #"\|"))
                         (map #(hash-map (second %), [(first %)])))]
    (apply (partial merge-with into) order-pairs)))

(defn middle-num
  "Finds the middle string in a list of string, and parse it to a
  number. Assumes the length of the list list is odd."
  [update]
  (read-string (nth update (/ (count update) 2))))

And the meat is in dep-sorted?, which tells us wheter an update is sorted, using a dependency graph as obtained from build-dependency-graph. It’s 2025 at the time of writing and I forgot how it works, figuring this out is left as an exercise for the reader.

(defn dep-sort
  "Sort a list of strings based on a dependency map.
  The map defines which elements should come after others."
  [dep-graph update]
  (let [graph (reduce (fn [acc item]
                        (assoc acc item 
                               (set (get dep-graph item []))))
                      {} update)
        local-deps (fn [deps] (filter #(contains? (set update) %) deps))]
    (vec (sort-by (fn [item]
                    (let [deps (get dep-graph item [])]
                      (count (local-deps deps))))
                  update))))

(defn dep-sorted? [dependency-graph update]
  (= update (dep-sort dependency-graph update)))

Part 2

This is now trivial, since we can now easily sort everything, filter the unsorted updates, and do the same computation:

(defn part2 [input]
  (let [[orderings updates deps] (parse-input input)
        is-sorted? (partial dep-sorted? deps)
        dep-sort (partial dep-sort deps)]
    (->> updates
         (pmap #(list % (dep-sort %)))
         (filter #(not= (first %) (last %)))
         (pmap last)
         (pmap middle-num)
         (reduce +))))

Day 6: Guard Gallivant

Part 1

The guard walks across the grid until they encounter an obstacle (#), marking a turn in clockwise direction. Simply walk out that path until (get-in grid next-location) is nil:

(defn guard-route
  "Takes a `grid` as input returns a vector of 2d coordinates: the route
  of the guard, starting at `start` and turning clockwise at \"#\"
  characters. "
  [grid start]
  (let [size (count grid)
        grid (assoc-in grid start \.)]
    (loop [location start
           directions (cycle v/cardinal-dirs)
           route []]
      (let [[y x] location
            [x' y'] (first directions)
            next-location [(+ y y') (+ x x')]
            next-object (get-in grid next-location)
            route (conj route location)]
        (condp = next-object
          nil route
          \. (recur next-location
                    directions
                    route)
          \# (recur location
                    (next directions)
                    route))))))

(defn part1 [input]
  (let [grid (g/to-matrix input)
        start (first (g/locs-where grid #(= % \^)))
        route (guard-route grid start)]
    (count (distinct route))))

Part 2

For each point in the route (that isn’t the starting position), add an obstacle and check whether the route has a loop:

(defn route-has-loop? [grid start]
  (let [size (count grid)
        grid (assoc-in grid start \.)]
    (loop [location start
           directions (cycle v/cardinal-dirs)
           visited #{}]
      (let [[y x] location
            [x' y'] (first directions)
            next-location [(+ y y') (+ x x')]
            next-object (get-in grid next-location)
            pair [next-location [x' y']]]
        (if (contains? visited pair)
          true ;; we have a loop!
          (condp = next-object
            nil false ;; we exited the puzzle
            \. (recur next-location
                      directions
                      visited)
            \# (recur location
                      (next directions)
                      (conj visited pair))))))))

(defn part2 [input]
  (let [grid (g/to-matrix input)
        start (first (g/locs-where grid #(= % \^)))
        route (disj (set (guard-route grid start)) start)]
    (->> route
         (pmap (fn [new-obstacle]
                 (route-has-loop? (assoc-in grid new-obstacle \#) start)))
         (filter true?)
         (count))))

Timing of different methods

The following table shows a short overview of the results of (time (p2 input)) (it’s too slow for (crit/quick-bench)) with some different variants:

Method	time
Set - always add & check	9s
Set - only add on obstacle	6s
Set - only check on north	5.5
Counter (7000)	4s

set methods.

These methods refer to keeping track of a set of visited (node, direction) pairs. If we’ve seen one before, we must be in a loop. My original implementation was Set - always add & check: add every location we visit to the visited set and check if we’ve seen it before. That turned out to be the slowest one—my code spent about 10% of its time hashing entries. One step faster is Set - only add on obstacle, which only adds an element to the set when we visit an obstacle.

The fastest set-related method (though only slightly) was Set - only check on north, and this only checks if the current (node, direction)-pair is in visited if direction = North=. This was counterintuitive for me since that meant it was actually doing some extra work: it might be traversing the current path for up to 3 extra obstacles compared to the previous one. However, the hashing was apparently so expensive compared to traversing the grid that this was still a hair faster.

Since this was only slightly faster but made the code a bit convoluted and difficult to understand (“why are we only checking if we’ve been here if we’re heading North right now?”), I opted for the second method.
Counter.

This is kind of a hack, but it’s faster than the set-methods. Instead of a visited set, we keep track of a counter of nodes we’ve visited. Once we reach 7000, we assume we’re in a loop and exit. 6500 also worked for me, but that might be too input-dependent.

Still, any arbitrary number fails for some input, so I’ve opted to not do this.

Day 7: Bridge Repair

Part 1

This is an example line: 3267: 81 40 27. Let $t = 3267$ be the target, and $n_1 = 81, n_2 = 40, n_3 = 27$ be the “numbers” that should make up $t$. Each equation has $k$ numbers, $k=3$ for this example.

Let’s define a function is-correct?, which will output true if $t$ can be “made” with $n_1, \dots, n_k$ and false otherwise.

Since the compution is LTR, $n_k$ will always be applied last. If the operator is multiplication, for example, $t$ must be divisible by $n_k$. If it is not, the multiplication operator is not valid for that spot. If it is, we recursively check is-correct? with a new $t' = t / n_k$, and the numbers $n_1, n_2, \dots, n_{k-1}$.

At a certain point we might end up with $k=1$, the base case for is-correct?. is-correct? will output true if and only if $t=k$.

We must first define for each operator a reverse and valid?:

(defn- operators-1 []
  [{:name :multiplication :reverse #(/ %1 %2) :valid? #(= 0 (mod %1 %2))}
   {:name :addition :reverse #(- %1 %2) :valid? #(> %1 %2)}])

And here is our recursive is-correct?:

(defn- is-correct?
  "Can `target` be made with `numbers`, using `operators`?"
  [target numbers operators]
  (if (= 1 (count numbers))
    (= target (first numbers))
    (->> operators
         (filter (fn [op] ((:valid? op) target (last numbers))))
         (some (fn [op]
                 (is-correct?
                  ((:reverse op) target (last numbers))
                  (butlast numbers)
                  operators))))))

(defn- sum-correct-equations [input operators]
  (->> (s/parse-lines input)
       (map s/parse-ints)
       (filter (fn [[target & numbers]] (is-correct? target numbers operators)))
       (map first)
       (reduce +)))

(defn part1 [input]
  (let [ops (operators-1)]
    (sum-correct-equations input ops)))

Part 2

Part two is effectively identical, but now with the concatenation operator:

(defn- operators-2 []
  (into (operators-1)
        [{:name :concatenation
          :reverse (fn [n x]
                     (let [s (str n)]
                       (Long/parseLong (subs s 0 (- (count s) (count (str x)))))))
          :valid? (fn [n x]
                    (let [sn (str n)
                          sx (str x)]
                      (and (> (count sn) (count sx))
                           (str/ends-with? sn sx))))}]))

(defn part2 [input]
  (let [ops (operators-2)]
    (sum-correct-equations input ops)))

My previous version ran over three seconds, but this runs in 50msec.

--- author: Rens Oliemans header-args: ":eval no :exports both" subtitle: My solutions for Advent of Code 2024 title: AoC 2024 --- Welcome to my solution page for [Advent of Code 2024](https://adventofcode.com/2024). You can find [the git repo here](https://codeberg.org/RensOliemans/AoC). # [Day 1: Historian Hysteria](https://adventofcode.com/2024/day/1) ## Part 1 We have a list of pairs of numbers, and we need to pair the smallest left number with the smallest right number, second-smallest left with second-smallest right, etc. Idea: transpose, sort both lists, transpose again, and compute. ``` clojure (defn part1 [input] (->> (s/parse-lines input) (map s/parse-ints) v/transpose (map sort) v/transpose (map #(abs (- (first %) (second %)))) (reduce +))) ``` ## Part 2 This is easy with the fn `frequencies`{.verbatim}: ``` clojure (defn part2 [input] (let [input (v/transpose (map s/parse-ints (s/parse-lines input))) one (first input) freqs (frequencies (second input))] (->> one (map #(* % (freqs % 0))) (reduce +)))) ``` # [Day 2: Red-Nosed Reports](https://adventofcode.com/2024/day/2) ## Part 1 `(partition 2 1)`{.verbatim} finds all pairs, and then we can just compute the difference and return whether each difference is between 1 and 3 (inclusive), and each difference has the same parity. ``` clojure (defn diffs [record] (->> record (partition 2 1) (mapv (fn [[a b]] (- b a))))) (defn is-safe? [record] (let [differences (diffs record)] (and (every? #(<= 1 (abs %) 3) differences) (apply = (map pos? differences))))) (defn part1 [input] (->> (s/parse-lines input s/parse-ints) (filter is-safe?) (count))) ``` ## Part 2 Remove each level one by one and check if the record is safe then. Not the most efficient, but simple and fast enough (\~50msec): ``` clojure (defn drop-nth [coll n] (keep-indexed #(if (not= %1 n) %2) coll)) (defn dampened-is-safe? [record] (some is-safe? (map #(drop-nth record %) (range (count record))))) (defn part2 [input] (->> (s/parse-lines input s/parse-ints) (filter dampened-is-safe?) (count))) ``` # [Day 3: Mull It Over](https://adventofcode.com/2024/day/3) ## Part 1 regex on `"mul$(\d+),(\d+)$"`{.verbatim}, multiply each result and sum. ``` clojure (defn part1 [input] (->> (re-seq #"mul$(\d+),(\d+)$" input) (map (fn [[_ a b]] (* (Long/parseLong a) (Long/parseLong b)))) (reduce +))) ``` ## Part 2 `do()`{.verbatim} enables instructions, `don't()`{.verbatim} disables them. I started out doing a more complicated loop where I keep track of the current state (enabled/disabled). Instead, we just remove all text in between `don't()`{.verbatim} and `do()`{.verbatim} and re-run part one on this smaller input. In order to replace everything, don't forget to remove the newlines as well, as some `don't()/do()`{.verbatim} pairs have newlines between them. ``` clojure (defn part2 [input] (let [inp (-> input (str/replace #"\n" "") (str/replace #"don't.+?do" ""))] (part1 inp))) ``` # [Day 4: Ceres Search](https://adventofcode.com/2024/day/4) ## Part 1 ``` clojure (defn is-xmas? "Does the grid `grid` contain the string \"XMAS\", starting at `start` and going in `direction`?" [grid start direction] (loop [location start chars (seq "XMAS")] (if (empty? chars) true (if (not= (get-in grid location) (first chars)) false (recur (mapv + location direction) (rest chars)))))) ``` This function does all the heavy lifting, for a given location and direction, finds whether the grid contains `XMAS`{.verbatim} there. ``` clojure (defn is-xmas? "Does the grid `grid` contain the string \"XMAS\", starting at `start` and going in `direction`?" [grid start direction] (loop [location start chars (seq "XMAS")] (if (empty? chars) true (if (not= (get grid location) (first chars)) false (recur (mapv + location direction) (rest chars)))))) ``` All that remains is to do this for each `X`{.verbatim} and for each direction (`v/adjacent-dirs`{.verbatim}): ``` clojure (defn count-xmases-at [grid start directions] (count (filter #(is-xmas? grid start %) directions))) (defn part1 [input] (let [grid (g/to-matrix input) xs (g/locs-where grid #(= % \X))] (->> xs (map #(count-xmases-at grid % v/adjacent-dirs)) (reduce +)))) ``` ## Part 2 For each `A`{.verbatim} and for each diagonal direction, check whether there are exactly two `MAS`{.verbatim}-es. ``` clojure (defn is-mas? [grid middle direction] (let [opposite-direction (mapv #(* -1 %) direction)] (and (= \M (get-in grid (mapv + middle direction))) (= \S (get-in grid (mapv + middle opposite-direction)))))) (defn count-mases-at [grid middle directions] (count (filter #(is-mas? grid middle %) directions))) (defn part2 [input] (let [grid (g/to-matrix input) as (g/locs-where grid #(= % \A))] (->> as (map #(count-mases-at grid % v/diagonal-dirs)) (filter #(= % 2)) (count)))) ``` # [Day 5: Print Queue](https://adventofcode.com/2024/day/5) ## Part 1 We can think of the input as a [directed graph](https://en.wikipedia.org/wiki/Directed_graph), where `29|13`{.verbatim} leads to a vertex from `29`{.verbatim} to `13`{.verbatim}. We parse the input to obtain the orderings, updates and a dependency graph. Our solution requires us to find the middle number of all updates that are correctly-ordered. Here's the parsing and the shell of part 1: ``` clojure (defn parse-input "Parses an input string and returns three useful objects. The first obj is a list of orderings, strings of type \"A|B\". The second obj is a list of updates, each one a list of strings. The third obj is a dependency graph, a map." [input] (let [[orderings updates] (->> (s/parse-blocks input) (map s/parse-lines))] [orderings (map #(str/split % #",") updates) (build-dependency-graph orderings)])) (defn part1 [input] (let [[orderings updates dep-graph] (parse-input input) dep-sorted? (partial dep-sorted? dep-graph)] (->> updates (pmap #(list % (dep-sorted? %))) (filter last) (pmap first) (pmap middle-num) (reduce +)))) ``` The above code relies on three functions not yet defined: `middle-num`{.verbatim}, `dep-sorted?`{.verbatim} and `build-dependency-graph`{.verbatim}. `build-dependency-graph`{.verbatim} and `middle-num`{.verbatim} are relatively straightforward: ``` clojure (defn build-dependency-graph [orderings] (let [order-pairs (->> orderings (map #(str/split % #"\|")) (map #(hash-map (second %), [(first %)])))] (apply (partial merge-with into) order-pairs))) (defn middle-num "Finds the middle string in a list of string, and parse it to a number. Assumes the length of the list list is odd." [update] (read-string (nth update (/ (count update) 2)))) ``` And the meat is in `dep-sorted?`{.verbatim}, which tells us wheter an update is sorted, using a dependency graph as obtained from `build-dependency-graph`{.verbatim}. It's 2025 at the time of writing and I forgot how it works, figuring this out is left as an exercise for the reader. ``` clojure (defn dep-sort "Sort a list of strings based on a dependency map. The map defines which elements should come after others." [dep-graph update] (let [graph (reduce (fn [acc item] (assoc acc item (set (get dep-graph item [])))) {} update) local-deps (fn [deps] (filter #(contains? (set update) %) deps))] (vec (sort-by (fn [item] (let [deps (get dep-graph item [])] (count (local-deps deps)))) update)))) (defn dep-sorted? [dependency-graph update] (= update (dep-sort dependency-graph update))) ``` ## Part 2 This is now trivial, since we can now easily sort everything, filter the unsorted updates, and do the same computation: ``` clojure (defn part2 [input] (let [[orderings updates deps] (parse-input input) is-sorted? (partial dep-sorted? deps) dep-sort (partial dep-sort deps)] (->> updates (pmap #(list % (dep-sort %))) (filter #(not= (first %) (last %))) (pmap last) (pmap middle-num) (reduce +)))) ``` # [Day 6: Guard Gallivant](https://adventofcode.com/2024/day/6) ## Part 1 The guard walks across the grid until they encounter an obstacle (`#`{.verbatim}), marking a turn in clockwise direction. Simply walk out that path until (`get-in grid next-location`{.verbatim}) is `nil`{.verbatim}: ``` clojure (defn guard-route "Takes a `grid` as input returns a vector of 2d coordinates: the route of the guard, starting at `start` and turning clockwise at \"#\" characters. " [grid start] (let [size (count grid) grid (assoc-in grid start \.)] (loop [location start directions (cycle v/cardinal-dirs) route []] (let [[y x] location [x' y'] (first directions) next-location [(+ y y') (+ x x')] next-object (get-in grid next-location) route (conj route location)] (condp = next-object nil route \. (recur next-location directions route) \# (recur location (next directions) route)))))) (defn part1 [input] (let [grid (g/to-matrix input) start (first (g/locs-where grid #(= % \^))) route (guard-route grid start)] (count (distinct route)))) ``` ## Part 2 For each point in the route (that isn't the starting position), add an obstacle and check whether the route has a loop: ``` clojure (defn route-has-loop? [grid start] (let [size (count grid) grid (assoc-in grid start \.)] (loop [location start directions (cycle v/cardinal-dirs) visited #{}] (let [[y x] location [x' y'] (first directions) next-location [(+ y y') (+ x x')] next-object (get-in grid next-location) pair [next-location [x' y']]] (if (contains? visited pair) true ;; we have a loop! (condp = next-object nil false ;; we exited the puzzle \. (recur next-location directions visited) \# (recur location (next directions) (conj visited pair)))))))) (defn part2 [input] (let [grid (g/to-matrix input) start (first (g/locs-where grid #(= % \^))) route (disj (set (guard-route grid start)) start)] (->> route (pmap (fn [new-obstacle] (route-has-loop? (assoc-in grid new-obstacle \#) start))) (filter true?) (count)))) ``` ### Timing of different methods The following table shows a short overview of the results of `(time (p2 input))` (it's too slow for `(crit/quick-bench)`) with some different variants: Method time ---------------------------- ------ Set - always add & check 9s Set - only add on obstacle 6s Set - only check on north 5.5 Counter (7000) 4s 1. `set`{.verbatim} methods. These methods refer to keeping track of a `set`{.verbatim} of visited `(node, direction)`{.verbatim} pairs. If we've seen one before, we must be in a loop. My original implementation was *Set - always add & check*: add *every* location we visit to the `visited`{.verbatim} set and check if we've seen it before. That turned out to be the slowest one—my code spent about 10% of its time hashing entries. One step faster is *Set - only add on obstacle*, which only adds an element to the set when we visit an obstacle. The fastest `set`{.verbatim}-related method (though only slightly) was *Set - only check on north*, and this only checks if the current `(node, direction)`{.verbatim}-pair is in `visited`{.verbatim} if `direction =`{.verbatim} North=. This was counterintuitive for me since that meant it was actually doing some extra work: it might be traversing the current path for up to 3 extra obstacles compared to the previous one. However, the hashing was apparently so expensive compared to traversing the grid that this was still a hair faster. Since this was only slightly faster but made the code a bit convoluted and difficult to understand ("why are we only checking if we've been here if we're heading North right now?"), I opted for the second method. 2. `Counter`{.verbatim}. This is kind of a hack, but it's faster than the `set`{.verbatim}-methods. Instead of a `visited`{.verbatim} set, we keep track of a `counter`{.verbatim} of nodes we've visited. Once we reach 7000, we assume we're in a loop and exit. 6500 also worked for me, but that might be too input-dependent. Still, any arbitrary number fails for some input, so I've opted to not do this. # [Day 7: Bridge Repair](https://adventofcode.com/2024/day/7) ## Part 1 This is an example line: `3267: 81 40 27`{.verbatim}. Let $t = 3267$ be the target, and $n_1 = 81, n_2 = 40, n_3 = 27$ be the "numbers" that should make up $t$. Each equation has $k$ numbers, $k=3$ for this example. Let's define a function `is-correct?`{.verbatim}, which will output `true`{.verbatim} if $t$ can be "made" with $n_1, \dots, n_k$ and `false`{.verbatim} otherwise. Since the compution is LTR, $n_k$ will always be applied last. If the operator is multiplication, for example, $t$ must be divisible by $n_k$. If it is not, the multiplication operator is not valid for that spot. If it is, we recursively check `is-correct?`{.verbatim} with a new $t' = t / n_k$, and the numbers $n_1, n_2, \dots, n_{k-1}$. At a certain point we might end up with $k=1$, the base case for `is-correct?`{.verbatim}. `is-correct?`{.verbatim} will output `true`{.verbatim} if and only if $t=k$. We must first define for each operator a `reverse`{.verbatim} and `valid?`{.verbatim}: ``` clojure (defn- operators-1 [] [{:name :multiplication :reverse #(/ %1 %2) :valid? #(= 0 (mod %1 %2))} {:name :addition :reverse #(- %1 %2) :valid? #(> %1 %2)}]) ``` And here is our recursive `is-correct?`{.verbatim}: ``` clojure (defn- is-correct? "Can `target` be made with `numbers`, using `operators`?" [target numbers operators] (if (= 1 (count numbers)) (= target (first numbers)) (->> operators (filter (fn [op] ((:valid? op) target (last numbers)))) (some (fn [op] (is-correct? ((:reverse op) target (last numbers)) (butlast numbers) operators)))))) (defn- sum-correct-equations [input operators] (->> (s/parse-lines input) (map s/parse-ints) (filter (fn [[target & numbers]] (is-correct? target numbers operators))) (map first) (reduce +))) (defn part1 [input] (let [ops (operators-1)] (sum-correct-equations input ops))) ``` ## Part 2 Part two is effectively identical, but now with the concatenation operator: ``` clojure (defn- operators-2 [] (into (operators-1) [{:name :concatenation :reverse (fn [n x] (let [s (str n)] (Long/parseLong (subs s 0 (- (count s) (count (str x))))))) :valid? (fn [n x] (let [sn (str n) sx (str x)] (and (> (count sn) (count sx)) (str/ends-with? sn sx))))}])) (defn part2 [input] (let [ops (operators-2)] (sum-correct-equations input ops))) ``` My [previous version](https://codeberg.org/RensOliemans/AoC/commit/da0758592738243980f33c3d86150682371e8c25) ran over three seconds, but this runs in 50msec.