aoc/year2019/
day15.rs

1//! # Oxygen System
2//!
3//! [Breadth-first search](https://en.wikipedia.org/wiki/Breadth-first_search) is the simplest
4//! pathfinding algorithm and is suitable when the cost of moving between locations is identical.
5//! [This excellent blog](https://www.redblobgames.com/pathfinding/a-star/introduction.html)
6//! has more detail on the various pathfinding algorithms that come in handy during Advent of Code.
7//!
8//! The tricky part is determining the shape of the maze. If we assume the maze consists only of
9//! corridors of width one and has no loops or rooms, then we can use the simple
10//! [wall follower](https://en.wikipedia.org/wiki/Maze-solving_algorithm#Wall_follower)
11//! algorithm to eventually trace our way through the entire maze back to the starting point.
12use std::collections::VecDeque;
13
14use super::intcode::*;
15use crate::util::hash::*;
16use crate::util::parse::*;
17use crate::util::point::*;
18
19type Input = (FastSet<Point>, Point);
20
21/// Build the shape of the maze using the right-hand version of the wall following algorithm.
22pub fn parse(input: &str) -> Input {
23    let code: Vec<_> = input.iter_signed().collect();
24    let mut computer = Computer::new(&code);
25
26    let mut paths = FastSet::with_capacity(1_000);
27    let mut walls = FastSet::with_capacity(1_000);
28
29    let mut first = true;
30    let mut direction = UP;
31    let mut position = ORIGIN;
32    let mut oxygen_system = ORIGIN;
33
34    loop {
35        direction = if first { direction.clockwise() } else { direction.counter_clockwise() };
36        let next = position + direction;
37
38        if walls.contains(&next) {
39            first = false;
40            continue;
41        }
42
43        computer.input(match direction {
44            UP => 1,
45            DOWN => 2,
46            LEFT => 3,
47            RIGHT => 4,
48            _ => unreachable!(),
49        });
50
51        match computer.run() {
52            State::Output(0) => {
53                first = false;
54                walls.insert(next);
55            }
56            State::Output(result) => {
57                first = true;
58                position = next;
59                paths.insert(next);
60
61                if result == 2 {
62                    oxygen_system = position;
63                }
64                if position == ORIGIN {
65                    break;
66                }
67            }
68            _ => unreachable!(),
69        }
70    }
71
72    (paths, oxygen_system)
73}
74
75/// BFS from the starting point until we find the oxygen system.
76pub fn part1(input: &Input) -> i32 {
77    let (mut maze, oxygen_system) = input.clone();
78    let mut todo = VecDeque::from([(ORIGIN, 0)]);
79
80    maze.remove(&ORIGIN);
81
82    while let Some((point, cost)) = todo.pop_front() {
83        if point == oxygen_system {
84            return cost;
85        }
86
87        for next in ORTHOGONAL.map(|o| point + o) {
88            if maze.remove(&next) {
89                todo.push_back((next, cost + 1));
90            }
91        }
92    }
93
94    unreachable!()
95}
96
97/// BFS from the oxygen system to all points in the maze.
98pub fn part2(input: &Input) -> i32 {
99    let (mut maze, oxygen_system) = input.clone();
100    let mut todo = VecDeque::from([(oxygen_system, 0)]);
101    let mut minutes = 0;
102
103    maze.remove(&oxygen_system);
104
105    while let Some((point, cost)) = todo.pop_front() {
106        minutes = cost;
107
108        for next in ORTHOGONAL.map(|o| point + o) {
109            if maze.remove(&next) {
110                todo.push_back((next, cost + 1));
111            }
112        }
113    }
114
115    minutes
116}
aoc/year2019/day15.rs

aoc/year2019/
day15.rs
