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    let mut first = true;
25    let mut direction = UP;
26    let mut position = ORIGIN;
27    let mut oxygen_system = ORIGIN;
28    let mut visited = FastSet::new();
29
30    loop {
31        direction = if first { direction.clockwise() } else { direction.counter_clockwise() };
32
33        match direction {
34            UP => computer.input(1),
35            DOWN => computer.input(2),
36            LEFT => computer.input(3),
37            RIGHT => computer.input(4),
38            _ => unreachable!(),
39        }
40
41        match computer.run() {
42            State::Output(0) => first = false,
43            State::Output(result) => {
44                first = true;
45                position += direction;
46                visited.insert(position);
47
48                if result == 2 {
49                    oxygen_system = position;
50                }
51                if position == ORIGIN {
52                    break;
53                }
54            }
55            _ => unreachable!(),
56        }
57    }
58
59    (visited, oxygen_system)
60}
61
62/// BFS from the starting point until we find the oxygen system.
63pub fn part1(input: &Input) -> i32 {
64    let (mut maze, oxygen_system) = input.clone();
65    let mut todo = VecDeque::from([(ORIGIN, 0)]);
66
67    while let Some((point, cost)) = todo.pop_front() {
68        maze.remove(&point);
69        if point == oxygen_system {
70            return cost;
71        }
72
73        for movement in ORTHOGONAL {
74            let next_point = point + movement;
75            if maze.contains(&next_point) {
76                todo.push_back((next_point, cost + 1));
77            }
78        }
79    }
80
81    unreachable!()
82}
83
84/// BFS from the oxygen system to all points in the maze.
85pub fn part2(input: &Input) -> i32 {
86    let (mut maze, oxygen_system) = input.clone();
87    let mut todo = VecDeque::from([(oxygen_system, 0)]);
88    let mut minutes = 0;
89
90    while let Some((point, cost)) = todo.pop_front() {
91        maze.remove(&point);
92        minutes = minutes.max(cost);
93
94        for movement in ORTHOGONAL {
95            let next_point = point + movement;
96            if maze.contains(&next_point) {
97                todo.push_back((next_point, cost + 1));
98            }
99        }
100    }
101
102    minutes
103}
aoc/year2019/day15.rs

aoc/year2019/
day15.rs
