Advent of Code 2021, Day 24: Computing with Sets

Day 24 of Advent of Code 2021 naively involves implementing a machine that implements an imaginary assembly language, with a program given as the puzzle input. This must then be executed up to 9^14 times to search for the lowest and highest program inputs that yield a specific result.

Implementing it as an interpreter is computationally infeasible. I did this as a first pass, and it would have taken almost one hundred years of wall clock time to execute.

Looking through the solutions posted to the Advent of Code subreddit for Day 24, there were a wide variety of solutions, including:

My solution was to modify my interpreter to work on sets, to search multiple possibilities in parallel. It wasn’t similar to any I saw, so I thought I’d write it up here.

Interpreter

First, let’s look at an interpreter for the specified ALU. Not shown is the step that parses the instructions. For example, the "mul x 0" string is transformed into the Clojure representation [:mul :x 0] .

(defn machine [input]
  {:memory {:x 0 :y 0 :z 0 :w 0}
   :input input})

(def machine-ops {:mul *
                  :add +
                  :div (fn [a b] (int (/ a b)))
                  :mod mod
                  :eql (fn [a b] (if (= a b) 1 0))})

(defn advance [machine instr]
  (let [[a b c] instr
        get-val (fn [v]
                  (if (keyword? v)
                    (get-in machine [:memory v])
                    v))]
    (if
      (= :inp a)
      (-> machine
          (assoc-in [:memory b] (first (:input machine)))
          (update :input rest))
      (assoc-in machine [:memory b]
                ((machine-ops a) (get-val b) (get-val c))))))

(defn run-program [machine instrs]
  (reduce advance machine instrs))

The advance function takes a machine and an instruction, and returns a new machine advanced by that instruction. The run-program function reduces the machine over a stream of instructions.

Computing with Sets

From here, the naive interpreter can be modified to operate on sets of integers, rather than integers.

Each set represents every possible value that may be bound to a variable.

When executing an operation on two sets, for example (+ a b) , the result is a set that contains each possible value that applies + to any member of a and any member of b . This is a cartesian operation between the sets.

For example:

;; In Clojure notation, Set A + Set B, each containing 1, 2 and 3
(+ #{1 2 3} #{1 2 3})
;; [A0 + B0, A0 + B1, A0 + B2], [A1 + B0, A1 + B1, ...
=> [[2 3 4] [3 4 5] [4 5 6]]
;; All possibilities are concatenated together
=> [2 3 4 3 4 5 4 5 6]
;; And finally, they're placed in a set, which removes duplicates
=> #{2 3 4 5 6}

(* #{1 2 3} #{0})
=> [[0] [0] [0]
=> [0 0 0]
=> #{0}

(= #{1 2} #{0 1 3})
=> [[0 1 0] [0 0 0]]
=> [0 1 0 0 0 0]
=> #{0 1}

The intention is to cull large segments of the search space in parallel, by fixing some inputs and leaving others floating.

Imagine we are looking to search for a + b + c + d = 35 , where each are between 1-9 , inclusive.

Let’s set a = 1 , and leave the rest foating:

(+ #{1} ; a
   #{1 2 3 4 5 6 7 8 9} ; b
   #{1 2 3 4 5 6 7 8 9} ; c
   #{1 2 3 4 5 6 7 8 9}) ; d
=> #{4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28}

As 35 is not in the result, a = 1 is not possible.

False positives are possible. The cartesian product is blind to correlations between variables. For example, (- x x) where x = #{1 2} would return #{-1 0 1} instead of exactly #{0} .

However, false negatives are not possible. If the desired result is not found in a set, it is guaranteed that no combination of inputs would yield it, and that part of the search space can be skipped.

Provenance is also not tracked. You know what possible results are, but not what inputs could have led to them.

Implementation

The modified interpeter is below. Note the changes:

Inputs are, in turn, expected to be expressed as sets of possibilities.

(defn machine [input]
  {:memory {:x #{0} :y #{0} :z #{0} :w #{0}}
   :input input})

(def machine-ops {:mul *
                  :add +
                  :div (fn [a b] (int (/ a b)))
                  :mod mod
                  :eql (fn [a b] (if (= a b) 1 0))})

(defn cartesian-op [op va vb]
  (into #{}
        (for [a va
              b vb]
          (op a b))))

(defn advance [machine instr]
  (let [[a b c] instr
        get-val (fn [v]
                  (if (keyword? v)
                    (get-in machine [:memory v])
                    #{v}))]
    (if
      (= :inp a)
      (-> machine
          (assoc-in [:memory b] (first (:input machine)))
          (update :input rest))
      (assoc-in machine [:memory b]
                (cartesian-op (machine-ops a)
                              (get-val b) (get-val c))))))

(defn run-program [machine instrs]
  (reduce advance machine instrs))

After the program has executed, the :z memory location is tested for inclusion of the value 0 .

In the worst case, the size of the sets may grow very large, and a circuit breaker would be needed - but it was not a necessary feature in order to solve Day 24.

Now we’ve built an interpreter that can search inputs in parallel, it’s time to discuss the search strategy. Our inputs are 14 digits long. Some digits in an input may be fixed to a single value, while others are left unknown, which is bound to the set #{1 2 3 4 5 6 7 8 9} .

I will use the notation 263xxxxxxxxxxx to represent an input where the first three digits are fixed to 263 , and the rest left unknown.

The search function is passed a list of fixed and free numbers. It checks every variation of the first free number to see if the intended result is possible. If so, it sets that number as fixed and recurses further.



(defn search [instrs fixed free]
  (apply concat
    (filter identity
            (for [i (first free)]
              (let [inp (concat fixed [#{i}] (rest free))
                    m (run-program (machine inp) instrs)
                    mem (get-in m [:memory :z])]
                (when (contains? mem 0)
                  (if (empty? (rest free))
                    (conj fixed #{i})
                    (search instrs
                            (conj fixed #{i}) (rest free)))))))))


To parallelize the execution, all permutations of the first three numbers are checked independently in a threadpool. A search path starting from 263 may look like:

263xxxxxxxxxxx
2631xxxxxxxxxx
2632xxxxxxxxxx
2633xxxxxxxxxx
26331xxxxxxxxx
26332xxxxxxxxx
26333xxxxxxxxx
26334xxxxxxxxx
263341xxxxxxxx
263342xxxxxxxx
263343xxxxxxxx
2633431xxxxxxx

Early Out Performance

On a single core of my Ryzen 3900X, testing 917xxxxxxxxxxx indicates without further recursion that this pattern will yield no answer, and takes 1231ms to execute.

This excludes 31.4 billion possibilities from the search. The initial scalar implementation of the interpreter takes approximately 0.1ms to test a single number.

This means that ruling out the search space via the set approach gives us a speed up of approximately 2.5 million times.

There are 729 possible values for the first three digits. Of these, 702 are immediately ruled out a single check. Others require recursion.

Results

Part I of the puzzle asks for the highest input that returns the expected result, which is 91397187145896 . This takes 75 seconds to compute, using all available cores.

Part II of the puzzle asks for the lowest input that returns the expected result, which is 41178298586991 . This takes 248 seconds to compute.

Additionally, the entire space can be searched, and 12,096 solutions can be retrieved in 3,486 seconds.

Not bad. But we can do better! In the next post, we’ll attempt to build a compiler to turn the ALU instructions into Rust.

Source Code

A complete listing of the scalar interpreter can be found here:

https://github.com/reitzensteinm/day24/blob/main/src/day24/scalar.clj

The set based search, including multithreading, can be found here:

https://github.com/reitzensteinm/day24/blob/main/src/day24/set.clj