year2019/
day15.rs

1use crate::intcode::features::Day09Features;
2use crate::intcode::{Event, Interpreter};
3use std::collections::VecDeque;
4use utils::prelude::*;
5
6/// Interpreting machine code to find the shortest path in a maze.
7#[derive(Clone, Debug)]
8pub struct Day15 {
9    part1: u32,
10    part2: u32,
11}
12
13#[derive(Clone, Copy, Debug)]
14struct Frame {
15    index: usize,
16    next_direction: usize,
17    backtrack: i64,
18}
19
20#[derive(Clone, Copy, Debug, PartialEq)]
21enum MoveResult {
22    HitWall,
23    Moved,
24    FoundOxygen,
25}
26
27#[derive(Clone, Copy, Debug, PartialEq)]
28#[repr(u8)]
29enum State {
30    Unknown,
31    Wall,
32    Open,
33}
34
35const WIDTH: usize = 49;
36const SIZE: usize = WIDTH * WIDTH;
37const START_INDEX: usize = (WIDTH / 2) * WIDTH + (WIDTH / 2);
38const DIRECTIONS: [(isize, i64, i64); 4] = [
39    (-(WIDTH as isize), 1, 2),
40    (WIDTH as isize, 2, 1),
41    (-1, 3, 4),
42    (1, 4, 3),
43];
44
45impl Day15 {
46    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
47        let mut interpreter = Interpreter::parse(input, 1)?;
48        let mut try_move = |movement_command: i64| {
49            interpreter.push_input(movement_command);
50
51            // Return error instead of panicking like Interpreter::expect_output
52            match interpreter.run::<Day09Features>() {
53                Event::Output(0) => Ok(MoveResult::HitWall),
54                Event::Output(1) => Ok(MoveResult::Moved),
55                Event::Output(2) => Ok(MoveResult::FoundOxygen),
56                Event::Halt | Event::Input | Event::Output(_) => Err(InputError::new(
57                    input,
58                    0,
59                    "expected program to output status",
60                )),
61            }
62        };
63
64        let mut grid = [State::Unknown; SIZE];
65        grid[START_INDEX] = State::Open;
66        let mut oxygen_index = None;
67
68        let mut stack = Vec::with_capacity(SIZE);
69        stack.push(Frame {
70            index: START_INDEX,
71            next_direction: 0,
72            backtrack: 0,
73        });
74
75        while let Some(frame) = stack.last_mut() {
76            if frame.next_direction == DIRECTIONS.len() {
77                if frame.backtrack != 0
78                    && let MoveResult::HitWall = try_move(frame.backtrack)?
79                {
80                    return Err(InputError::new(
81                        input,
82                        0,
83                        "expected backtracking move to succeed",
84                    ));
85                }
86
87                stack.pop();
88                continue;
89            }
90
91            let (delta, command, backtrack) = DIRECTIONS[frame.next_direction];
92            frame.next_direction += 1;
93
94            let next = frame.index.wrapping_add_signed(delta);
95            if !(WIDTH..SIZE - WIDTH).contains(&next)
96                || next % WIDTH == 0
97                || next % WIDTH == WIDTH - 1
98            {
99                return Err(InputError::new(input, 0, "grid too large"));
100            }
101
102            if grid[next] != State::Unknown {
103                continue;
104            }
105
106            let result = try_move(command)?;
107            if result == MoveResult::HitWall {
108                grid[next] = State::Wall;
109            } else {
110                grid[next] = State::Open;
111                stack.push(Frame {
112                    index: next,
113                    next_direction: 0,
114                    backtrack,
115                });
116
117                if result == MoveResult::FoundOxygen {
118                    if oxygen_index.is_some() {
119                        return Err(InputError::new(input, 0, "duplicate oxygen systems"));
120                    }
121                    oxygen_index = Some(next);
122                }
123            }
124        }
125
126        let Some(oxygen_index) = oxygen_index else {
127            return Err(InputError::new(input, 0, "no oxygen system found"));
128        };
129
130        let mut queue = VecDeque::new();
131        queue.push_back(oxygen_index);
132        grid[oxygen_index] = State::Wall;
133
134        let mut part1 = 0;
135        let mut minutes = 0;
136
137        loop {
138            for _ in 0..queue.len() {
139                let index = queue.pop_front().unwrap();
140                if index == START_INDEX {
141                    part1 = minutes;
142                }
143
144                for offset in [-(WIDTH as isize), -1, 1, WIDTH as isize] {
145                    let next = index.wrapping_add_signed(offset);
146                    if grid[next] == State::Open {
147                        grid[next] = State::Wall;
148                        queue.push_back(next);
149                    }
150                }
151            }
152
153            if queue.is_empty() {
154                break;
155            }
156
157            minutes += 1;
158        }
159
160        Ok(Self {
161            part1,
162            part2: minutes,
163        })
164    }
165
166    #[must_use]
167    pub fn part1(&self) -> u32 {
168        self.part1
169    }
170
171    #[must_use]
172    pub fn part2(&self) -> u32 {
173        self.part2
174    }
175}
176
177examples!(Day15 -> (u32, u32) []);
year2019/day15.rs

year2019/
day15.rs
