aoc/year2018/
day20.rs

1//! # A Regular Map
2//!
3//! Simple solution taking advantage of a controversial property of the input. After taking any
4//! branch it's assumed that we can return to the pre-branch position. This does *not* hold for
5//! general inputs, as it's easy to construct paths which violate this constraint.
6//!
7//! We use a stack to save the position before a branch, pushing whenever an opening `(` is
8//! encountered then popping whenever the closing `)` is found. Additionally we assume that
9//! the location will never move more than 55 rooms from the starting location in order to use
10//! a fixed size array to hold the minimum distance to any room.
11type Input = (u32, usize);
12
13pub fn parse(input: &str) -> Input {
14    explore(input)
15}
16
17pub fn part1(input: &Input) -> u32 {
18    input.0
19}
20
21pub fn part2(input: &Input) -> usize {
22    input.1
23}
24
25fn explore(input: &str) -> Input {
26    // Start in the center.
27    let mut index = 6105;
28    // 55 in each direction, gives a width and height of 110, for a total size of 12,100.
29    let mut grid = vec![u32::MAX; 12_100];
30    let mut stack = Vec::with_capacity(500);
31    let mut part_one = 0;
32
33    grid[index] = 0;
34
35    for b in input.bytes() {
36        let distance = grid[index];
37
38        match b {
39            b'(' => stack.push(index),
40            b'|' => index = stack[stack.len() - 1],
41            b')' => index = stack.pop().unwrap(),
42            b'N' => index -= 110,
43            b'S' => index += 110,
44            b'W' => index -= 1,
45            b'E' => index += 1,
46            _ => (),
47        }
48
49        grid[index] = grid[index].min(distance + 1);
50        part_one = part_one.max(grid[index]);
51    }
52
53    let part_two = grid.iter().filter(|d| (1000..u32::MAX).contains(d)).count();
54    (part_one, part_two)
55}
aoc/year2018/day20.rs

aoc/year2018/
day20.rs
