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 crate::util::hash::*;
15use crate::util::intcode::*;
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 (maze, oxygen_system) = input.clone();
78    bfs(maze, ORIGIN, Some(oxygen_system))
79}
80
81/// BFS from the oxygen system to every point in the maze.
82pub fn part2(input: &Input) -> i32 {
83    let (maze, oxygen_system) = input.clone();
84    bfs(maze, oxygen_system, None)
85}
86
87/// Returns the cost to reach `end` or the cost to reach the furthest point if there is no target.
88fn bfs(mut maze: FastSet<Point>, start: Point, end: Option<Point>) -> i32 {
89    let mut todo = VecDeque::from([(start, 0)]);
90    let mut result = 0;
91
92    maze.remove(&start);
93
94    while let Some((point, cost)) = todo.pop_front() {
95        result = cost;
96
97        if end == Some(point) {
98            break;
99        }
100
101        for next in ORTHOGONAL.map(|o| point + o) {
102            if maze.remove(&next) {
103                todo.push_back((next, cost + 1));
104            }
105        }
106    }
107
108    result
109}
aoc/year2019/day15.rs

aoc/year2019/
day15.rs
