aoc/year2019/
day15.rs

1//! # Oxygen System
2//!
3//! [Breadth first search](https://en.wikipedia.org/wiki/Breadth-first_search) is the simplest
4//! path finding 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 path finding 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 super::intcode::*;
13use crate::util::hash::*;
14use crate::util::parse::*;
15use crate::util::point::*;
16use std::collections::VecDeque;
17
18type Input = (FastSet<Point>, Point);
19
20/// Build the shape of the maze using the right-hand version of the wall following algorithm.
21pub fn parse(input: &str) -> Input {
22    let code: Vec<_> = input.iter_signed().collect();
23    let mut computer = Computer::new(&code);
24
25    let mut paths = FastSet::with_capacity(1_000);
26    let mut walls = FastSet::with_capacity(1_000);
27
28    let mut first = true;
29    let mut direction = UP;
30    let mut position = ORIGIN;
31    let mut oxygen_system = ORIGIN;
32
33    loop {
34        direction = if first { direction.clockwise() } else { direction.counter_clockwise() };
35        let next = position + direction;
36
37        if walls.contains(&next) {
38            first = false;
39            continue;
40        }
41
42        match direction {
43            UP => computer.input(1),
44            DOWN => computer.input(2),
45            LEFT => computer.input(3),
46            RIGHT => computer.input(4),
47            _ => unreachable!(),
48        }
49
50        match computer.run() {
51            State::Output(0) => {
52                first = false;
53                walls.insert(next);
54            }
55            State::Output(result) => {
56                first = true;
57                position = next;
58                paths.insert(next);
59
60                if result == 2 {
61                    oxygen_system = position;
62                }
63                if position == ORIGIN {
64                    break;
65                }
66            }
67            _ => unreachable!(),
68        }
69    }
70
71    (paths, oxygen_system)
72}
73
74/// BFS from the starting point until we find the oxygen system.
75pub fn part1(input: &Input) -> i32 {
76    let (mut maze, oxygen_system) = input.clone();
77    let mut todo = VecDeque::from([(ORIGIN, 0)]);
78
79    maze.remove(&ORIGIN);
80
81    while let Some((point, cost)) = todo.pop_front() {
82        if point == oxygen_system {
83            return cost;
84        }
85
86        for next in ORTHOGONAL.map(|o| point + o) {
87            if maze.remove(&next) {
88                todo.push_back((next, cost + 1));
89            }
90        }
91    }
92
93    unreachable!()
94}
95
96/// BFS from the oxygen system to all points in the maze.
97pub fn part2(input: &Input) -> i32 {
98    let (mut maze, oxygen_system) = input.clone();
99    let mut todo = VecDeque::from([(oxygen_system, 0)]);
100    let mut minutes = 0;
101
102    maze.remove(&ORIGIN);
103
104    while let Some((point, cost)) = todo.pop_front() {
105        minutes = minutes.max(cost);
106
107        for next in ORTHOGONAL.map(|o| point + o) {
108            if maze.remove(&next) {
109                todo.push_back((next, cost + 1));
110            }
111        }
112    }
113
114    minutes
115}
aoc/year2019/day15.rs

aoc/year2019/
day15.rs
