Last week I explained how I got the right answer in a very unsatisfying way. In this post, I'll show how I eventually got to a proper solution.

I'm going to jump right in, so if you're not familiar with the problem or where we left off, this may not make much sense.

Yet another dead end

My next idea was that, maybe, if I could reduce the entire thing to a single algebraic formula, that would give me further insight into the problem. I spent some time trying to do that manually, and it worked quite well until the fifth input, when the size of the formula suddenly started to explode.

As a concrete example, here's the code for my first two inputs:

inp w
mul x 0
add x z
mod x 26
div z 1
add x 10
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 2
mul y x
add z y
inp w
mul x 0
add x z
mod x 26
div z 1
add x 15
eql x w
eql x 0
mul y 0
add y 25
mul y x
add y 1
mul z y
mul y 0
add y w
add y 16
mul y x
add z y

Walking through that line by line, we can construct a formula for each variable in terms of the inputs. Further, we can simplify those formulas quite a bit because we know all variables/registers start at 0 and inputs can only be between 1 and 9.

After the first line, our "state" can be represented as:

w = I_0
x = 0
y = 0
z = 0

The second line does nothing: it multiplies x by zero, but it's already zero. The next three lines are similarly useless: z is zero so adding it to x changes nothing; x is zero so mod with any base is still zero, and division by 1 is always a no-op.

Continuing like that, we get the following state just before the second input:

w = I_0
x = 1
y = (+ I_0 2)
z = (+ I_0 2)

You can probably see why I was hopeful this would work out nicely. So I kept going. Just before the third input, the state looks like:

w = I2
x = 1
y = (+ I2 16)
z = (+ (* (+ I1 2) 26)
       I2
       16)

which still looks quite nice.

Just before the 6th input, though, things are starting to get messy:

w = I5
x = (== 0 (== I5 (- I4 8)))
y = (* (== 0 (== I5 (- I4 8)))
       (+ I5 1))
z = (+ (* (+ (* (+ (* (+ I1 2) 26)
                   I2
                   16)
                26)
             I3
             9)
          (+ (* 25
                (== (== (- I4 8) I5) 0))
             1))
       (* (+ I5 1)
          (== (== (- I4 8) I5) 0)))

At that point I decided to stop trying to do this manually and start writing code for it instead. I started with just turning the raw code into algebraic expressions.

(defn to-expr
  [instrs]
  (reduce
    (fn [acc instr]
      (match instr
        [:inp r] (-> acc
                     (assoc r [:inp (:input-count acc)])
                     (update :input-count inc))
        [:add _ [:lit 0]] acc
        [:add r1 [:lit n]] (update acc r1 (fn [prev] [:add prev [:lit n]]))
        [:add r1 [:reg r2]] (update acc r1 (fn [prev] [:add prev (acc r2)]))
        [:mul r1 [:lit 0]] (assoc acc r1 [:lit 0])
        [:mul r1 [:lit 1]] acc
        [:mul r1 [:lit n]] (update acc r1 (fn [prev] [:mul prev [:lit n]]))
        [:mul r1 [:reg r2]] (update acc r1 (fn [prev] [:mul prev (acc r2)]))
        [:div r1 [:lit 1]] acc
        [:div r1 [:lit n]] (update acc r1 (fn [prev] [:div prev [:lit n]]))
        [:div r1 [:reg r2]] (update acc r1 (fn [prev] [:div prev (acc r2)]))
        [:mod r1 [:lit n]] (update acc r1 (fn [prev] [:mod prev [:lit n]]))
        [:mod r1 [:reg r2]] (update acc r1 (fn [prev] [:mod prev (acc r2)]))
        [:eql r1 [:lit n]] (update acc r1 (fn [prev] [:eql prev [:lit n]]))
        [:eql r1 [:reg r2]] (update acc r1 (fn [prev] [:eql prev (acc r2)]))))
    {:w [:lit 0], :x [:lit 0], :y [:lit 0], :z [:lit 0], :input-count 0}
    instrs))

(Compared to my previous post, I had now slightly changed the parsed format of expressions to make it easier to distinguish between registers and literals in the second argument of two-argument opcodes.)

Run until just before the second inp instruction, this yields (just for :z):

(->> input
     (take 18)
     to-expr
     :z)
[:add [:mul [:lit 0]
            [:add [:mul [:add [:lit 0] [:lit 25]]
                        [:eql [:eql [:add [:mod [:add [:lit 0] [:lit 0]]
                                                [:lit 26]]
                                          [:lit 10]]
                                    [:inp 0]]
                              [:lit 0]]]
                  [:lit 1]]]
      [:mul [:add [:add [:lit 0] [:inp 0]]
                  [:lit 2]]
            [:eql [:eql [:add [:mod [:add [:lit 0] [:lit 0]]
                                    [:lit 26]]
                              [:lit 10]]
                        [:inp 0]]
                  [:lit 0]]]]

Which is, uh, nice, I guess, but a bit of a far cry from my manual determination of [:add [:inp 0] [:lit 2]].

So I needed to add some simplifications. Some of them are obvious: we literally have [:add [:lit 0] [:lit 0]] in there. Some may be less obvious; we'll get to those later. This kind of modification on this type of tree is, in my experience, best handled by a combination of core.match and clojure.walk (specifically postwalk, in this case):

(ns t.day24
  (:require [clojure.core.match :refer [match]]
            [clojure.walk :as walk]))

This lets us write a simplification function like this:

(defn simplify
  [expr]
  (walk/postwalk
    (fn [op]
      (match op
        [:add [:lit 0] [:lit 0]] [:lit 0]
        :else op))
    expr))

In case you're not familiar with either match or postwalk, here's how to read that. The match macro is shaped like case: the first argument is a value we are going to compare against a number of conditions, and each subsequent pair of arguments is a condition followed by a result.

Conditions are "matched" against the given value. In this simple case, the matching will be done by equality: if the given value, op, is exactly [:add [:lit 0] [:lit 0]], the function will return [:lit 0].

The match macro admits a default case with the special :else condition, to mirror the behaviour of core constructs like cond.¹

The postwalk function is going to recursively traverse all Clojure data structures and, when going back up (hence the "post" in "postwalk"), will apply the given function, replacing the node by the function result. One important consequence of that is you can assume, when writing your postwalk rules, that the children of the current node have already been transformed.

So in this case, the simplify function will replace [:add [:lit 0] [:lit 0]] with just [:lit 0], and leave all other nodes unchanged. Ran on the same first sequence of input (stopping just before the second inp), we now get:

(->> input
     (take 18)
     to-expr
     :z
     simplify)
[:add [:mul [:lit 0]
            [:add [:mul [:add [:lit 0] [:lit 25]]
                        [:eql [:eql [:add [:mod [:lit 0] [:lit 26]]
                                          [:lit 10]]
                                    [:inp 0]]
                              [:lit 0]]]
                  [:lit 1]]]
      [:mul [:add [:add [:lit 0] [:inp 0]] [:lit 2]]
            [:eql [:eql [:add [:mod [:lit 0] [:lit 26]] [:lit 10]] [:inp 0]]
                  [:lit 0]]]]

which is not much better quite yet, but now we have an easy way to add new simplification rules. For example, we can compute additions when both inputs are literals (or have been simplified to literals), by adding this line to our simplify function:

[:add [:lit n1] [:lit n2]] [:lit (+ n1 n2)]

This is where match departs from case: whereas case is always looking for and exact match, match can abstract over some components of the structure we're matching, and give them a name. In this case, it allows us to grab the two integers buried in these nested vectors.

We also know that adding 0 is always a no-op, as is multiplying by 1, and that multiplying anything by 0 yields 0, so we don't need to compute that thing. These can all be encoded quite directly:

(defn simplify
  [expr]
  (walk/postwalk
    (fn [op]
      (match op
        ;; removed as it's a special case of the next one
        ;; [:add [:lit 0] [:lit 0]] [:lit 0]
        ;; compute additions when both parts are literals
        [:add [:lit n1] [:lit n2]] [:lit (+ n1 n2)]
        ;; adding 0 is a no-op, on both sides
        [:add exp [:lit 0]] exp
        [:add [:lit 0] exp] exp
        ;; multiplying by 1 is a no-op, on both sides
        [:mul exp [:lit 1]] exp
        [:mul [:lit 1] exp] exp
        ;; multiplying by 0 yields 0
        [:mul [:lit 0] _] [:lit 0]
        [:mul _ [:lit 0]] [:lit 0]
        ;; else, keep unchanged
        :else op))
    expr))

and we now get a much nicer expression:

(->> input
     (take 18)
     to-expr
     :z
     simplify)
[:mul [:add [:inp 0] [:lit 2]]
      [:eql [:eql [:add [:mod [:lit 0] [:lit 26]] [:lit 10]]
                  [:inp 0]]
            [:lit 0]]]

We're not quite there yet, but we're not far off. Looking at this expression, we can see the rules we need to add. First, we know that mod 0 x is always zero. That's easy enough to encode. That will yield an addition between literals, and since we apply our simplifications in postwalk order, the corresponding rule on additions will kick in. Adding:

[:mod [:lit 0] exp] [:lit 0]

to our rules yields:

(->> input
     (take 18)
     to-expr
     :z
     simplify)
[:mul [:add [:inp 0] [:lit 2]]
      [:eql [:eql [:lit 10] [:inp 0]]
            [:lit 0]]]

We're getting close.

Now, when I resolved this manually, I only had the addition part of this expression. How did I get rid of the multiplication? My reasoning was this:

• Inputs are known to always be between 1 and 9.
• Therefore, [:eql [:lit 10] [:inp 0]] is always going to be false, i.e. 0.
• We then compare it to 0, so that yields 1.
• We can fall back on an existing rule: multiplying by 1 is a no-op.

How can we encode that? A simple approach here would be to go directly for:

[:eql [:lit n] [:inp _]] (if (<= 1 n 9) op [:lit 0])
[:eql [:lit n1] [:lit n2]] [:lit (if (== n1 n2) 1 0)]

and we now get our happy result:

(->> input
     (take 18)
     to-expr
     :z
     simplify)
[:add [:inp 0] [:lit 2]]

Moving on to bigger chunks of the input, here's what we get just before the third inp:

(->> input
     (take 36)
     to-expr
     :z
     simplify)
[:add [:mul [:add [:inp 0] [:lit 2]]
            [:add [:mul [:lit 25]
                        [:eql [:eql [:add [:mod [:add [:inp 0] [:lit 2]]
                                                [:lit 26]]
                                          [:lit 15]]
                                    [:inp 1]]
                              [:lit 0]]]
                  [:lit 1]]]
      [:mul [:add [:inp 1] [:lit 16]]
            [:eql [:eql [:add [:mod [:add [:inp 0] [:lit 2]] [:lit 26]]
                              [:lit 15]]
                        [:inp 1]]
                  [:lit 0]]]]

This is, again, quite a bit more complex than my handcrafted simplifications. What are we missing? When looking at this, I can tell that [:add [:inp 0] [:lit 2]] is always going to be smaller than [:lit 26], so I can simplify that :mod expression. But how do I know that? Well, I'm computing the range of possible values for the first argument of :mod, and if that range is contained by the range of 0 to the second argument of :mod (assuming that one is known), then I can consider the mod operation as a no-op and simplify it.

At this point here's how it could work:

(defn compute-range
  [op]
  (match op
    [:add e1 e2] (let [r1 (compute-range e1)
                       r2 (compute-range e2)]
                   [(+ (apply min r1)
                       (apply min r2))
                    (+ (apply max r1)
                       (apply max r2))])
    [:mul e1 e2] (let [r1 (compute-range e1)
                       r2 (compute-range e2)]
                   ;; we're not dealing with negative numbers
                   ;; yet, but we should at some point
                   [(* (apply min r1)
                       (apply min r2))
                    (* (apply max r1)
                       (apply max r2))])
    [:lit n] [n]
    [:inp _] [1 9]))

(defn simplify
  [expr]
  (walk/postwalk
    (fn [op]
      (match op
        ;; eliding all the other rules for brevity
        [:mod exp [:lit n]] (let [[m M] (compute-range exp)]
                              (if (<= 0 m M n)
                                exp
                                op))
        :else op))
    expr))

With this additional rule, we get:

(->> input
     (take 36)
     to-expr
     :z
     simplify)
[:add [:mul [:add [:inp 0] [:lit 2]]
            [:add [:mul [:lit 25]
                        [:eql [:eql [:add [:add [:inp 0] [:lit 2]]
                                          [:lit 15]]
                                    [:inp 1]]
                              [:lit 0]]]
                  [:lit 1]]]
      [:mul [:add [:inp 1] [:lit 16]]
            [:eql [:eql [:add [:add [:inp 0] [:lit 2]] [:lit 15]]
                        [:inp 1]]
                  [:lit 0]]]]

The same reasoning can be applied to simplify :eql nodes: if we can compute a range for both arguments (which we usually can), and they don't intersect, we know the result is always going to be 0.

I spent a lot more time adding more and more instructions to my input, looking at the resulting expression, and trying to come up with algebraic simplifications I could make. For example, here's a slightly more complicated one:

(:or [:div [:add [:mul exp [:lit m1]] x] [:lit m2]]
     [:div [:add x [:mul exp [:lit m1]]] [:lit m2]]
     [:div [:add [:mul [:lit m1] exp] x] [:lit m2]]
     [:div [:add x [:mul [:lit m1] exp]] [:lit m2]])
(let [[m M] (compute-range x)]
  (if (and (== m1 m2)
           (<= 0 m M (dec m1)))
    exp
    op))

If we multiply an expression by \(n\), then add something smaller than \(n\), and then divide by \(n\) again (with an integer division), what we added is lost and thus can be discarded in advance. There's a corresponding simplification for mod: if we multiply by \(n\), add something smaller than \(n\), then apply a mod n, what we're left with is always going to be that thing we added, and the thing we multiplied can fall off.

(The :or syntax is a match feature that lets one specify multiple patterns leading to the same result. I'm using it here to fake an understanding of commutativity.)

After a while, though, I ran out of ideas for how to simplify the expressions I got, and the ones I did get for the full input were still way too large for me to comprehend, or gain any insight from.

So I stopped working on this for a while. Like an hour or so. Then I had an epiphany.

Finally, a workable idea

Many of the advanced simplifications I came up with depended in some way on this notion of computing the range of possible values for subexpressions. And, while at first I'd gotten away with just handling a subset of intructions in compute-range, I'd quickly gotten to the point where it was handling all of the (admittedly not very large) instruction set.

So what if I just computed the range of the entire expression?

I cleaned my slate for the, what, fifth time? And started over with just my parse function. That expression non-sense was clearly a dead end, but it did give me, for the first time, an idea that seemed like it might work in my head.

Here's what the plan was: if I can compute a range based on a range, I can walk down all of the instructions, keeping as my state not the value of each register, but its range. When I reach the end of the instructions, I can look at the range of the :z register. The beauty of that is that, if I can work on everything as a range, I can also consider my inputs as variable ranges. Going back to my brute force approach, if I now want to check whether 989 is a good prefix for my final answer, I can check that by running through all of my instructions once, using the input ranges [9 9], [8 8], [9 9], followed by eleven times [1 9], and check if 0 is still in the resulting range. If it's not, I have just eliminated \(9^{11}\) possibilities. By walking through my instructions once.

Here's how that works. First, we need a function that takes in a list of input ranges and a list of instructions, and returns the output range for the :z register:

(defn compute-range
  [instr inputs]
  (loop [instr instr
         inputs inputs
         state {:w [0 0], :x [0 0], :y [0 0], :z [0 0]}]
    (if (empty? instr)
      (:z state)
      (let [op (first instr)]
        (if (= op [:inp :w])
          (recur (rest instr)
                 (rest inputs)
                 (assoc state :w (first inputs)))
          (recur (rest instr)
                 inputs
                 (match op
                   [:add r [:lit n]]
                   (update state r (fn [[m M]] [(+ m n) (+ M n)]))
                   [:add r1 [:reg r2]]
                   (update state r1 (fn [[m1 M1]]
                                      (let [[m2 M2] (get state r2)]
                                        [(+ m1 m2) (+ M1 M2)])))
                   [:mul r [:lit n]]
                   (update state r (fn [[m M]]
                                     (sort [(* m n) (* M n)])))
                   [:mul r1 [:reg r2]]
                   (update state r1 (fn [[m1 M1]]
                                      (let [[m2 M2] (get state r2)
                                            prods (for [m [m1 M1]
                                                        n [m2 M2]]
                                                    (* m n))]
                                        [(apply min prods)
                                         (apply max prods)])))
                   [:div r [:lit n]]
                   (update state r (fn [[m M]]
                                     (sort [(quot m n) (quot M n)])))
                   [:mod r [:lit n]]
                   (update state r (fn [[m M]]
                                     (if (or (> (- M m) n)
                                             (> (rem m n) (rem M n)))
                                       [0 (dec n)]
                                       [(rem m n) (rem M n)])))
                   [:eql r [:lit n]]
                   (update state r (fn [[m M]]
                                     (cond (= m n M) [1 1]
                                           (<= m n M) [0 1]
                                           :else [0 0])))
                   [:eql r1 [:reg r2]]
                   (update state r1 (fn [[m1 M1]]
                                      (let [[m2 M2] (get state r2)]
                                        (cond (< M2 m1) [0 0]
                                              (< M1 m2) [0 0]
                                              (= m1 M1 m2 M2) [1 1]
                                              :else [0 1])))))))))))

This is a bit long, but there's really nothing new: we just compute the possible range based on the range of each argument. There's no need for recursive calls in computing the ranges because we're now working directly with concrete values, not abstract expressions.

Addition is the simplest one; multiplication could change order based on signs, as could division; and mod and eql are a bit more tricky, but hopefully still readable.

This code is precise enough that, given only single-digit ranges, it will output a single-digit range, too.

Now, we can just brute force our way to a solution:

(defn solve
  [instr size target reverse?]
  (let [h (fn rec [fixed-input]
            (let [input (take size (concat fixed-input (repeat [1 9])))
                  [m M] (compute-range instr input)]
              (cond (and (= (count fixed-input) size)
                         (== m M target))
                    (->> fixed-input (map first) (apply str) Long/parseLong)
                    (or (= (count fixed-input) size)
                        (not (<= m target M)))
                    nil
                    :else
                    (->> (range 9)
                         (map inc)
                         ((fn [s] (if reverse? (reverse s) s)))
                         (map (fn [n] (conj fixed-input [n n])))
                         (some rec)))))]
    (h [])))

where size is the number of inp instructions, target is 0 and reverse? is true for part 2 and false for part 1.

This is very much just trying every single number recursively. But it completes for part one in about 3s, and for part 2 in about 200s. And, unlike last time, it knows when it's done.

This is a very naive implementation of this approach, of course, and it could be made a lot faster. I'm still working on that. I currently have it down to just under 3s on part 2 (and around 150ms on part 1). That may or may not turn into a future post.

One point I will mention on that effort though: it may look like I wasted a lot of time on other approaches before getting to this one. But it wasn't really wasted, was it? On the one hand, it's only because I started working on this wacky, clearly-doomed² idea of reducing the instructions to an expression that I got my final idea at all. On the other hand, pretty much every single idea I've explored in this journey has been useful in optimizing this approach so far.

Conclusion

I really like the approach I eventually came up with, compared to all the other approaches I've seen since. I obviously didn't want to see any other solution until I'd come up with my own, but since then I've talked to a few friends who also did AoC, as well as read a few blogs online.

The reason I like my approach best is because I came up with it, so I want to rationalize it being better. The way in which I rationalize it at the moment is that, out of all the approaches I've seen so far, it's the only one that requires no assumption on the specific program we get as an input. It's entirely based on understanding just the instruction set itself.

I hope you've enjoyed reading through my meanderings, and that you've learned something from it. Maybe a programming technique you weren't aware of, maybe some lesson in tenacity and how creativity can work, or maybe just that I'm weird and the way I think makes no sense to you.