aoc/year2018/
day16.rs

1//! # Chronal Classification
2//!
3//! There are only 16 opcodes so we can use bitwise logic to efficiently perform the set operations
4//! that uniquely determine the mapping of each opcode to instruction.
5//!
6//! First we create a bitmask for each instruction block in the first half of the input
7//! with a `1` for each potential instruction. For example:
8//!
9//! ```none
10//!     Before: [3, 2, 1, 1]
11//!     9 2 1 2
12//!     After:  [3, 2, 2, 1]
13//!
14//!     Possible instructions: mulr, addi, seti
15//!     Binary Mask: 0000001000000110
16//! ```
17//!
18//! For part one the [`count_ones`] intrinsic computes the size of each set.
19//!
20//! For part two we need to determine the mapping of the unknown codes. First we reduce each
21//! unknown to a single set by taking the intersection of all examples. Then similar to
22//! solving simultaneous equation, we eliminate one unknown at a time, removing it from the other
23//! possibilities. This causes a domino effect, continuing until all unknowns are resolved.
24//!
25//! [`count_ones`]: u32::count_ones
26use crate::util::iter::*;
27use crate::util::parse::*;
28
29pub struct Input {
30    samples: Vec<(usize, u32)>,
31    program: Vec<[usize; 4]>,
32}
33
34pub fn parse(input: &str) -> Input {
35    let (first, second) = input.rsplit_once("\n\n").unwrap();
36    let samples = first
37        .iter_unsigned()
38        .chunk::<4>()
39        .chunk::<3>()
40        .map(|[before, instruction, after]| {
41            let [unknown, a, b, c] = instruction;
42            let mut mask = 0;
43
44            // Build set of possible opcodes
45            for opcode in 0..16 {
46                if cpu(opcode, a, b, &before) == after[c] {
47                    mask |= 1 << opcode;
48                }
49            }
50
51            (unknown, mask)
52        })
53        .collect();
54    let program = second.iter_unsigned().chunk::<4>().collect();
55
56    Input { samples, program }
57}
58
59pub fn part1(input: &Input) -> usize {
60    input.samples.iter().filter(|(_, mask)| mask.count_ones() >= 3).count()
61}
62
63pub fn part2(input: &Input) -> usize {
64    // Take intersection of samples, reducing each unknown opcode to a single set of possibilities.
65    let mut masks = [0xffff; 16];
66
67    for &(unknown, mask) in &input.samples {
68        masks[unknown] &= mask;
69    }
70
71    // To uniquely determine the mapping, there must be at least 1 opcode during each iteration
72    // that only has one possibility.
73    let mut convert = [0; 16];
74
75    while let Some(index) = masks.iter().position(|m| m.count_ones() == 1) {
76        let mask = masks[index];
77        // This opcode has only 1 possible mapping, so remove possbility from other opcodes.
78        masks.iter_mut().for_each(|m| *m &= !mask);
79        // Add mapping.
80        convert[index] = mask.trailing_zeros() as usize;
81    }
82
83    // Run the program now that we know the mapping.
84    let mut register = [0; 4];
85
86    for &[unknown, a, b, c] in &input.program {
87        let opcode = convert[unknown];
88        register[c] = cpu(opcode, a, b, &register);
89    }
90
91    register[0]
92}
93
94fn cpu(opcode: usize, a: usize, b: usize, register: &[usize; 4]) -> usize {
95    match opcode {
96        0 => register[a] + register[b],              // addr
97        1 => register[a] + b,                        // addi
98        2 => register[a] * register[b],              // mulr
99        3 => register[a] * b,                        // muli
100        4 => register[a] & register[b],              // banr
101        5 => register[a] & b,                        // bani
102        6 => register[a] | register[b],              // borr
103        7 => register[a] | b,                        // bori
104        8 => register[a],                            // setr
105        9 => a,                                      // seti
106        10 => (a > register[b]) as usize,            // gtir
107        11 => (register[a] > b) as usize,            // gtri
108        12 => (register[a] > register[b]) as usize,  // gtrr
109        13 => (a == register[b]) as usize,           // eqir
110        14 => (register[a] == b) as usize,           // eqri
111        15 => (register[a] == register[b]) as usize, // eqrr
112        _ => unreachable!(),
113    }
114}
aoc/year2018/day16.rs

aoc/year2018/
day16.rs
