year2017/
day23.rs

1use utils::number::is_prime;
2use utils::prelude::*;
3
4/// Interpreting assembly to count composite numbers.
5///
6/// Uses a modified version of the interpreter from [day 18](crate::Day18).
7#[derive(Clone, Debug)]
8pub struct Day23 {
9    instructions: Vec<Instruction>,
10}
11
12#[derive(Copy, Clone, Debug, PartialEq)]
13enum Register {
14    A,
15    B,
16    C,
17    D,
18    E,
19    F,
20    G,
21    H,
22}
23
24#[derive(Copy, Clone, Debug, PartialEq)]
25enum Instruction {
26    Set(Register, Register),
27    SetN(Register, i32),
28    Sub(Register, Register),
29    SubN(Register, i32),
30    Mul(Register, Register),
31    MulN(Register, i32),
32    JnzN(Register, i32),
33    Jmp(i32), // Used for jnz $n where $n != 0
34    Noop(),   // Used for jgz $n where $n == 0
35}
36
37impl Day23 {
38    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
39        let register = parser::literal_map!(
40            "a" => Register::A,
41            "b" => Register::B,
42            "c" => Register::C,
43            "d" => Register::D,
44            "e" => Register::E,
45            "f" => Register::F,
46            "g" => Register::G,
47            "h" => Register::H,
48        );
49
50        let instruction = parser::parse_tree!(
51            ("set ", r @ register, b' ') =>> {
52                (r2 @ register) => Instruction::Set(r, r2),
53                (v @ parser::i32()) => Instruction::SetN(r, v),
54            },
55            ("sub ", r @ register, b' ') =>> {
56                (r2 @ register) => Instruction::Sub(r, r2),
57                (v @ parser::i32()) => Instruction::SubN(r, v),
58            },
59            ("mul ", r @ register, b' ') =>> {
60                (r2 @ register) => Instruction::Mul(r, r2),
61                (v @ parser::i32()) => Instruction::MulN(r, v),
62            },
63            ("jnz ") =>> {
64                (r @ register, b' ', v @parser::i32()) => Instruction::JnzN(r, v),
65                (x @ parser::i32(), b' ', v @ parser::i32()) => {
66                    if x != 0 {
67                        Instruction::Jmp(v)
68                    } else {
69                        Instruction::Noop()
70                    }
71                },
72            },
73        );
74
75        Ok(Self {
76            instructions: instruction.parse_lines(input)?,
77        })
78    }
79
80    #[must_use]
81    pub fn part1(&self) -> u64 {
82        self.run(&mut [0; 8])
83    }
84
85    #[must_use]
86    pub fn part2(&self) -> i64 {
87        let mut reg = [1, 0, 0, 0, 0, 0, 0, 0];
88        self.run(&mut reg);
89        reg[Register::H as usize]
90    }
91
92    fn run(&self, reg: &mut [i64; 8]) -> u64 {
93        let mut pc = 0;
94        let mut mul_count = 0;
95        while pc < self.instructions.len() {
96            #[rustfmt::skip] // Rustfmt wants the pattern to be on a single long line
97            match self.instructions[pc..] {
98                // Recognize the naive prime check and replace it with a native implementation
99                //   set $d 2
100                //   set $e 2
101                //   set $g $d
102                //   mul $g $e
103                //   sub $g $b
104                //   jnz $g 2
105                //   set $f 0
106                //   sub $e -1
107                //   set $g $e
108                //   sub $g $b
109                //   jnz $g -8
110                //   sub $d -1
111                //   set $g $d
112                //   sub $g $b
113                //   jnz $g -13
114                [
115                    Instruction::SetN(d, 2),
116                    Instruction::SetN(e, 2),
117                    Instruction::Set(g, d2),
118                    Instruction::Mul(g2, e2),
119                    Instruction::Sub(g3, b),
120                    Instruction::JnzN(g4, 2),
121                    Instruction::SetN(f, 0),
122                    Instruction::SubN(e3, -1),
123                    Instruction::Set(g5, e4),
124                    Instruction::Sub(g6, b2),
125                    Instruction::JnzN(g7, -8),
126                    Instruction::SubN(d3, -1),
127                    Instruction::Set(g8, d4),
128                    Instruction::Sub(g9, b3),
129                    Instruction::JnzN(g10, -13),
130                    ..
131                ] if b == b2 && b == b3 && reg[b as usize] >= 0
132                    && d == d2 && d == d3 && d == d4
133                    && e == e2 && e == e3 && e == e4
134                    && g == g2 && g == g3 && g == g4 && g == g5&& g == g6 && g == g7 && g == g8 && g == g9 && g == g10
135                => {
136                    reg[d as usize] = reg[b as usize];
137                    reg[e as usize] = reg[b as usize];
138                    if !is_prime(reg[b as usize] as u64) {
139                        reg[f as usize] = 0;
140                    }
141                    reg[g as usize] = 0;
142                    pc += 15;
143                    mul_count += (reg[b as usize] - 2).pow(2) as u64;
144                    continue;
145                }
146                _ => {},
147            };
148
149            match self.instructions[pc] {
150                Instruction::Set(r, r2) => reg[r as usize] = reg[r2 as usize],
151                Instruction::SetN(r, v) => reg[r as usize] = v as i64,
152                Instruction::Sub(r, r2) => reg[r as usize] -= reg[r2 as usize],
153                Instruction::SubN(r, v) => reg[r as usize] -= v as i64,
154                Instruction::Mul(r, r2) => {
155                    reg[r as usize] *= reg[r2 as usize];
156                    mul_count += 1;
157                }
158                Instruction::MulN(r, v) => {
159                    reg[r as usize] *= v as i64;
160                    mul_count += 1;
161                }
162                Instruction::JnzN(r, o) => {
163                    if reg[r as usize] != 0 {
164                        pc = pc.wrapping_add_signed(o as isize);
165                        continue;
166                    }
167                }
168                Instruction::Jmp(o) => {
169                    pc = pc.wrapping_add_signed(o as isize);
170                    continue;
171                }
172                Instruction::Noop() => {}
173            }
174
175            pc += 1;
176        }
177        mul_count
178    }
179}
180
181examples!(Day23 -> (u64, i64) []);
year2017/day23.rs

year2017/
day23.rs
