year2018/
day16.rs

1use utils::prelude::*;
2
3/// Inferring opcode operations from examples.
4///
5/// See also [day 19](crate::Day19) and [day 21](crate::Day21).
6#[derive(Clone, Debug)]
7pub struct Day16 {
8    samples: Vec<(u32, u16)>,
9    instructions: Vec<(u32, [u32; 3])>,
10}
11
12utils::enumerable_enum! {
13    #[repr(u32)]
14    #[derive(Copy, Clone, Debug)]
15    enum Operation {
16        Addr,
17        Addi,
18        Mulr,
19        Muli,
20        Banr,
21        Bani,
22        Borr,
23        Bori,
24        Setr,
25        Seti,
26        Gtir,
27        Gtri,
28        Gtrr,
29        Eqir,
30        Eqri,
31        Eqrr,
32    }
33}
34
35impl Day16 {
36    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
37        let registers = parser::digit().map(u32::from).repeat_n::<4, _>(", ");
38        let instruction = parser::number_range(0u32..=15)
39            .with_suffix(b' ')
40            .then(parser::number_range(0u32..=3).repeat_n::<3, _>(b' '));
41        let sample = registers
42            .with_prefix("Before: [")
43            .with_suffix("]".then(parser::eol()))
44            .then(instruction.with_suffix(parser::eol()))
45            .then(
46                registers
47                    .with_prefix("After:  [")
48                    .with_suffix("]".then(parser::eol())),
49            )
50            .map(|(before, (opcode, [a, b, c]), after)| {
51                (
52                    opcode,
53                    // Convert the before and after registers and the operands into a mask of
54                    // possible operations as used in both parts.
55                    Operation::iter().fold(0, |acc, op| {
56                        let possible = Self::execute(op, a, b, &before) == after[c as usize];
57                        acc | (possible as u16) << op as u32
58                    }),
59                )
60            });
61
62        let (samples, instructions) = sample
63            .repeat(parser::eol(), 1)
64            .with_eol()
65            .with_eol()
66            .with_eol()
67            .then(instruction.repeat(parser::eol(), 1))
68            .parse_complete(input)?;
69
70        Ok(Self {
71            samples,
72            instructions,
73        })
74    }
75
76    #[must_use]
77    pub fn part1(&self) -> usize {
78        self.samples
79            .iter()
80            .filter(|&(_, mask)| mask.count_ones() >= 3)
81            .count()
82    }
83
84    #[must_use]
85    pub fn part2(&self) -> u32 {
86        let mut op_masks = [u16::MAX; 16];
87        for &(opcode, mask) in &self.samples {
88            op_masks[opcode as usize] &= mask;
89        }
90
91        let mut ops = [Operation::Addi; 16];
92        for _ in 0..16 {
93            let opcode = op_masks
94                .iter()
95                .position(|&mask| mask.count_ones() == 1)
96                .expect("no solution found: all remaining opcodes could be multiple operations");
97
98            let mask = op_masks[opcode];
99            ops[opcode] = Operation::from_discriminant(mask.trailing_zeros());
100
101            op_masks.iter_mut().for_each(|m| *m &= !mask);
102        }
103
104        let mut registers = [0; 4];
105        for &(opcode, [a, b, c]) in &self.instructions {
106            registers[c as usize] = Self::execute(ops[opcode as usize], a, b, &registers);
107        }
108        registers[0]
109    }
110
111    #[inline]
112    fn execute(op: Operation, a: u32, b: u32, registers: &[u32; 4]) -> u32 {
113        match op {
114            Operation::Addr => registers[a as usize] + registers[b as usize],
115            Operation::Addi => registers[a as usize] + b,
116            Operation::Mulr => registers[a as usize] * registers[b as usize],
117            Operation::Muli => registers[a as usize] * b,
118            Operation::Banr => registers[a as usize] & registers[b as usize],
119            Operation::Bani => registers[a as usize] & b,
120            Operation::Borr => registers[a as usize] | registers[b as usize],
121            Operation::Bori => registers[a as usize] | b,
122            Operation::Setr => registers[a as usize],
123            Operation::Seti => a,
124            Operation::Gtir => u32::from(a > registers[b as usize]),
125            Operation::Gtri => u32::from(registers[a as usize] > b),
126            Operation::Gtrr => u32::from(registers[a as usize] > registers[b as usize]),
127            Operation::Eqir => u32::from(a == registers[b as usize]),
128            Operation::Eqri => u32::from(registers[a as usize] == b),
129            Operation::Eqrr => u32::from(registers[a as usize] == registers[b as usize]),
130        }
131    }
132}
133
134examples!(Day16 -> (usize, u32) []);
year2018/day16.rs

year2018/
day16.rs
