From 22c9812924f361ec5dceb8ec44c0c53c6996e475 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Tue, 3 Feb 2026 00:18:36 +0100 Subject: [PATCH] Day 17 --- src/day17.rs | 253 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 7 ++ src/main.rs | 4 +- 3 files changed, 262 insertions(+), 2 deletions(-) create mode 100644 src/day17.rs diff --git a/src/day17.rs b/src/day17.rs new file mode 100644 index 0000000..0eabca8 --- /dev/null +++ b/src/day17.rs @@ -0,0 +1,253 @@ +use std::{convert::TryFrom, io::BufRead}; + +use itertools::Itertools; + +/* +Combo operand (3 bits): + 0-3: Literal + 4-6: Register A-C + 7: Not used + +After each instruction (except Jnz) the instruction pointer is increased by 2. +*/ + +#[repr(u8)] +pub enum Opcode { + Adv = 0x00, // Division: A <- A/2^combo operand. + Blx = 0x01, // Bitwise XOR: B <- B xor literal operand. + Bst = 0x02, // Modulo: B <- combo operand mod 8. + Jnz = 0x03, // If A != 0 goto literal operand. + Bxc = 0x04, // Bitwise XOR: B <- B xor C. (operand is ignored). + Out = 0x05, // Output the combo operand mod 8. + Bdv = 0x06, // Division: B <- A/2^combo operand. + Cdv = 0x07, // Division: C <- A/2^combo operand. +} + +impl TryFrom for Opcode { + type Error = (); + fn try_from(value: u8) -> Result { + match value { + v if v == Opcode::Adv as u8 => Ok(Opcode::Adv), + v if v == Opcode::Blx as u8 => Ok(Opcode::Blx), + v if v == Opcode::Bst as u8 => Ok(Opcode::Bst), + v if v == Opcode::Jnz as u8 => Ok(Opcode::Jnz), + v if v == Opcode::Bxc as u8 => Ok(Opcode::Bxc), + v if v == Opcode::Out as u8 => Ok(Opcode::Out), + v if v == Opcode::Bdv as u8 => Ok(Opcode::Bdv), + v if v == Opcode::Cdv as u8 => Ok(Opcode::Cdv), + _ => Err(()), + } + } +} + +#[derive(Debug, Copy, Clone)] +pub struct State { + reg_a: i64, + reg_b: i64, + reg_c: i64, +} + +impl State { + fn new(reg_a: i64, reg_b: i64, reg_c: i64) -> State { + State { + reg_a, + reg_b, + reg_c, + } + } +} + +pub fn read(reader: &mut dyn BufRead) -> (State, Vec) { + let mut state = State::new(0, 0, 0); + let mut lines = reader.lines(); + + state.reg_a = lines.next().unwrap().unwrap()[12..].parse().unwrap(); + state.reg_b = lines.next().unwrap().unwrap()[12..].parse().unwrap(); + state.reg_c = lines.next().unwrap().unwrap()[12..].parse().unwrap(); + lines.next(); + + let program: Vec = lines.next().unwrap().unwrap()[9..] + .split(',') + .map(|n| n.parse().unwrap()) + .collect(); + + (state, program) +} + +pub fn run(state: &mut State, program: &[u8]) -> String { + output_to_string(&run_to_vec(state, program)) +} + +fn output_to_string(output: &[u8]) -> String { + output.iter().join(",") +} + +fn run_to_vec(state: &mut State, program: &[u8]) -> Vec { + let mut instruction_pointer = 0; + let mut output: Vec = Vec::new(); + + while instruction_pointer < program.len() { + let instruction = program[instruction_pointer]; + let operand = program[instruction_pointer + 1] as i64; + let operand_combo = if operand <= 3 { + operand + } else { + match operand { + 4 => state.reg_a, + 5 => state.reg_b, + 6 => state.reg_c, + _ => 0, + } + }; + + instruction_pointer += 2; + + match instruction.try_into() { + Ok(Opcode::Adv) => state.reg_a /= 1 << operand_combo, + Ok(Opcode::Blx) => state.reg_b ^= operand, + Ok(Opcode::Bst) => state.reg_b = operand_combo % 8, + Ok(Opcode::Jnz) => { + if state.reg_a != 0 { + instruction_pointer = operand as usize; + } + } + Ok(Opcode::Bxc) => state.reg_b ^= state.reg_c, + Ok(Opcode::Out) => { + output.push((operand_combo % 8) as u8); + } + Ok(Opcode::Bdv) => state.reg_b = state.reg_a / (1 << operand_combo), + Ok(Opcode::Cdv) => state.reg_c = state.reg_a / (1 << operand_combo), + Err(_) => { + eprintln!("Can't decode instruction {instruction} @ {instruction_pointer}"); + break; + } + } + } + + output +} + +pub fn fix_corrupted_reg_a(state: &mut State, program: &[u8]) -> i64 { + let reg_b = state.reg_b; + let reg_c = state.reg_c; + + let l = program.len(); + let mut to_skip = vec![0u8; l]; + let mut a = 0; + let mut i = l - 1; + loop { + // println!("{i} --------"); // Debug. + + let mut skipped = 0; + for x in 0..8 { + // println!("a = {:048b}", a); // Debug. + + state.reg_a = a; + state.reg_b = reg_b; + state.reg_c = reg_c; + + let output = run_to_vec(state, program); + + if output.len() == l { + // Debug. + // println!("(a >> ({} * 3)) mod 8 = {}", i, (a >> (i * 3)) % 8); + // println!("{} ({})", output_to_string(&output), output.len()); + + if output[i] == program[i] { + // It was the last digit -> return the register A value. + if i == 0 { + return a; + } + + if skipped == to_skip[i] { + i -= 1; + break; + } else { + skipped += 1; + } + } + + if x == 8 - 1 { + a &= !(0b111111 << (3 * i)); // Erase current position and previous one. + to_skip[i] = 0; + + i += 1; + to_skip[i] += 1; + break; + } + } + + if output.len() > l { + return -1; + } + + a += 8i64.pow(i as u32); + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn part1_example_1() { + let mut state = State::new(0, 0, 9); + let _output = run(&mut state, &[2, 6]); + assert_eq!(state.reg_b, 1); + } + + #[test] + fn part1_example_2() { + let mut state = State::new(10, 0, 0); + let output = run(&mut state, &[5, 0, 5, 1, 5, 4]); + assert_eq!(output, "0,1,2"); + } + + #[test] + fn part1_example_3() { + let mut state = State::new(2024, 0, 0); + let output = run(&mut state, &[0, 1, 5, 4, 3, 0]); + assert_eq!(output, "4,2,5,6,7,7,7,7,3,1,0"); + } + + #[test] + fn part1_example_4() { + let mut state = State::new(0, 29, 0); + let _output = run(&mut state, &[1, 7]); + assert_eq!(state.reg_b, 26); + } + + #[test] + fn part1_example_5() { + let mut state = State::new(0, 2024, 43690); + let _output = run(&mut state, &[4, 0]); + assert_eq!(state.reg_b, 44354); + } + + static EXAMPLE_PART_1: &str = "Register A: 729 +Register B: 0 +Register C: 0 + +Program: 0,1,5,4,3,0"; + + #[test] + fn part1_example_6() { + let (mut state, program) = read(&mut EXAMPLE_PART_1.as_bytes()); + let output = run(&mut state, &program); + assert_eq!(output, "4,6,3,5,6,3,5,2,1,0"); + } + + static EXAMPLE_PART_2: &str = "Register A: 2024 +Register B: 0 +Register C: 0 + +Program: 0,3,5,4,3,0"; + + #[test] + fn part2_example_1() { + let (mut state, program) = read(&mut EXAMPLE_PART_2.as_bytes()); + let reg_a = fix_corrupted_reg_a(&mut state, &program); + assert_eq!(reg_a, 117440); + } +} diff --git a/src/days.rs b/src/days.rs index afb47a7..3fc858a 100644 --- a/src/days.rs +++ b/src/days.rs @@ -149,3 +149,10 @@ pub fn day16(reader: &mut dyn BufRead) -> String { let (score, nb_tiles) = day16::best_score_and_nb_of_tiles_best_spot(&maze, &start, &direction); format!("part1: {score}, part2: {nb_tiles}",) } + +pub fn day17(reader: &mut dyn BufRead) -> String { + let (mut state, program) = day17::read(reader); + let output = day17::run(&mut state.clone(), &program); + let reg_a = day17::fix_corrupted_reg_a(&mut state, &program); + format!("part1: '{output}', part2: {reg_a}") +} diff --git a/src/main.rs b/src/main.rs index b962cd5..98da7f9 100644 --- a/src/main.rs +++ b/src/main.rs @@ -16,7 +16,7 @@ mod day13; mod day14; mod day15; mod day16; -// mod day17; +mod day17; // mod day18; // mod day19; // mod day20; @@ -47,7 +47,7 @@ fn main() { days::day14, days::day15, days::day16, - // days::day17, + days::day17, // days::day18, // days::day19, // days::day20, -- 2.51.0