aoc/year2020/
day08.rs

1//! # Handheld Halting
2//!
3//! A brute force implementation that changes every `Jmp` or `Nop` in the input one at at time then
4//! tests the result would have `O(n²)` complexity for part two.
5//!
6//! We can solve part two in `O(n)` complexity, executing each instruction at most twice. We start
7//! the same as the brute force solution by stepping through the input speculatively changing each
8//! `Nop` to a `Jmp` or vice-versa, then executing the remaining program from that point and
9//! checking if it finishes.
10//!
11//! The trick is to re-use the `visited` vec that stores if we have executed an instruction before.
12//! As each previous failed code path will have executed some instructions, trying to execute an
13//! instruction twice means that we know immediately we are on a bad path and can stop.
14use crate::util::iter::*;
15use crate::util::parse::*;
16
17pub enum Instruction {
18    Acc(i16),
19    Jmp(i16),
20    Nop(i16),
21}
22
23impl Instruction {
24    fn from([a, b]: [&str; 2]) -> Instruction {
25        let amount = b.signed();
26        match a {
27            "acc" => Instruction::Acc(amount),
28            "jmp" => Instruction::Jmp(amount),
29            "nop" => Instruction::Nop(amount),
30            _ => unreachable!(),
31        }
32    }
33}
34
35enum State {
36    Infinite(i32),
37    Halted(i32),
38}
39
40pub fn parse(input: &str) -> Vec<Instruction> {
41    input.split_ascii_whitespace().chunk::<2>().map(Instruction::from).collect()
42}
43
44pub fn part1(input: &[Instruction]) -> i32 {
45    let mut visited = vec![false; input.len()];
46
47    match execute(input, 0, 0, &mut visited) {
48        State::Infinite(acc) => acc,
49        State::Halted(_) => unreachable!(),
50    }
51}
52
53pub fn part2(input: &[Instruction]) -> i32 {
54    let mut pc = 0;
55    let mut acc = 0;
56    let visited = &mut vec![false; input.len()];
57
58    loop {
59        match input[pc] {
60            Instruction::Acc(arg) => {
61                pc += 1;
62                acc += arg as i32;
63            }
64            Instruction::Jmp(arg) => {
65                let speculative = pc + 1;
66                match execute(input, speculative, acc, visited) {
67                    State::Infinite(_) => pc = pc.wrapping_add(arg as usize),
68                    State::Halted(acc) => break acc,
69                }
70            }
71            Instruction::Nop(arg) => {
72                let speculative = pc.wrapping_add(arg as usize);
73                match execute(input, speculative, acc, visited) {
74                    State::Infinite(_) => pc += 1,
75                    State::Halted(acc) => break acc,
76                }
77            }
78        }
79    }
80}
81
82fn execute(input: &[Instruction], mut pc: usize, mut acc: i32, visited: &mut [bool]) -> State {
83    loop {
84        if pc >= input.len() {
85            break State::Halted(acc);
86        } else if visited[pc] {
87            break State::Infinite(acc);
88        }
89
90        visited[pc] = true;
91
92        match input[pc] {
93            Instruction::Acc(arg) => {
94                pc += 1;
95                acc += arg as i32;
96            }
97            Instruction::Jmp(arg) => {
98                pc = pc.wrapping_add(arg as usize);
99            }
100            Instruction::Nop(_) => {
101                pc += 1;
102            }
103        }
104    }
105}
aoc/year2020/day08.rs

aoc/year2020/
day08.rs
