Rust

Part 2 really broke me. I ended up converting the instructions into a pair of equations, that I then used to do DFS to find the A value. Then I realised the compute function already does this for me…

#[cfg(test)]
mod tests {
    use regex::Regex;

    fn compute(registers: &mut [u64], instructions: &[u64]) -> String {
        let mut out = vec![];
        let mut ip = 0;
        loop {
            let opcode = instructions[ip];
            let operand = instructions[ip + 1];

            match opcode {
                0 => {
                    println!(
                        "0: A <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[0] /= 1 << combo(operand, registers)
                }
                1 => {
                    println!("1: B <= B[{}]^{}", registers[1], operand);
                    registers[1] ^= operand
                }
                2 => {
                    println!(
                        "2: B <= {} ({}:{:?})",
                        combo(operand, registers) % 8,
                        operand,
                        registers
                    );
                    registers[1] = combo(operand, registers) % 8
                }
                3 => {
                    if registers[0] != 0 {
                        println!("3: JUMP {}", operand);
                        ip = operand as usize;
                        continue;
                    }
                }
                4 => {
                    println!("4: B <= B[{}]^C[{}]", registers[1], registers[2]);
                    registers[1] ^= registers[2]
                }
                5 => {
                    out.push(combo(operand, registers) % 8);
                    println!(
                        "5: OUT: {} ({}:{:?})",
                        out.last().unwrap(),
                        operand,
                        registers
                    );
                }

                6 => {
                    println!(
                        "6: B <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[1] = registers[0] / (1 << combo(operand, registers))
                }
                7 => {
                    println!(
                        "7: C <= A[{}]/{} ({}:{:?})",
                        registers[0],
                        1 << combo(operand, registers),
                        operand,
                        registers
                    );
                    registers[2] = registers[0] / (1 << combo(operand, registers))
                }
                _ => unreachable!(),
            }
            ip += 2;
            if ip >= instructions.len() {
                break;
            }
        }
        out.iter()
            .map(|v| v.to_string())
            .collect::<Vec<String>>()
            .join(",")
    }

    fn combo(p0: u64, regs: &[u64]) -> u64 {
        match p0 {
            0..=3 => p0,
            4..=6 => regs[(p0 - 4) as usize],
            _ => unreachable!(),
        }
    }

    #[test]
    fn day17_part1_test() {
        let input = std::fs::read_to_string("src/input/day_17.txt").unwrap();
        let mut parts = input.split("\n\n");
        let re = Regex::new(r"[\-0-9]+").unwrap();
        let mut registers = re
            .captures_iter(parts.next().unwrap())
            .map(|x| {
                let first = x.get(0).unwrap().as_str();
                first.parse::<u64>().unwrap()
            })
            .collect::<Vec<u64>>();

        let instructions = parts
            .next()
            .unwrap()
            .replace("Program: ", "")
            .split(",")
            .map(|s| s.parse::<u64>().unwrap())
            .collect::<Vec<u64>>();

        let out = compute(&mut registers, &instructions);
        println!("{out}");
    }

    #[test]
    fn day17_part2_test() {
        let input = std::fs::read_to_string("src/input/day_17.txt").unwrap();
        let mut parts = input.split("\n\n");
        let _ = parts.next().unwrap();

        let instructions = parts
            .next()
            .unwrap()
            .replace("Program: ", "")
            .split(",")
            .map(|s| s.parse::<u64>().unwrap())
            .collect::<Vec<u64>>();

        fn search_generic(a_prev: u64, i: usize, instructions: &Vec<u64>) -> Option<u64> {
            let out = instructions[i];
            for j in 0..8 {
                let next_a = (a_prev << 3) + j;
                let expected = instructions[i..]
                    .iter()
                    .map(|v| v.to_string())
                    .collect::<Vec<String>>()
                    .join(",");

                let mut regs = [next_a, 0, 0];
                if expected == compute(&mut regs, instructions) {
                    if i == 0 {
                        return Some(next_a);
                    }
                    if let Some(a) = search_generic(next_a, i - 1, instructions) {
                        return Some(a);
                    }
                }
            }
            None
        }

        let res_a = search_generic(0, instructions.len() - 1, &instructions).unwrap();

        let mut registers = [res_a, 0, 0];
        let out = compute(&mut registers, &instructions);
        let expected = instructions
            .iter()
            .map(|v| v.to_string())
            .collect::<Vec<String>>()
            .join(",");

        assert_eq!(expected, out);
        println!("{res_a}");
    }
}