2024 day 17

pub fn part_two(input: &str) -> Option<u64> {
    let inst: Vec<u8> = parse(input).1;

    fn solve(inst: &Vec<u8>, pos: usize, a: u64) -> bool {
        let mut reg: Vec<u64> = vec![a, 0, 0];
        for p in 0..(inst.len() / 2) {
            let operand = inst[p * 2 + 1] as u64;

            match OpCode::from_u8(inst[p * 2]) {
                OpCode::Adv => reg[0] >>= combo(operand, &reg),
                OpCode::Bxl => reg[1] ^= operand,
                OpCode::Bst => reg[1] = combo(operand, &reg) % 8,
                OpCode::Jnz => return solve(inst, pos + 1, reg[0]),
                OpCode::Bxc => reg[1] ^= reg[2],
                OpCode::Out if ((combo(operand, &reg) % 8) as u8) != inst[pos] => return false,
                OpCode::Out if pos == (inst.len() - 1) => return true,
                OpCode::Out => {}
                OpCode::Bdv => reg[1] = reg[0] >> combo(operand, &reg),
                OpCode::Cdv => reg[2] = reg[0] >> combo(operand, &reg),
            }
        }

        false
    }

    let mut search: Vec<u64> = vec![0];

    // progressively search for solution to each output in reverse
    for target in (0..inst.len()).rev() {
        println!("{:?}", search);
        let mut next: Vec<u64> = Vec::new();
        // 8 possible values of RegA could generate this, so check them
        for a in search.iter().flat_map(|a| (0..8).map(move |i| a + i)) {
            if solve(&inst, target, a) {
                // this value of RegA produces the last N values
                if target == 0 {
                    // done!
                    return Some(a);
                }
                next.push(a << 3);
            }
        }
        search = next;
    }

    None
}