Day 17: Chronospatial Computer

with open('input/17.txt', 'r') as f:
    lines = f.read().splitlines()

register_a = int(lines[0].split()[-1])
register_b = int(lines[1].split()[-1])
register_c = int(lines[2].split()[-1])

program = list(map(int, lines[4].split()[1].split(',')))

program_pointer = 0
program_output = []

def combo_operand(operand: int):
    if operand <= 3:
        return operand
    if operand == 4:
        return register_a
    if operand == 5:
        return register_b
    if operand == 6:
        return register_c
    raise ValueError(f'Invalid combo operand {operand}')

def adv(operand: int):
    global register_a
    res = register_a // (2 ** combo_operand(operand))
    register_a = res

def bxl(operand: int):
    global register_b
    register_b = register_b ^ operand

def bst(operand: int):
    global register_b
    register_b = combo_operand(operand) % 8

def jnz(operand: int):
    global program_pointer
    if register_a != 0:
        program_pointer = operand - 2

def bxc(operand: int):
    global register_b
    register_b = register_b ^ register_c

def out(operand: int):
    program_output.append(combo_operand(operand) % 8)

def bdv(operand: int):
    global register_b
    res = register_a // (2 ** combo_operand(operand))
    register_b = res

def cdv(operand: int):
    global register_c
    res = register_a // (2 ** combo_operand(operand))
    register_c = res

operations = [adv, bxl, bst, jnz, bxc, out, bdv, cdv]

while 0 <= program_pointer < len(program):
    operation = program[program_pointer]
    operand = program[program_pointer + 1]
    operations[operation](operand)
    program_pointer += 2

print("Part 1:", ",".join(map(str,program_output)))

# 2,4,1,3,7,5,4,2,0,3,1,5,5,5,3,0

# WHILE A != 0:
    # bst 4: B = A % 8
    # bxl 3: B = B ^ 3
    # csv 5: C = A // 2 ** B
    # bxc: B = B ^ C
    # adv 3: A = A // 8
    # bxl 5: B = B ^ 5
    # out 5: B % 8

target_output = "".join(map(str, program))

def run(a: int):
    b = 0
    c = 0
    output = []
    while a != 0:
        b = a % 8
        b = b ^ 3
        c = a // (2 ** b)
        b = b ^ c
        a = a // 8
        b = b ^ 5
        output.append(b % 8)
    return "".join(map(str, output))

encountered_prefixes = set()
prefix_queue = [""]
length = len(target_output)
lowest_match = None
while len(prefix_queue) > 0:
    prefix = prefix_queue.pop(0)
    if prefix in encountered_prefixes:
        continue
    encountered_prefixes.add(prefix)
    #print(prefix, len(matches))
    for i in range(8):
        s = prefix + str(i) + "0" * (length - len(prefix) - 1)
        a = int(s, 8)
        result = run(a)
        if len(result) < length:
            continue
        if result == target_output:
            if lowest_match is None or a < lowest_match:
                lowest_match = a
                print("Part 2:", lowest_match)
                exit()
        idx = length - len(prefix) - 1
        if target_output[idx] == result[idx]:
            prefix_queue.append(prefix + str(i))

Class {
	#name : 'Day17Computer',
	#superclass : 'Object',
	#instVars : [ 'a', 'b', 'c', 'program', 'ip', 'halted', 'output' ],
	#category : 'AoCDay17',
	#package : 'AoCDay17'
}

Day17Computer >> initialize [
	ip := 1.
	halted := false.
	output := OrderedCollection new.
]

Day17Computer >> step [
	| opcode operations combo literal |
	(ip between: 1 and: program size) ifFalse: [ halted := true. ^ self ].
	opcode := program at: ip.
	literal := program at: (ip + 1).
	combo := { 0 . 1 . 2 . 3 . a . b . c } at: ((program at: (ip + 1)) + 1).
	operations := Dictionary newFromPairs: {
		0 . [ a := a >> combo ] .
		1 . [ b := b bitXor: literal ] .
		2 . [ b := combo % 8 ] .
		3 . [ a ~= 0 ifTrue: [ ip := literal - 1 ] ] .
		4 . [ b := b bitXor: c ] .
		5 . [ output add: combo % 8 ] .
		6 . [ b := a >> combo ] .
		7 . [ c := a >> combo ]
	}.
	(operations at: opcode) value.
	ip := ip + 2
]

Class {
	#name : 'Day17Solver',
	#superclass : 'AoCSolver',
	#instVars : [ 'aInitial', 'bInitial', 'cInitial', 'program' ],
	#category : 'AoCDay17',
	#package : 'AoCDay17'
}

Day17Solver >> parseRawData [
	| nums |
	nums := ('\d+' asRegex matchesIn: rawData) collect: #asInteger.
	aInitial := nums first.
	bInitial := nums second.
	cInitial := nums third.
	program := nums allButFirst: 3
]

Day17Solver >> solvePart1 [
	^ $, join: ((self runComputer: aInitial) collect: #asString)
]

Day17Solver >> solvePart2 [
	^ self solve2Helper: 0 finished: 0
]

Day17Solver >> runComputer: aStart [
	| computer |
	computer := Day17Computer new a: aStart; b: bInitial; c: cInitial; program: program.
	[ computer halted ] whileFalse: [ computer step ].
	^ computer output
]

Day17Solver >> solve2Helper: a finished: n [
	| output target recResult |
	n = program size ifTrue: [ ^ a ].
	target := program at: program size - n.
	0 to: 7 do: [ :x |
		output := self runComputer: a << 3 + x.
		output first = target ifTrue: [
			recResult := self solve2Helper: a << 3 + x finished: n + 1.
			recResult > 0 ifTrue: [ ^ recResult ] ] ].
	^ 0
]

Part 1 was very boring; everything worked on the 2nd try -- The Sokoban puzzle was much more interesting.

pub fn part1(input: &PuzzleInput) -> String {
    let machine = run_machine(input);
    machine.output.iter().join(",").to_string()
}

pub fn run_machine(input: &PuzzleInput) -> Machine {
    let mut machine = Machine {
        a: input.register_a,
        b: input.register_b,
        c: input.register_c,
        program: input.program.clone(),
        instr_ptr: 0,
        output: vec![],
    };

    while let Some(_) = machine.step() {}

    machine
}

#[derive(Debug, Clone)]
pub struct Machine {
    pub a: u64,
    pub b: u64,
    pub c: u64,

    pub program: Vec<u64>,
    pub instr_ptr: usize,
    pub output: Vec<u64>,
}

impl Machine {
    pub fn step(&mut self) -> Option<()> {
        let instr: Instruction = self.read()?.into();

        match instr {
            Instruction::Adv => self.adv(),
            Instruction::Bxl => self.bxl(),
            Instruction::Bst => self.bst(),
            Instruction::Jnz => self.jnz(),
            Instruction::Bxc => self.bxc(),
            Instruction::Out => self.out(),
            Instruction::Bdv => self.bdv(),
            Instruction::Cdv => self.cdv(),
        };

        Some(())
    }

    pub fn read(&mut self) -> Option<u64> {
        if self.instr_ptr >= self.program.len() {
            return None;
        }

        let val = self.program[self.instr_ptr];
        self.instr_ptr += 1;
        Some(val)
    }

    pub fn adv(&mut self) -> Option<()> {
        let numerator = self.a as f64;
        let denominator = (1 << self.combo_operand()?) as f64;
        self.a = (numerator / denominator).trunc() as u64;
        Some(())
    }

    pub fn bxl(&mut self) -> Option<()> {
        let operand = self.literal_operand()?;
        self.b ^= operand;
        Some(())
    }

    pub fn bst(&mut self) -> Option<()> {
        let operand = self.combo_operand()?;
        self.b = operand % 8;
        Some(())
    }

    pub fn jnz(&mut self) -> Option<()> {
        let o = self.literal_operand()?;

        if self.a == 0 {
            return Some(());
        }

        self.instr_ptr = o as usize;
        Some(())
    }

    pub fn bxc(&mut self) -> Option<()> {
        let _ = self.literal_operand()?;
        let r = self.b ^ self.c;
        self.b = r;
        Some(())
    }

    pub fn out(&mut self) -> Option<()> {
        let o = self.combo_operand()? % 8;
        self.output.push(o);
        Some(())
    }

    pub fn bdv(&mut self) -> Option<()> {
        let numerator = self.a as f64;
        let denominator = (1 << self.combo_operand()?) as f64;
        self.b = (numerator / denominator).trunc() as u64;
        Some(())
    }

    pub fn cdv(&mut self) -> Option<()> {
        let numerator = self.a as f64;
        let denominator = (1 << self.combo_operand()?) as f64;
        self.c = (numerator / denominator).trunc() as u64;
        Some(())
    }

    pub fn literal_operand(&mut self) -> Option<u64> {
        let x = *self.program.get(self.instr_ptr)?;
        self.instr_ptr += 1;
        Some(x)
    }

    pub fn combo_operand(&mut self) -> Option<u64> {
        let x = self.program.get(self.instr_ptr)?;
        self.instr_ptr += 1;

        match x {
            0..=3 => return Some(*x),
            4 => return Some(self.a),
            5 => return Some(self.b),
            6 => return Some(self.c),
            7 => unreachable!("Reserved operand"),
            _ => panic!("Invalid operand"),
        }
    }
}

#[derive(Debug, PartialEq, Eq)]
pub enum Instruction {
    Adv,
    Bxl,
    Bst,
    Jnz,
    Bxc,
    Out,
    Bdv,
    Cdv,
}

impl From<u64> for Instruction {
    fn from(value: u64) -> Self {
        match value {
            0 => Instruction::Adv,
            1 => Instruction::Bxl,
            2 => Instruction::Bst,
            3 => Instruction::Jnz,
            4 => Instruction::Bxc,
            5 => Instruction::Out,
            6 => Instruction::Bdv,
            7 => Instruction::Cdv,
            _ => panic!("Invalid instruction"),
        }
    }
}

Part 2 took a long time. I transcribed the machine code back into a more high-level representation and noticed that a is only ever divided by eight.

It would probably be possible to just derive the bit pattern for the registers if you stare at it hard enough, but I took this as an opportunity to play with Z3.
After a few skill issues with getting it to do XOR and 2**X operations (not to mention the sidequest of translating the entire fucking VM into Python because the Rust bindings aren't complete for Z3), I had an answer that produced a quine; however, it was too high. Then I was left scratching my head, because Z3 refused to find answers below it, and if I gave it a constraint not to exceed the known result, it produced even higher numbers. Finally, after fiddling with the number of bits in the BitVecs, it finally spit out an answer that the AoC site accepted -- though I'm not sure if I just got lucky there. :(

/* Advent of Code 2024
 * Day 17: Chronospatial Computer
 */

#import "Basic";
#import "File";
#import "String";

Registers :: struct {
    a, b, c: int;
}

State :: struct {
    register_a, iteration: int;
}

resolve_combo_operand :: (operand: u8, registers: Registers) -> int {
    if operand == {
        case 4; return registers.a;
        case 5; return registers.b;
        case 6; return registers.c;
        case;   return operand;
    }
}

run_program :: (initial_registers: Registers, program: [] u8) -> [..] int {
    registers := initial_registers;
    instruction_pointer := 0;
    output: [..] int;

    while instruction_pointer < program.count {
        opcode := program[instruction_pointer];
        operand := program[instruction_pointer + 1];
        instruction_pointer += 2;

        // I don't personally find the instruction names any more readable than
        // the plain opcodes, so I didn't bother using an enum.
        if opcode == {
            case 0;
                registers.a = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );

            case 1;
                registers.b = registers.b ^ operand;

            case 2;
                registers.b = resolve_combo_operand(operand, registers) % 8;

            case 3;
                if registers.a != 0 {
                    instruction_pointer = operand;
                }

            case 4;
                registers.b = registers.b ^ registers.c;

            case 5;
                array_add(
                    *output,
                    resolve_combo_operand(operand, registers) % 8
                );

            case 6;
                registers.b = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );

            case 7;
                registers.c = (
                    registers.a
                    / 1 << resolve_combo_operand(operand, registers)
                );
        }
    }

    return output;
}

main :: () {
    input, success := read_entire_file("inputs/day_17.txt");
    assert(success);

    lines := split(input, "\n");
    defer array_free(lines);

    program_strings := split(slice(lines[4], 9, lines[4].count - 9), ",");
    defer array_free(program_strings);

    program: [..] u8;
    defer array_free(program);

    for program_strings {
        array_add(*program, xx string_to_int(it));
    }

    output := run_program(.{
        a = string_to_int(slice(lines[0], 12, lines[0].count - 12)),
        b = string_to_int(slice(lines[1], 12, lines[1].count - 12)),
        c = string_to_int(slice(lines[2], 12, lines[2].count - 12))
    }, program);
    defer array_free(output);

    builder: String_Builder;
    defer reset(*builder);

    for output {
        print_to_builder(*builder, "%", it);
        if it_index < output.count - 1 {
            append(*builder, ",");
        }
    }

    print("Part 1: %\n", builder_to_string(*builder));

    // Every three bits given to the program add another number to the output.
    // Because of this, we can bruteforce three bits at a time. We're using BFS
    // here instead of just bruteforcing the groups of bits in sequence because
    // occasionally we may run into a false lead.
    queue: [..] State;
    array_add(*queue, .{0, 0});
    defer array_free(queue);

    while queue.count {
        current := queue[0];
        array_ordered_remove_by_index(*queue, 0);

        target := program[program.count - current.iteration - 1];
        for 0..7 {
            new_register_a := current.register_a << 3 | it;
            registers := Registers.{new_register_a, 0, 0};

            output := run_program(registers, program);
            defer array_free(output);

            if output[0] == target {
                if current.iteration == program.count - 1 {
                    print("Part 2: %\n", new_register_a);
                    return;
                } else {
                    array_add(*queue, .{registers.a, current.iteration + 1});
                }
            }
        }
    }
}