Once again, I used Rust.
Introduction
We need to model a 3-bit computer with three registers and run a program created for this fictional computer. The instructions and operands of those insructions in this computer are all three bits (values from 0 to 7), however the 3 registers can hold any integer value. Part one of this day was pretty straightforward, but part two required that we reverse engineer the provided machine code to figure out the answer.
The boring part (parsing)
The input has two sections. The first section gives the initial values of the three registers and the second section is a comma separated list of numbers representing the program itself.
The first thing I do is to split the input on two consecutive newlines to separate the two sections. Then, I parse each part. Without going into too much detail, I use the split_once, split and parse functions of &str to parse each part of the input.
I then put all the parsed parts together into a Computer struct, which is responsible for executing the given program. Other than the three registers and the instructions, the struct stores an instruction pointer that tells us which instruction to execute next and a list of outputs. These are initialized to 0 to point to the first instruction when starting execution and to an empty list.
#[derive(Debug, Clone, PartialEq, Eq)]
struct Computer {
reg_a: u64,
reg_b: u64,
reg_c: u64,
instruction_ptr: usize,
instructions: Vec<u8>,
outputs: Vec<u8>,
}
fn parse_input(inp: String) -> Computer {
let (first_part, second_part) = inp.split_once("\n\n").unwrap();
let mut it = first_part
.lines()
.map(|l| l.split_once(':').unwrap().1.trim().parse().unwrap());
let reg_a = it.next().unwrap();
let reg_b = it.next().unwrap();
let reg_c = it.next().unwrap();
let instructions = second_part
.split_once(':')
.unwrap()
.1
.trim()
.split(',')
.map(|n| n.parse().unwrap())
.collect::<Vec<_>>();
Computer {
instructions,
instruction_ptr: 0,
reg_a,
reg_b,
reg_c,
outputs: Vec::new(),
}
}The straightforward part (part one)
This fictional computer has 8 commands that cover division (really just right-shifts), XORs, outputting, and conditional jumps. It outputs 3-bit numbers. There are two ways to read the operand depending on the command, the literal operand is the value of the operand itself and the "combo" operand can refer to one of the three registers or the values 0 to 3. See the original problem page for more details. The program executes the command at its current instruction pointer (which starts out at 0) and then moves on to where the instruction pointer points to after the command executes. For all commands except the conditional jump, the instruction pointers increments by 2, representing the command itself and its instruction. The program ends running when the instruction pointer would go past the program.
For part one, we need to execute the program and then get the value it outputs, joined by commas. We do this by implementing the logic of the 8 commands, and modify the values of the registers and instruction pointer accordingly. My implementation defines a run method on the Computer struct that outputs a Vec<u8> of outputs and then my part 1 function joins that into a comma-separated string.
fn part1(input: &Computer) -> String {
let mut computer = input.clone();
let outputs = computer.run();
let outputs_s: Vec<_> = outputs.iter().map(|x| x.to_string()).collect();
outputs_s.join(",")
}
impl Computer {
fn run(&mut self) -> Vec<u8> {
loop {
let current_instruction = self.instructions[self.instruction_ptr];
let operand = self.instructions[self.instruction_ptr + 1];
match current_instruction {
0 => {
// adv
let operand = self.combo_operand(operand);
self.reg_a = self.reg_a / (1 << operand);
self.instruction_ptr += 2;
}
6 => {
// bdv
let operand = self.combo_operand(operand);
self.reg_b = self.reg_a / (1 << operand);
self.instruction_ptr += 2;
}
7 => {
// cdv
let operand = self.combo_operand(operand);
self.reg_c = self.reg_a / (1 << operand);
self.instruction_ptr += 2;
}
1 => {
// bxl
self.reg_b = self.reg_b ^ (operand as u64);
self.instruction_ptr += 2;
}
2 => {
// bst
let operand = self.combo_operand(operand);
self.reg_b = operand % 8;
self.instruction_ptr += 2;
}
3 => {
// jnz
if self.reg_a == 0 {
self.instruction_ptr += 2;
} else {
self.instruction_ptr = operand.into();
}
}
4 => {
// bxc
self.reg_b = self.reg_b ^ self.reg_c;
self.instruction_ptr += 2;
}
5 => {
// out
let operand = self.combo_operand(operand);
self.outputs.push((operand % 8) as u8);
self.instruction_ptr += 2;
}
_ => panic!("invalid opcode"),
}
if self.instruction_ptr >= self.instructions.len() {
break;
}
}
self.outputs.clone()
}
fn combo_operand(&self, operand: u8) -> u64 {
match operand {
lit @ 0..=3 => lit.into(),
4 => self.reg_a,
5 => self.reg_b,
6 => self.reg_c,
_ => panic!("invalid combo operand"),
}
}
}Reverse engineering time (part two)
Now, we need to figure out the minimum value for register A that will convert the program into a quine, that is, the output should be the same as the program itself. To do this, we need to reverse engineer the program and find out what it does.
My input was this:
Register A: 64584136
Register B: 0
Register C: 0
Program: 2,4,1,2,7,5,1,3,4,3,5,5,0,3,3,0Let’s decode it step by step. First, let’s convert the numbers into the instruction names and arguments.
bst 4
bxl 2
cdv 5
bxl 3
bxc 3
out 5
adv 3
jnz 0Now, let’s convert this into a symbolic representation of what each instruction does.
B <- A % 8
B <- B xor 2
C <- A >> B
B <- B xor 3
B <- B xor C
output B % 8
A <- A >> 3
goto 0 if A != 0Note the last 2 lines carefully: A is shifted right by 3 and then the program goes back to the first instruction, repeating the program if A is not zero. What this means is that the program’s first output depends on the entirety of A but the second value depends only on A >> 3 and the last output depends only on the most significant 3 bits of A.
With this insight, we can construct the answer one step at a time, starting from the 3 MSB bits and then adding 3 bits to our answer until the output matches the program. So now, we start by maintaining a list of possible answers. This starts out as a singleton list with the item 0 as all a values must end at 0 for the program to terminate. Then, for each number i in the program, we try extending each such possible answer by all 8 combinations of 3 bits (0 to 7) and only keeping the extended possible answer if it matches the last i elements of the program. Finally, we return the minimum value in the list after all iterations are done.
fn part2(input: &Computer) -> u64 {
let computer = input.clone();
let instructions = computer.instructions.clone();
// The instructions in the input do the following:
// * compute some hash of A
// * output that hash mod 8
// * A = A >> 3
// * if A != 0, goto start
//
// What this means is that the first number outputted depends on all of A but the
// last number outputted depends only on the highest 3 bits of A. Similarily, the
// second last number only depends on the highest 6 bits of A and we can work
// backwards from there.
let mut a_values = vec![0];
for i in 0..instructions.len() {
let mut next_a_values = Vec::new();
for last_a_value in a_values.clone() {
for k in 0..8 {
let next_a_value = last_a_value << 3 | k;
let mut new_computer = computer.clone();
new_computer.reg_a = next_a_value;
let slice_to_test = &instructions[instructions.len() - 1 - i..instructions.len()];
let output = new_computer.run();
if &output == slice_to_test {
next_a_values.push(next_a_value);
}
}
}
a_values = next_a_values;
}
a_values.sort();
a_values.remove(0)
}