year2020/
day08.rs

1use utils::prelude::*;
2
3/// Interpreting assembly and fixing an infinite loop.
4#[derive(Clone, Debug)]
5pub struct Day08 {
6    part1: i32,
7    part2: i32,
8}
9
10#[derive(Copy, Clone, Debug)]
11enum Instruction {
12    Acc(i32),
13    Jmp(i32),
14    Nop(i32),
15}
16
17#[derive(Copy, Clone, Debug, Eq, PartialEq)]
18enum State {
19    Unvisited,
20    Loops,
21    Terminates,
22}
23
24impl Day08 {
25    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
26        if input.is_empty() {
27            return Err(InputError::new(input, 0, "expected instruction"));
28        }
29
30        let instructions = parser::parse_tree!(
31            ("acc ", v @ parser::i32()) => Instruction::Acc(v),
32            ("jmp ", v @ parser::i32()) => Instruction::Jmp(v),
33            ("nop ", v @ parser::i32()) => Instruction::Nop(v),
34        )
35        .parse_lines(input)?;
36
37        let len = instructions.len();
38        let mut outcomes = vec![State::Unvisited; len + 1];
39        let mut alternatives = Vec::with_capacity(len);
40        outcomes[len] = State::Terminates;
41
42        let (mut pc, mut part1) = (0, 0);
43        while outcomes.get(pc) == Some(&State::Unvisited) {
44            outcomes[pc] = State::Loops;
45
46            match instructions[pc] {
47                Instruction::Acc(value) => {
48                    part1 += value;
49                    pc += 1;
50                }
51                Instruction::Jmp(offset) => {
52                    alternatives.push((pc + 1, part1));
53                    pc = pc.wrapping_add_signed(offset as isize);
54                }
55                Instruction::Nop(offset) => {
56                    alternatives.push((pc.wrapping_add_signed(offset as isize), part1));
57                    pc += 1;
58                }
59            };
60        }
61
62        if pc >= len {
63            return Err(InputError::new(input, 0, "expected program to loop"));
64        }
65
66        let mut path = Vec::with_capacity(len);
67        let mut suffix_sums = vec![0; len + 1];
68        for &(alternate_pc, alternative_acc) in alternatives.iter().rev() {
69            if alternate_pc > len {
70                continue;
71            }
72
73            if outcomes[alternate_pc] == State::Unvisited {
74                path.clear();
75                pc = alternate_pc;
76                while pc < len && outcomes[pc] == State::Unvisited {
77                    outcomes[pc] = State::Loops;
78                    path.push(pc);
79                    pc = match instructions[pc] {
80                        Instruction::Acc(_) | Instruction::Nop(_) => pc + 1,
81                        Instruction::Jmp(offset) => {
82                            pc.checked_add_signed(offset as isize).unwrap_or(usize::MAX)
83                        }
84                    };
85                }
86
87                if pc <= len && outcomes[pc] == State::Terminates {
88                    let mut acc = suffix_sums[pc];
89                    for &pc in path.iter().rev() {
90                        if let Instruction::Acc(value) = instructions[pc] {
91                            acc += value;
92                        }
93                        suffix_sums[pc] = acc;
94                        outcomes[pc] = State::Terminates;
95                    }
96                }
97            }
98
99            if outcomes[alternate_pc] == State::Terminates {
100                return Ok(Self {
101                    part1,
102                    part2: alternative_acc + suffix_sums[alternate_pc],
103                });
104            }
105        }
106
107        Err(InputError::new(
108            input,
109            0,
110            "expected one corrupted instruction",
111        ))
112    }
113
114    #[must_use]
115    pub fn part1(&self) -> i32 {
116        self.part1
117    }
118
119    #[must_use]
120    pub fn part2(&self) -> i32 {
121        self.part2
122    }
123}
124
125examples!(Day08 -> (i32, i32) [
126    {file: "day08_example0.txt", part1: 5, part2: 8},
127]);
year2020/day08.rs

year2020/
day08.rs
