This is the fourth article in a series covering Advent of Code 2024 in Rust.

Day 21: Keypad Conundrum

I loved the presentation of this puzzle, where unfortunately rooms keep being inaccessible and we need a recursive mess of robots controlling robots typing on keypads. But boy, it took me forever to solve this one, both because there are lots of smaller sub-problems to solve, but mainly because I struggled for a long time to find the right angle of attack. Follow me down a few interesting dead ends, dear reader.

The first part of the puzzle asks to type a code on a numeric keypad like the below by giving a robot directional instructions via a directional keypad (shown below) via two more robots that that type on directional keypads:

+---+---+---+
| 7 | 8 | 9 |      If we want to type 029A ...
+---+---+---+        
| 4 | 5 | 6 |      ... a possible direcitonal sequence is 
+---+---+---+          <A^A>^^AvvvA
| 1 | 2 | 3 |        
+---+---+---+
    | 0 | A |
    +---+---+

    +---+---+       And to type <A^A>^^AvvvA ...
    | ^ | A |       
+---+---+---+       ... on this keypad, a possible sequence is:
| < | v | > |           v<<A>>^A<A>AvA<^AA>A<vAAA>^A
+---+---+---+    

                    And we  repeat that one more time with the
                    same directional keypad.

The puzzle asks to find a shortest sequence of button presses at the top of the whole sequence.

I also played the usual game of predict the twist and thought about ideas like adding more stacked keypads, a longer code, which both mainly seem to increase the factors blowing up the search tree size. I also considered some twist that would change the layout of the keypads, which would scramble the basic building blocks.

Brute force

If we start from the numeric keypad there isn’t much variation that’s possible. The order of the code is fixed, and with only straight movements, the only choice we have is in what order we handle vertical/horizontal movement(s) for cases where we are moving diagonally:

+---+---+---+
|   | + - 9 |  Moving from 2 to 9, we have three possible paths:
+---+-|-+-|-+        ^^>    2x up and 1x to the right
|   | + - + |        >^^    1x right and 2x up
+---+-|-+-|-+        ^>^    right, up, right
|   | 2 --+ |        
+---+---+---+
    |   |   |
    +---+---+

I started by implementing brute force algorithms to find all the possible paths between two keys on both keypad types. I started with permutations (i.e., build up a single result like ^^v and then compute all permutations). But that makes things hard with the invalid positions. So I instead opted for an iterative algorithm that built up a list of all paths of length N (starting with the empty path), growing each path by all possible moves taking us closer to the goal in each round. To then move up on the directional keypads, I toyed with a simple greedy approach, taking an arbitrary shortest path at each level. But that fails because our choice of path at one level might yield a longer path at the level above. For example:

The first solution has a longer key sequence at the top, even though
the sequence at level 1 is the same length:

0: <A
1: <v<A>>^A
2: <v<A>A<A>>^AvAA<^A>A

0: <A
1: v<<A>>^A
2: <vA<AA>>^AvAA<^A>A

The second solution is shorter because `v<<A` is a better choice at level
1 than `<v<A`.

Insights

Working the problem for a while, I had two insights that helped. First, I thought about how might our choice of path would translate to needing a longer sequence on the (directional) keypad above. It occurred to me that

1. We should minimize moves on the keypad above. For example ^<^ will need us to move twice (from ^ to < and back to ^), while >^^ or ^^> will only require a single move.

2. We might end up closer to the next key we need. For example vv>A will require fewer moves than >vvA. It takes two moves from v to A, but only one from > to A.

The first case is simple to translate into a heuristic. We should always prefer to move as far in one direction in one go as possible, creating “runs” like vvv in the sequence (that will not require moves on the keypad above). The second case is trickier, but even #1 means we are now down to at most 2 possible paths between two keys (depending on which direction we start with). So our search tree has become a binary tree.

The other realization I had was that we didn’t need to solve the whole code sequence as a monolithic problem. Each time we are pressing a key on the bottom-most (numeric) keypad, we must be pressing the A key on all the directional keypads above. There creates a “synchronization point” where the history becomes irrelevant. For example, how we arrived at the 0 key (from our start at A) has no bearing on the best key sequence for moving from 0 to 2. So the problem boils down to finding an optimal sequence of key presses for each pair of keys in the code and we can then just concatenate these. Using these insights, I could solve the first problem in a brute force way.

<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>A
                 |
          v<<A>>^A<A>AvA<^AA>A<vAAA>^A 
                 |
                <A^A>^^AvvvA
                 |
              (A)029A

The second part of the problem asks to solve the same issue with 25 directional keypads (ha, I knew it! ;). At this point, the problem is clearly dominated by how we choose to move on the directional keypads, so I started to wonder about those. I began to look more closely at all the possible movement patterns on the directional keypad. I tabulated all possible moves, and what shortest / longest paths they would expand to at a couple of levels up:

This yields some disheartening examples, where we find that a choice giving us a longer sequence at level N yields a shorter sequence at level N+1, another indication that a naive search that just picks the shortest sequence at each level can’t work:

v> [2]   =>   <vA>A [5]   =>      v<<A>A>^AvA^A [13]
>v [2]   =>    vA<A [4]   =>     <vA>^Av<<A>>^A [14]

v< [2]   =>   <vA<A [5]   =>  v<<A>A>^Av<<A>>^A [17]
<v [2]   =>  v<<A>A [6]   =>     <vA<AA>>^AvA^A [14]

A failed approach: anchor on single moves

But the problem is clearly recursive in nature. Each time we need to move between two keys on the directional keypad, that movement will translate to a sequence of the kind <move>A[<move>A[<move>A]] at the next level, where <move> is again one of our basic moves from the table above. There are 6 moves where we can choose between key sequences, and based on the table we can get an intuition which of them seems to expand worse after a couple of steps. So I figured I could try a heuristic that would simply pick the “best” alternative for each choice (the one that yielded the shortest path after 3 expansions) and would recursively apply that choice.

But there were two issues with this approach. First, what move we need to pick depends on the position we’re at on the underlying keypad, so there is no good unit along which we can decompose the problem. And, second, actually expanding the full sequence gets very slow at 25 levels deep. We can see this if we expand the first move (from A to 8) in the code 879A, which quickly yields strings several megabytes long:

Examining 879A
  0: 4
  1: 9
  2: 19
  3: 47
  4: 109
  5: 273
  6: 675
  7: 1687
  8: 4209
  9: 10505
  10: 26263
  11: 65587
  12: 163933
  13: 409517
  14: 1023351
  15: 2556855
  16: 6388837
  17: 15963357
  18: 39886855
  19: 99663535

  // Things were getting very slow at this point

Grammars & dynamic programming

This problem smelled of something grammar-like, where we can recursively replace shorter movement sequences with the longer ones one level above. After several false starts, it took drawing a few examples on paper to realize the “synchronization point” idea from earlier didn’t only apply globally, but also locally for each keypad. By focusing on sequences ending on the A key on a given keypead, we remove position from the equation!. For example, we can see the “movement atom” ^>A expanding to the same sequence of <Av>A^A on the keypad at each level here (intuitively there is an optimal way to use the keypad above to press certain keys followed by A on the keypad below, and when we’re back at A, it’s a blank slate again).

        vA

        <vA^>A
           ---
            |
            +----------+
                       |
                       v
        v<<A>A^>A  [<Av>A^A]
              ---
               |
               +----------+
                          |
                          v
        <vA<AA  vA^A  [<Av>A^A]  ...

So we can turn the problem into a substitution grammar with rules like the below (which we’ll apply 25 times), where each rule maps a single “atom” (some movements followed by a single A) to a new sequence of atoms for the keypad above:

vA  ::= <vA ^>A
^>A ::= <A v>A ^A
...

And we can resort to dynamic programming to deal with the wide fanout. Instead of actually expanding the string in full, we can memoize a function len(seq, level) that will tell us how long a given sequence is at a given level. If we assign level 0 to the topmost (directional) keypad we type on and level 26 to the numeric keypad at the bottom, we can compute the length of a given sequence on the level above

With each grammar rule mapping an atom A to sub-atoms A1-AN
we can create a function suitable for dynamic progamming:

A ::= A1 A2 ...

len(A, 0) = |A|
len(A, N) = len(A1, N-1) + len(A2, N-1) + ...

For example:

vA  ::= <vA ^>A

len("vA", 2) = len("<vA", 1) + len("^>A", 1)

Peeking

With these approaches I had a program that quickly produced a result… that was wrong >.<. I verified that applying the approach to the first problem yielded the right result (yes), but I somehow still didn’t get the right result for the second one. While I generally made it a point to stay clear of looking up other solutions for this series, I felt I had solved the interesting bits so I decided to look around at other’s solutions and I learned a few things.

As explained in this post, we should prefer moves in the order <, v, ^, >, which gives us a heuristic for the second intuition earlier from the article. The post points to another place that nicely explains this choice with the fact that it’s benefical to first press the keys furthest from A (especially <) so we can then press other keys on the way back. I updated my moveset with these rules, but still didn’t get an accepted result.

So I ended up benchmarking against another existing solution in python. After futzing around for a while aligning the memoization tables, I found both programs were computing the same values for the keypad movement atoms at all levels (yay), but that the python program computed a different top-level score. After a while debugging, I found that I had a bug in my code that walked over the invalid keypad position while mapping the numeric keypad moves like ^^^< to directional keypads. After fixing that bug, I finally got the right solution.

Day 22: Monkey Market

In this puzzle we’re asked to predict the secret numbers of buyers on the Monkey Exchange Market, in order to procure an absurd number of bananas to buy back the McGuffin of our story.

The first part of the puzzle revolves around a pseudo-random number generator. The function given for the sequence is below:

n_x+1 = h(g(f(n_x)))
f(x) = (x ^ (x * 64)) % C
g(x) = (x ^ (x / 32)) % C
h(x) = (x ^ (x * 2024)) % C

where
  ^ is XOR
  % is modulo
  C is 16777216

I suspected the twist here might end up being something a bit similar to Day 17’s Chronospatial Computer where the second part of the puzzle asks for elements so far along in the sequence that we cannot efficiently compute the answer and instead needed to reason about the sequence behaviour, so I toyed around a bit with this.

I noticed that all the operands are powers of two (16777216 is 2**24), so we can also view the PRNG function in terms of bit manipulations, where the multiplication/divison shift the bits and where the modulo operation simply keeps each value clamped to the 24 least-significant bits. So we can implement the PRNG function like this in Rust:

fn prng(i: usize) -> usize {
    const MASK: usize = 0x0ffffff;  // 16777216 - 1
    let f = (i ^ (i << 6)) & MASK;
    let g = (f ^ (f >> 5)) & MASK;
    let h = (g ^ (g << 11)) & MASK;
    h
}

I left things there and computed the 2000-th number by applying that function in a loop, which solved the first part of the problem.

Second part

The second part took a different turn than expected. It asked to look only at the least-significant (decimal) digit of each sequence and the delta encoding between each of them. This yields sequences like shown below, where the digit is the sell prices each buyer is currently offering. (each buyer will buy at most once). We’re instructed to buy as many bananas as possible using an “interpreter” monkey that can be instructed to watch for a sequence of four consecutive price changes (e.g., -1 0 0 2) and will buy from the current seller when it observes these before moving on to the next seller:

                                V
Buyer 1:   3  0  6  5  4  4  4  6  4  4  2
(delta)      -3  6 -1 -1  0  0  2 -2  0 -2 
                      -----------
                                                     V
Buyer 2:   1  5  9  3  3  2  5  7  6  6  8  7  7  7  9
(delta)       4  4 -6  0 -1  3  2 -1  0  2 -1  0  0  2 
                                           -----------

...

With the sequence "-1  0  0  2" our interpreter would sell
to Buyer 1 for 6 bananas and to Buyer 2 for 9.

The problem them was to figure out the best 4-digit delta sequence that would lead to our interpreter receiving the maximum number of bananas for our sales. Given we are looking for a single delta sequence I figured it was best to re-map things by the delta sequence. I created a sales Opportunity struct and ran through each buyer’s sequence of numbers creating a map along the lines of the below, which will make it easier to compute the price per sequence:

/// Computes a map of sales opportunities for the given list of buyers.
fn compute_opportunities(buyers: &mut Vec<Buyer>) -> HashMap<DeltaSequence, Vec<Opportunity>> {
  ... 
}

// 4, -1, -4, -2: Opportunity { buyer_no: 1, index: 540, price: 1 }
//                Opportunity { buyer_no: 6, index: 1125, price: 1 }
//                Opportunity { buyer_no: 25, index: 608, price: 0 }
//                Opportunity { buyer_no: 39, index: 1968, price: 1 }
//                ...

// -9, 8, -8, 2:  Opportunity { buyer_no: 21, index: 1699, price: 2 }
//                Opportunity { buyer_no: 98, index: 37, price: 2 }
//                Opportunity { buyer_no: 123, index: 385, price: 2 }
//                Opportunity { buyer_no: 156, index: 1305, price: 2 }
//                ...

What didn’t quite become clear to me from the description was whether we were dealing with a kind of “global time” problem where the interpreter would observe the numbers of all buyers in parallel, and would only look at numbers N+1 from the next buyer after having bought at number N from a given one (which would end up “invalidating” possible buys in the are marked with . below). Or whether each buyer would be looked at in sequence - local time like - where the interpreter would start at number 0 for each buyer. There was a sentence “If the monkey never hears that sequence of price changes from a buyer, the monkey will never sell, and will instead just move on to the next buyer.” that kinda sounded like the latter option, but I wasn’t sure (it sounded almost too easy).

Global time: sellers offer in parallel, we may "miss" some earlier sales
(V demarks a successful sale, we couldn't sell for Buyer 2 at ...)

Buyer 1:   ----------V
Buyer 2:   ...........-----------V


Local time: start at 0 with each seller, we can buy whenever we like

Buyer 1:   ----------V
Buyer 2:   ----V

I tried out the latter option on the example that was given and found that this yielded the right answer. And applying that same problem yielded the right answer for part 2. I wasn’t sure if I should feel elated or disappointed that this problem was comparatively easy after the brutal difficulty spike of day 21, but I did feel energized to jump into problem 23 next.

Day 23: LAN Party

Day 23 is a graph problem happening in an undirected graph, representing a fictional network of computers for a LAN party. Computers are identified by 2-letter names like aq or ta and the input is simply a list of edges:

kh-tc
qp-kh
de-cg
ka-co
...

The first part of the puzzle asks us to find groups of 3 (fully) connected computers. In other words, we’re looking for all complete K3 subgraphs in the network. We’re asked to only consider triples where at least one machine’s name starts with a t, e.g., co,de,ta.

The graph is relatively small with ~500 machines/nodes, so we could probably do something with an adjacency matrix. But I chose to read the edges into an adjacency-list like representation where I simply stored a set of connected computers for each machine in the network, which allows a reasonably efficient way to look up if two given machines are connected and allows us to scan across all machines in the network:

/// A network of connected machines.
struct Network {
    /// Stores an adjacency "list" for each machine in the network.
    neighbors: HashMap<Machine, HashSet<Machine>>,
}

It took me a moment to figure out a good way to approach finding the complete subgraphs. I considered brute force algorithms like simply enumerating all possible triplets and performing a connectivity check, but that felt expensive at ~23M possibilities to draw 3 machines from 520. Given we only care about subgraphs that contain a machine starting with a t, we can obviously make the problem simpler by starting a search there. I considered a graph search approach (where we can stop as soon as we reach the starting node again, and could prune paths > 3 nodes), but these all felt too complex for what we needed to do here. After drawing a few example graphs, I realized I could operate with set intersections in the neighbors data structure.

Each K3 is a “triangle” of connected machines. So whenever we have an edge between two machines, the question simply becomes to find all third machines that both of them are connected to. So my solution became to scan over all machines starting with a t, look each of their neighbors and then intersect their adjacency sets.

      ef      zz        tr
      .     .     ~     ~
       .  .         ~  ~
       ab ---------- cd
       .  .          ~ ~
      .     .     ~     ~
    gh        yy          fs

So if we have

  ab: {cd, ef, gh, zz, yy}   // Set shown with .
  cd: {ab, tr, fs, zz, yy}   // Set shown with ~

we can intersect the two sets to find the common neighbors {zz, yy},
giving us the triples {ab,cd,zz} and {ab,cd,yy}

One issue with this approach is that it will create duplicate output(s). In the above example we would both consider the edge ab-cd starting at node ab and later again at node cd. I figured I could either remove edges we had considered (kind of the inverse approach of how some cycle detection algorithms work) or we could simply de-dupe the output in the end. I tried the removal idea, but that ended up giving me a too low result, and I think that’s because we might be removing groups that have multiple nodes with t in them too aggressively. I moved to deduping via a set and that gave me the right answer.

For the second part we’re asked to find the largest complete (sub-)graph. It’s clear that a single set intersection won’t cut it for that problem. I thought about graph searches or a Union Find like approach, but it’s hard to satisfy the “fully connected” property with them. After a while I realized that we can combine the “iteratively grow smaller sets/graphs” idea of Union-Find with my earlier set approach. Looking at what we did for the first part, we grew a fully connected 2 graph node - K2 - into a K3 by finding another node that had edges to all nodes in the K2. And we can continue this process. A KN-1 we have found, can be grown into KN by adding a node that has edges to all of the nodes of KN-1 (the dotted edges below):

This nicely illustrates why a KN has (N-1)! edges. Each node we add needs to connect to more other nodes, and we’re adding N-1 edges when we grow KN-1 to KN. (N-1)

     *               *. . . *          *-----*  
    . .      =>      |    . .    =>    | \ / |   =>   ...
   .   .             | .    .          | / \ |  
  *-----*            *------*          *-----*
     K2                 K3                K4    

In terms of our “adjacency set” data structure above, we can now use the map in reverse. If we have a KN-1, we can scan down the sets and check which ones contain all the nodes, which then means we can add the node associated with the set (if it isn’t yet in KN-1):

If we have found K2 {ab, cd}, we can scan the sets:

  ab: {...}                         |
  cd: {...}                         V
  ...
  ef: {..., ab, ..., cd, ...}    // contains {ab, cd}, ef not in graph
  ...

=> we now know K3 {ab, cd, ef} exists, and can repeat the process

We do need to be careful about local maxima here, though. Adding the “wrong” node to a graph might preclude us from further growth. Consider the example below, where we start with a K2 {ab, cd} that is actually part of a K4 (dotted lines). But once we grow the graph into {ab,cd,zz} we are stuck in a local maxium as we cannot add ef or gh to the K3 as they lack connections to zz.

         ab      ef
         * . . . *
       / | .   . .
      /  |  . .  .
  zz *   |   .   .
      \  |  . .  .
       \ | .   . .
         * . . . *
         cd      gh

To avoid this problem, we need to maintain a set of graphs and produce all possible extensions of each given graph for each “round” (i.e., in the previous problem, {ab,cd} would need to expand to all of {ab,cd,zz}, {ab,cd,ef} and {ab,cd,gh}). I implemented this approach, starting with the problem input (each edge denotes a K2 we can start with). To avoid the set growing too large, we can prune graphs that no longer grow. We can do this by keeping generations of sets, where we derive a new set of KN graphs from a previous set of KN-1 (which we then discard).

While implementing this I struggled a bit with my data types. I originally wanted to represent each Kn as a HashSet<Machine>, but that would have made the overall set of Kn’s a HashSet<HashSet<Machine>> which doesn’t work as HashSet does not implement the Hash trait, due to the unordered nature of the set. Given I already had a MachineGroup type that internally stored things as a sorted vector, I went with HashSet<MachineGroup> and implemented some glue code to allow checking if a given MachineGroup (aka Kn) was fully contained in a HashSet (so I could implement the label-scanning with my set-based neighbors structure).

This worked out nicely. I was vaguely disappointed that the output didn’t spell something after the co,de,ka,ta example, but it is tricky to find a 26 character sentence that has the right order.

% cat inputs/aoc23.txt | cargo run --release
3380 machine groups of size K2
11011 machine groups of size K3
26455 machine groups of size K4
45045 machine groups of size K5
55770 machine groups of size K6
50622 machine groups of size K7
33462 machine groups of size K8
15730 machine groups of size K9
5005 machine groups of size K10
975 machine groups of size K11
91 machine groups of size K12
1 machine groups of size K13
...

Day 24: Crossed Wires

This puzzle asks to evaluate a bunch of boolean logic gates connected by named “wires”. The input is a graph of AND, OR and XOR gates with the “wires” being edges between their inputs and outputs. With input signals given to a first set of wires, we’re asked to compute the output (which then gets combined into a boolean number).

I saw two fundamental approaches to the problem. On the one hand, we can compute the output in rounds, repeatedly scanning over our gates and computing an output value whenever a gate has two defined inputs. This will eventually converge to the point where no more new outputs can be computed and we can then evaluate the final output. However, given we only actually care about the values of a subset of wires (the wires named z** that make up the output), I figured it would be a better approach to use lazy evaluation and compute the output in “pull mode”, where each wire knows how to “ask” its connected gate for its input and where each gate knows how to ask it’s two connected wires for an input. Here’s the key parts of the code implementing that idea:

/// Our device consisting of connected gates and wires.
struct Device {
    wires: HashMap<String, Wire>,
    gates: Vec<Gate>,
}

impl Device {
    /// Computes the output of the given gate.
    ///
    /// Will recursively compute values for the input wire(s) if needed.
    fn compute_gate_output(&mut self, gate_no: usize) -> Value {
        assert!(gate_no < self.gates.len());
        let gate = &self.gates[gate_no];
        let input_a = gate.inputs[0].clone();
        let input_b = gate.inputs[1].clone();
        let a = self.compute_wire_value(&input_a);
        let b = self.compute_wire_value(&input_b);

        let gate = &self.gates[gate_no];
        gate.compute(a, b)
    }

    /// Computes the value of the given wire.
    ///
    /// If the value is not yet known, will recursively compute values
    /// for the input gate until a label arrives.
    fn compute_wire_value(&mut self, label: &str) -> Value {
        let wire = self.wires.get(label).expect("Unknown wire {label}");
        match wire.value.0 {
            Some(_) => wire.value.clone(),
            None => self.compute_gate_output(wire.input.expect("Wire {label} has no input")),
        }
    }
}

This way we’re sure to only ever compute values we need. And that worked nicely. After some obvious issues with endianness and an off-by-one error in computing the decimal value from the binary representation (first multiply by two, then add the next bit…), I got the right answer for the first part.

Second part

The second part reveals that our network of gates is actually an adder. However, it’s a broken adder because some output wires were swapped between pairs of gates - and it’s our job to find and fix those.

With over 200 gates in my problem, we don’t want to randomly swap (4 pairs of) wires. So we need a way to localize where the problems are. One way to do this would be to render a graph of the adder and do this by visual inspection. But I wondered if we could do something more programmatic, by having inputs that only exercised part of network of gates. If you think about how an adder works it’s very similar to manual addition on paper. We add up from the lowest-significant “digit” and if that overflows we carry things over into the next addition. This has the property that any given (pair of) bits in the input, will only ever influence the immediate bits at or to the left of that position in the output.

   0110 1 .............
 + 0000 1 .............
   ---1 - -------------    <-- The carry in action
   0111 1 .............
        ^
        The result of this addition will only
        influence bits at or to the left of the position
        in the output.

I assumed the network was probably a ripple-carry adder, but the general ideas should also apply to their more fancy block-based brethren.

So, to narrow down what part of the network has wrong connections, we can use inputs with either a single 1 (tests the gates computing the actual sum of two bits) or a single pair of ones (tests the carry) and check if we get the expected output, and we can try this at different bit positions:

    ...010000...         ...010000...     
  + ...000000...       + ...010000...       If we keep the carry from the lower digits to 0
    ------------         ------------       these additions should produce exactly the shown
        1                   10              output (if bits show up elsewhere, there's a mistake)

While thinking about this, it also occurred to me that we can look at the whole graph as a big DAG, and simply ask for each output wire z.. what input wires it will end up evaluating. In a correct network, we would expect that output wire zN would only ever look at input wires x0..N and y0..N.

I ran with the earlier checking idea and that produced some promising intermediate results:

% cat inputs/aoc24.txt | cargo run --release
Checking x
1+0 @ bit 12 shows up at position 13
1+0 @ bit 16 shows up at position 17
...
Checking carries
1+1 @ bit 11 has carryover at 13 (should be 12)
1+1 @ bit 12 has carryover at 12 (should be 13)
1+1 @ bit 15 has carryover at 17 (should be 16)
1+1 @ bit 23 has carryover at 25 (should be 24)
...

Nah: Pruning the graph

I then figured we could combine this idea with the DAG graph idea and try to isolate things to only the subgraph connecting the input/output wires we just identified. I implemented a pruning algorithm that removed all the input/output wires that weren’t showing any errors and then iteratively removed any gates and wires that weren’t connected to anything else. This yielded a small(er) number of possible wires to try and swap.

I then implemented a simple brute-force algorithm that would try swapping each pair of wires on the full device, and would re-run validation. This looked promising, but soon ran into stack overflow issues, as swapping some wires seems to introduce loops (doh…):

Found 62 wires to try and swap: ["hfh", "jqn", "kfc", ..., "wwd"]
Swapping hfh <=> jqn: no effect (22 >= 21)
Swapping hfh <=> kfc: no effect (25 >= 21)
Swapping hfh <=> vjq: no effect (22 >= 21)
Swapping hfh <=> bvg: no effect (22 >= 21)
Swapping hfh <=> nnv: no effect (22 >= 21)

thread 'main' has overflowed its stack
fatal runtime error: stack overflow

After implementing a loop detection algorithm, so I could rule out swaps that produce a broken device, I tried a simply greedy algorithm first, that would swap any pair of output wires, trying to optimize the total number of wrong inputs/outputs. But that runs into weird local minima, where we eventually can no longer fix the device further by performing random swaps:

Inputs/outputs with crossed wires: {"x23", "z29", "z12", ...}
Finding wires connecting wrong inputs/outputs
Found 62 wires to try and swap: ["bvg", "nkh", "kmd", ...]
Swapping kwb <=> z12 brings down crossed wires to 15: {"y24", "x16", "x24", "y15", "x29", "z30", "x23", "y16", "z29", "z24", "z17", "z25", "y23", "y29", "x15"}
Swapping stj <=> wwd brings down crossed wires to 12: {"z25", "z17", "z30", "y23", "x15", "y29", "x23", "z29", "x16", "y16", "x29", "y15"}
Swapping bnk <=> jqn brings down crossed wires to 11: {"y15", "y23", "z25", "x29", "x16", "z17", "x15", "x23", "z30", "y16", "y29"}
...
// Somewhere around 6-8 this hits a dead end, where none of the swaps
// further improve the situation.

Nope: Incremental fixing

Thinking back to the beginning, I figured we should make use of the fact that the carries only ever affect more significant bits, which implies that we should fix the least significant bits first, as we won’t have any side effects from other crossed wires on those. Another way to think of things here is that we can always build an N+1 bit (ripple carry) adder from a working N bit adder that we add one more full adder to. I first tried an approach with deleting the edges and gates again, but that also ran into trouble, making me suspect my algorithm of pruning the graph might have some issues.

Thinking about ways to incrementally fix things, I eventually realized that I could make use of the fact that I had implemented lazy evaluation for the wires, which lets us observe which internal wires actually participate in computing a certain bit of output. This way, we can tell which wires are correct, e.g., if we successfully validated the N least significant output bits, we can mark all the internal wires that were touched as correct. And if we then find an issue with wire N+1, we can focus on only the newly modified wires and swap these with wires whose values we hadn’t yet computed.

I struggled a lot with this approach, as this approach often found multiple swaps that would fix the immediate issue at hand, and again ran into local minima. Sometimes we seemed to be borrowing trouble by swapping a wire with something random from the higher bits, which fixed the issue at hand, but led to problems later. A symptom of this I found is that my solution seemed happy to swap z12 <-> z13, which seemed to fix the immediate issue(s) I was checking for in the lower 12 bits. I realized the issue here was that I was checking individual bits with bit patterns like ...00100..., which of course means we can “borrow” a lot of 0 bits from the higher positions.

Incremental fixing with a search graph

I wondered if I needed to build an actual search tree where we keep multiple interesting swaps and build on each of those. When combined with an approach of both checking the individual bits and overall operations checking all bits, this seemed to look promising, except I seemed to have some issue in my validation functions. In the below output we see that we manage to fix a first error by swapping either z12 <-> kwb, pushing the error from bit 11 to bit 15 (yay), but we later are visiting a machine that is supposed to have the error at bit 29, but the inner check (to discover the part of the machine without issues) claims we have an error at bit 24!

Device has 45 input bits and 222 output wires
Visiting {} w/ first error @ 11
  2^12 - 1  + 1 did not yield a 1 at bit 12
  Found issue at bit 12 (new: {"z12"})
Visiting {("z12", "kwb")} w/ first error @ 15
  2^16 - 1  + 1 did not yield a 1 at bit 16
  Found issue at bit 16 (new: {"gkw", "nkh", "z16", "cmc", "cgn"})
...
Visiting {("wwd", "tgr"), ("z12", "kwb"), ("z16", "qkf")} w/ first error @ 29
  2^25 - 1  + 1 did not yield a 1 at bit 25
  Found issue at bit 25 (new: {"z25", "tgr", "skh"})
...

I realized that my different approaches for testing the whole machine (which involved computing values for all bits, to avoid the “zeros borrowed” issue from earlier) and testing a partial machine (to discover which wires were yet unused) were each blind to certain kinds of errors. I decided I should be more systematic here.

Interlude: truth tables

If we look at a single full-adder, there are three inputs (2 bits to add - x, y and the carry-in - ci) and two outputs (result z and carry out - co). So we can distinguish 8 possible states, the first four without a carry in and the latter four with one.

Given we can’t directly influence the carry value in our device (as we don’t know a priori what wire is the carry in value for a given adder), we have to produce these states with bit patterns in the input (where we set the n - 1 bits both to 1 to produce a carry). So we should test all of:

# Bit additions to test (all values in binary notation)
# The arrows show bit position N that we are testing

 |    |       |
 v    v       v
 0 +  0   =   0
 1 +  0   =   1
 0 +  1   =   1
 1 +  1   =  10        # Trivial carry-in
 01 + 01  =   10       # Trivial carry out
 11 + 01  =  100
 01 + 11  =  100
 11 + 11  =  110

Success

Improving the bit checking almost solve the problem. With that approach, the program found 3 swaps that pushed the error up to bit 29. However, it then got stuck not finding any further improvements:

Device has 45 input bits and 222 output wires
Visiting {} w/ first error @ 11
  Found issue at bit 11 (newly evaluated wires: {"z12"})
  Found 4 swaps that improve the device: [("z12", "vjq"), ("z12", "z13"), ("z12", "kwb"), ("z12", "hnd")]
...
Visiting {("z12", "kwb"), ("z16", "qkf"), ("z24", "tgr")} w/ first error @ 29
  Found issue at bit 29 (newly evaluated wires: {"z30", "ffr", "psc", "fvm", "cph"})
  No swaps found that improve the device

Can you spot the problem? Note that when finding an error at bit 11 the only newly evaluated wire is z12, meaning we don’t consider z11 or any of its inputs as candidates for a swap. The reason for this is that I hadn’t considered that checking bit N will also evaluate the wire zN+1 (to check for the carry).

Fixing that issue was the final breakthrough. Once I had corrected my code to consider both zN and zN+1 and their inputs as candidates for swaps, my program computed the correct solution.

The solution could probably be improved a bit further in some ways:

• Switch to a depth-first search using a priority queue and first evaluating candidates with the best bit error.
• Fix the dumb mistake of swaps being ordered (facepalm…): Found 2 swaps that improve the device: [("jqn", "cph"), ("cph", "jqn")]
• Remove a bunch of repetition in the bit validations.

But I did not explore those and instead jumped to …

Day 25: Code Chronicle

This puzzle presents some “keys” and “locks” with 5 pins each and asks to figure out which keys can(not) fit into given locks by checking if a given key overlaps with a given pin(s) maxium travel.

Lock      Key           Nope, this won't fit (- is the lock, + is the key, X is a conflict)

                        + Overlaps show with sums > 5
                        | +-- Gaps show as sums < 5
                        v v  
05043  +  43402   =    48445
#####     .....        -----
.#.##     .....        .-.--
.#.##     #.#..        +-+--
.#.##     ###..   ==>  +X+--    
.#.#.     ###.#        +X+-+
.#...     ###.#        +X+.+
.....     #####        +++++
                        ^
                        Things overlap here           

The first part simply asks to parse a bunch of keys and locks and to try each pair, reporting how many of them can fit together. With the usual parsing boilerplate out of the way, this boils down to a simple vector addition. I crated a newtype abstraction for the rows of 5 values and defined addition for them, which made this pretty straightforward:

/// Wapper type so we can define operations on the type.
#[derive(PartialEq,Eq,PartialOrd,Ord,Debug,Clone,Hash)]
pub struct Row([usize; 5]);

impl Row {
    pub fn new() -> Row {
        Row([0, 0, 0, 0, 0])
    }
}

impl Add for Row {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Row([
            self.0[0] + rhs.0[0],
            self.0[1] + rhs.0[1],
            self.0[2] + rhs.0[2],
            self.0[3] + rhs.0[3],
            self.0[4] + rhs.0[4],
        ])
    }
}

impl AddAssign for Row {
    fn add_assign(&mut self, rhs: Self) {
        self.0[0] += rhs.0[0];
        self.0[1] += rhs.0[1];
        self.0[2] += rhs.0[2];
        self.0[3] += rhs.0[3];
        self.0[4] += rhs.0[4];
    }
}

impl Row {
    /// Checks if all values in the row are <= v
    fn all_le(&self, v: usize) -> bool {
        for i in 0..self.0.len() {
            if self.0[i] > v {
                return false;
            }
        }
        true
    }
}

#[derive(PartialEq, Eq, Hash)]
pub struct Lock {
    pub pins: Row,
}

#[derive(PartialEq, Eq, Hash)]
pub struct Key {
    pub cuts: Row,
}

impl Key {
    /// Tells if this key fits into the given lock.
    fn fits_into(&self, lock: &Lock) -> bool {
        let combined = self.cuts.clone() + lock.pins.clone();
        combined.all_le(5)
    }
}

At this point I was bracing myself for another really tough nut to crack, given how challenging the second halves of days 21 and 24 were. But it turns out, there is no second half of the puzzle! Instead, the story wrapped up with a bow (!) and after delivering the Chronicle of all the places visited and puzzles solved to Santa, I had wrapped up my first Advent of Code in Rust!