Advent of Code 2024 - Day 17Chronospatial Computer

| Problem statement | Source code | Tags: VMManual inspectionBitwise operationsPuzzle

This problem pays tribute to 2018 day 6 (unimplemented).

Part 1

Not much to say. After IntCode, this is just another assembly language to parse and execute.

Part 2

This problem reminds me of 2021 day 24, where we also have to stare at assembly and figure out some pattern, so here it is.

bst %a    # B = A & 0b111
bxl $X    # B = B ^ X
cdv %b    # C = A >> B
bxl $Y    # B = B ^ Y
bxc $4    # B = B ^ C
out %b    # output B & 0b111
adv $3    # A = A >> 3
jnz $0    # If A != 0, loop

I'm redacting X and Y because they are personalized. Anyway, this code is just the following in C (because OCaml is terrible at describing bitwise operations):

do {
    int b = a & 0b111;
    int c = a >> (b ^ x);
    b = b ^ x ^ y ^ c;
    printf("%d,", b & 0b111);
    a = a >> 3;
} while (a != 0);

Even simpler:

do {
    int ao = a & 0b111; // Last 3 bits of a
    printf("%d,", ((a >> (ao ^ x)) ^ a ^ x ^ y) & 0b111);
    a = a >> 3;
} while (a != 0);

Let's assume x = 1, y = 2 (they aren't for my input). Denote the bits of a from lowest to highest (at this particular iteration) as [a0], [a1], etc. The output is then:

The expected output is:

2,4,1,X,7,5,1,Y,4,4,5,5,0,3,3,0

Since I want to find the smallest a, I should start with the most significant bits and work our way down. The last output is 0, and I can pick all rows in the table that don't contain any 1 bits. Since higher bits than the MSB are necessarily 0, the only solution is ao = 011. That's the highest octet of a. Now I can pick the next octet equipped with this knowledge, and so on. Sometimes I may have multiple choices, and I use a DFS to figure out the first valid solution.

In my code, I literally built up this table by precomputing (a >> (ao ^ x)) ^ ao ^ x ^ y for every value of ao, using a bit_info data structure:

(* For a given octet in a, what is the corresponding output? *)
type bit_info =
  (* A bit higher than this octet. The int is the offset from the last known bit
  (we determine a from the highest bit); true = not inverted.  *)
  (* Ex: (true, 2) => the output bit corresponds to the 3rd lowest known bit *)
  | Symbol of bool * int
  | Bit of int (* 1 or 0 *)

let info =
  [ 0; 1; 2; 3; 4; 5; 6; 7 ]
  |> List.map (fun i ->
      let a0, a1, a2 = split_bits i in
      shift_by (i lxor x) (a0, a1, a2)
      |> xor_bits [ Bit a2; Bit a1; Bit a0 ]
      |> xor_bits [ Bit x2; Bit x1; Bit x0 ]
      |> xor_bits [ Bit y2; Bit y1; Bit y0 ])
  |> List.mapi (fun i l -> (i, l))

Then, for each output number, I find all possibilities of ao that's compatible with the current a value, and try each one. The tentative_a is the bits of a that we have already determined (starting from the least significant determined bit, up to the most significant determined bit which is also the MSB of the whole a).

let rec search_a tentative_a info prog =
  match prog with
  | [] -> Some tentative_a
  | out :: rest ->
      let out0, out1, out2 = split_bits out in
      info
      |> List.filter (fun (_, inf) ->
          List.for_all2 (is_bit_compatible tentative_a) [ out2; out1; out0 ] inf)
      |> List.map fst
      |> List.find_map (fun ao ->
          let ao0, ao1, ao2 = split_bits ao in
          let tentative_a' =
            Array.append (Array.of_list [ ao0; ao1; ao2 ]) tentative_a
          in
          search_a tentative_a' info rest)

The last step is just to go through hoops to convert this bit array into an integer.

search_a (Array.make 0 0) info (List.rev (Array.to_list prog))
|> Option.get |> Array.to_list |> List.rev
|> List.fold_left (fun acc bit -> (acc lsl 1) + bit) 0
|> Printf.printf "%d\n"