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    // Start in the center.
15    let mut index = 6105;
16    // 55 in each direction, gives a width and height of 110, for a total size of 12,100.
17    let mut grid = vec![u32::MAX; 12_100];
18    let mut stack = Vec::with_capacity(500);
19    let mut part_one = 0;
20
21    grid[index] = 0;
22
23    for b in input.bytes() {
24        let distance = grid[index];
25
26        match b {
27            b'(' => stack.push(index),
28            b'|' => index = *stack.last().unwrap(),
29            b')' => index = stack.pop().unwrap(),
30            b'N' => index -= 110,
31            b'S' => index += 110,
32            b'W' => index -= 1,
33            b'E' => index += 1,
34            _ => (),
35        }
36
37        grid[index] = grid[index].min(distance + 1);
38        part_one = part_one.max(grid[index]);
39    }
40
41    let part_two = grid.iter().filter(|d| (1000..u32::MAX).contains(d)).count();
42    (part_one, part_two)
43}
44
45pub fn part1(input: &Input) -> u32 {
46    input.0
47}
48
49pub fn part2(input: &Input) -> usize {
50    input.1
51}
aoc/year2018/day20.rs

aoc/year2018/
day20.rs
