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

aoc/year2018/
day20.rs
