aoc/year2020/
day08.rs

1//! # Handheld Halting
2//!
3//! A brute force implementation that changes every `Jmp` or `Nop` in the input one at a 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 reuse the `seen` 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(isize),
19    Jmp(isize),
20    Nop(isize),
21}
22
23impl Instruction {
24    fn from([a, b]: [&str; 2]) -> Self {
25        let amount = b.signed();
26        match a {
27            "acc" => Self::Acc(amount),
28            "jmp" => Self::Jmp(amount),
29            "nop" => Self::Nop(amount),
30            _ => unreachable!(),
31        }
32    }
33}
34
35enum State {
36    Infinite(isize),
37    Halted(isize),
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]) -> isize {
45    let mut seen = vec![false; input.len()];
46
47    match execute(input, 0, 0, &mut seen) {
48        State::Infinite(acc) => acc,
49        State::Halted(_) => unreachable!(),
50    }
51}
52
53pub fn part2(input: &[Instruction]) -> isize {
54    let mut pc = 0;
55    let mut acc = 0;
56    let mut seen = vec![false; input.len()];
57
58    loop {
59        let (next, speculative) = match input[pc] {
60            Instruction::Acc(arg) => {
61                pc += 1;
62                acc += arg;
63                continue;
64            }
65            Instruction::Jmp(arg) => (pc.wrapping_add_signed(arg), pc + 1),
66            Instruction::Nop(arg) => (pc + 1, pc.wrapping_add_signed(arg)),
67        };
68
69        match execute(input, speculative, acc, &mut seen) {
70            State::Infinite(_) => pc = next,
71            State::Halted(acc) => break acc,
72        }
73    }
74}
75
76fn execute(input: &[Instruction], mut pc: usize, mut acc: isize, seen: &mut [bool]) -> State {
77    loop {
78        if pc >= input.len() {
79            break State::Halted(acc);
80        } else if seen[pc] {
81            break State::Infinite(acc);
82        }
83
84        seen[pc] = true;
85
86        match input[pc] {
87            Instruction::Acc(arg) => {
88                pc += 1;
89                acc += arg;
90            }
91            Instruction::Jmp(arg) => pc = pc.wrapping_add_signed(arg),
92            Instruction::Nop(_) => pc += 1,
93        }
94    }
95}
aoc/year2020/day08.rs

aoc/year2020/
day08.rs
