- commit
- 04137c4900ddd3982fe3c32b200558d68d3486ce
- parent
- 8e8988fd784454fafd20813f40c4c685491b4613
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2024-12-17 08:39
2024-12-17
Diffstat
A | 2024/17/input.txt | 5 | +++++ |
A | 2024/17/solution.rs | 185 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
A | 2024/17/test1.txt | 5 | +++++ |
A | 2024/17/test2.txt | 5 | +++++ |
4 files changed, 200 insertions, 0 deletions
diff --git a/2024/17/input.txt b/2024/17/input.txt
@@ -0,0 +1,5 @@ -1 1 Register A: 30553366 -1 2 Register B: 0 -1 3 Register C: 0 -1 4 -1 5 Program: 2,4,1,1,7,5,4,7,1,4,0,3,5,5,3,0
diff --git a/2024/17/solution.rs b/2024/17/solution.rs
@@ -0,0 +1,185 @@ -1 1 #[path = "../lib.rs"] -1 2 mod lib; -1 3 -1 4 fn parse_input() -> (usize, Vec<usize>) { -1 5 let mut a = 0; -1 6 let mut program = vec![]; -1 7 -1 8 for line in lib::iter_input() { -1 9 match line.split_once(": ") { -1 10 Some(("Register A", v)) => { -1 11 a = v.parse::<usize>().unwrap(); -1 12 } -1 13 Some(("Register B", v)) => { -1 14 assert!(v == "0") -1 15 } -1 16 Some(("Register C", v)) => { -1 17 assert!(v == "0") -1 18 } -1 19 Some(("Program", v)) => { -1 20 program = v.split(',').map(|c| c.parse::<usize>().unwrap()).collect(); -1 21 } -1 22 _ => {} -1 23 }; -1 24 } -1 25 -1 26 return (a, program); -1 27 } -1 28 -1 29 fn decompile_combo(value: usize) -> String { -1 30 return match value { -1 31 0 | 1 | 2 | 3 => value.to_string(), -1 32 4 => "A".to_string(), -1 33 5 => "B".to_string(), -1 34 6 => "C".to_string(), -1 35 _ => unreachable!(), -1 36 }; -1 37 } -1 38 -1 39 fn decompile(program: &Vec<usize>) { -1 40 let mut i = 0; -1 41 while i < program.len() { -1 42 match program[i] { -1 43 0 => { -1 44 println!("A = A >> {}", decompile_combo(program[i + 1])); -1 45 } -1 46 1 => { -1 47 println!("B ^= {}", program[i + 1]); -1 48 } -1 49 2 => { -1 50 println!("B = {} % 8", decompile_combo(program[i + 1])); -1 51 } -1 52 3 => { -1 53 println!("if A != 0: jump({})", program[i + 1]); -1 54 } -1 55 4 => { -1 56 println!("B ^= C"); -1 57 } -1 58 5 => { -1 59 println!("output({} % 8)", decompile_combo(program[i + 1])) -1 60 } -1 61 6 => { -1 62 println!("B = A >> {}", decompile_combo(program[i + 1])); -1 63 } -1 64 7 => { -1 65 println!("C = A >> {}", decompile_combo(program[i + 1])); -1 66 } -1 67 _ => unreachable!(), -1 68 }; -1 69 i += 2; -1 70 } -1 71 println!(""); -1 72 } -1 73 -1 74 fn get_combo(value: usize, reg: &[usize; 3]) -> usize { -1 75 return match value { -1 76 0 | 1 | 2 | 3 => value, -1 77 4 => reg[0], -1 78 5 => reg[1], -1 79 6 => reg[2], -1 80 _ => unreachable!(), -1 81 }; -1 82 } -1 83 -1 84 fn exec(i: usize, reg: &mut [usize; 3], program: &Vec<usize>, output: &mut Vec<usize>) -> usize { -1 85 match program[i] { -1 86 0 => { -1 87 reg[0] >>= get_combo(program[i + 1], reg); -1 88 } -1 89 1 => { -1 90 reg[1] ^= program[i + 1]; -1 91 } -1 92 2 => { -1 93 reg[1] = get_combo(program[i + 1], reg) % 8; -1 94 } -1 95 3 => { -1 96 if reg[0] != 0 { -1 97 return program[i + 1]; -1 98 } -1 99 } -1 100 4 => { -1 101 reg[1] ^= reg[2]; -1 102 } -1 103 5 => { -1 104 output.push(get_combo(program[i + 1], reg) % 8); -1 105 } -1 106 6 => { -1 107 reg[1] = reg[0] >> get_combo(program[i + 1], reg); -1 108 } -1 109 7 => { -1 110 reg[2] = reg[0] >> get_combo(program[i + 1], reg); -1 111 } -1 112 _ => unreachable!(), -1 113 }; -1 114 return i + 2; -1 115 } -1 116 -1 117 fn exec_cycle(program: &Vec<usize>, a: usize) -> usize { -1 118 let mut reg = [a, 0, 0]; -1 119 let mut output = vec![]; -1 120 let mut i = 0; -1 121 while output.len() == 0 { -1 122 i = exec(i, &mut reg, program, &mut output); -1 123 } -1 124 return output[0]; -1 125 } -1 126 -1 127 fn reverse(program: &Vec<usize>, a: usize, i: usize) -> Option<usize> { -1 128 // I noticed some properties about the input -1 129 // -1 130 // - it ends with a conditional jump to the start of the program -1 131 // - that is the only jump -1 132 // - a single value is output on every iteration -1 133 // - that value can be derived from A, without knowing the initial B and C -1 134 // - A is shifted by 3 bits in every iteration and not otherwise changed -1 135 // -1 136 // In other words: The program iterate through the 3-bit blocks in A and -1 137 // outputs some values for each one. These values may also depend on the -1 138 // higher bits, but not on the lower. This means that we can construct an -1 139 // initial value for A by starting at the highest bits (that will generate -1 140 // the last output). -1 141 -1 142 if i == program.len() { -1 143 return Some(a); -1 144 } -1 145 -1 146 for j in 0..8 { -1 147 let next = (a << 3) | j; -1 148 if exec_cycle(program, next) == program[program.len() - i - 1] { -1 149 if let Some(result) = reverse(program, next, i + 1) { -1 150 return Some(result); -1 151 } -1 152 } -1 153 } -1 154 -1 155 return None; -1 156 } -1 157 -1 158 fn part1(program: &Vec<usize>, a: usize) -> String { -1 159 let mut reg = [a, 0, 0]; -1 160 let mut output = vec![]; -1 161 let mut i = 0; -1 162 -1 163 while i < program.len() { -1 164 i = exec(i, &mut reg, &program, &mut output); -1 165 } -1 166 -1 167 return output -1 168 .iter() -1 169 .map(|&x| x.to_string()) -1 170 .collect::<Vec<String>>() -1 171 .join(","); -1 172 } -1 173 -1 174 fn part2(program: &Vec<usize>) -> usize { -1 175 return reverse(program, 0, 0).unwrap(); -1 176 } -1 177 -1 178 fn main() { -1 179 let (a, program) = parse_input(); -1 180 -1 181 decompile(&program); -1 182 -1 183 println!("part1: {}", part1(&program, a)); -1 184 println!("part2: {}", part2(&program)); -1 185 }
diff --git a/2024/17/test1.txt b/2024/17/test1.txt
@@ -0,0 +1,5 @@ -1 1 Register A: 729 -1 2 Register B: 0 -1 3 Register C: 0 -1 4 -1 5 Program: 0,1,5,4,3,0
diff --git a/2024/17/test2.txt b/2024/17/test2.txt
@@ -0,0 +1,5 @@ -1 1 Register A: 2024 -1 2 Register B: 0 -1 3 Register C: 0 -1 4 -1 5 Program: 0,3,5,4,3,0