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 equations, 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            // Build set of possible opcodes.
43            let mask = (0..16)
44                .filter(|&opcode| cpu(opcode, a, b, &before) == after[c])
45                .fold(0, |mask, opcode| mask | (1 << opcode));
46
47            (unknown, mask)
48        })
49        .collect();
50    let program = second.iter_unsigned().chunk::<4>().collect();
51
52    Input { samples, program }
53}
54
55pub fn part1(input: &Input) -> usize {
56    input.samples.iter().filter(|(_, mask)| mask.count_ones() >= 3).count()
57}
58
59pub fn part2(input: &Input) -> usize {
60    // Take intersection of samples, reducing each unknown opcode to a single set of possibilities.
61    let mut masks = [0xffff; 16];
62
63    for &(unknown, mask) in &input.samples {
64        masks[unknown] &= mask;
65    }
66
67    // To uniquely determine the mapping, there must be at least 1 opcode during each iteration
68    // that only has one possibility.
69    let mut convert = [0; 16];
70
71    while let Some(index) = masks.iter().position(|&n| n.count_ones() == 1) {
72        let mask = masks[index];
73        // This opcode has only 1 possible mapping, so remove possibility from other opcodes.
74        masks.iter_mut().for_each(|m| *m &= !mask);
75        // Add mapping.
76        convert[index] = mask.trailing_zeros() as usize;
77    }
78
79    // Run the program now that we know the mapping.
80    let mut register = [0; 4];
81
82    for &[unknown, a, b, c] in &input.program {
83        let opcode = convert[unknown];
84        register[c] = cpu(opcode, a, b, &register);
85    }
86
87    register[0]
88}
89
90fn cpu(opcode: usize, a: usize, b: usize, register: &[usize; 4]) -> usize {
91    match opcode {
92        0 => register[a] + register[b],                // addr
93        1 => register[a] + b,                          // addi
94        2 => register[a] * register[b],                // mulr
95        3 => register[a] * b,                          // muli
96        4 => register[a] & register[b],                // banr
97        5 => register[a] & b,                          // bani
98        6 => register[a] | register[b],                // borr
99        7 => register[a] | b,                          // bori
100        8 => register[a],                              // setr
101        9 => a,                                        // seti
102        10 => usize::from(a > register[b]),            // gtir
103        11 => usize::from(register[a] > b),            // gtri
104        12 => usize::from(register[a] > register[b]),  // gtrr
105        13 => usize::from(a == register[b]),           // eqir
106        14 => usize::from(register[a] == b),           // eqri
107        15 => usize::from(register[a] == register[b]), // eqrr
108        _ => unreachable!(),
109    }
110}
aoc/year2018/day16.rs

aoc/year2018/
day16.rs
