aoc/year2016/
day13.rs

1//! # A Maze of Twisty Little Cubicles
2//!
3//! We first generate the maze dynamically then explore it using a
4//! [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) solving both part one and part
5//! two simultaneously.
6//!
7//! As we start at (1, 1) and the most steps that we are interested in for part two is 50, while
8//! part one requires more than 50 steps but should easily be reachable without exceeding bounds,
9//! we can bound the maze to 2 + 50 = 52 in each dimension and use a fixed size array.  Rather
10//! than filling the array up front, we can lazily populate it as the horizon expands.
11
12use crate::util::parse::*;
13use std::collections::VecDeque;
14
15type Input = (u32, u32);
16
17pub fn parse(input: &str) -> Input {
18    let favorite: usize = input.unsigned();
19
20    // Lazy evaluation: set maze[x][y] to true once a point is visited
21    let mut maze = [[false; 52]; 52];
22    maze[1][1] = true;
23    let mut at = |x: usize, y: usize| -> bool {
24        if maze[x][y] {
25            return false;
26        }
27        maze[x][y] = true;
28        let n = (x * x) + (3 * x) + (2 * x * y) + y + (y * y) + favorite;
29        n.count_ones().is_multiple_of(2)
30    };
31
32    let mut part_two = 0;
33    let mut todo = VecDeque::new();
34
35    todo.push_back((1, 1, 0));
36
37    while let Some((x, y, cost)) = todo.pop_front() {
38        // Target is at least 68 moves from the start. Since we're doing a BFS we're guaranteed
39        // to have checked all locations less than or equal to 50 before reaching the target.
40        if x == 31 && y == 39 {
41            return (cost, part_two);
42        }
43        if cost <= 50 {
44            part_two += 1;
45        }
46
47        if x > 0 && at(x - 1, y) {
48            todo.push_back((x - 1, y, cost + 1));
49        }
50        if y > 0 && at(x, y - 1) {
51            todo.push_back((x, y - 1, cost + 1));
52        }
53        if at(x + 1, y) {
54            todo.push_back((x + 1, y, cost + 1));
55        }
56        if at(x, y + 1) {
57            todo.push_back((x, y + 1, cost + 1));
58        }
59    }
60
61    unreachable!()
62}
63
64pub fn part1(input: &Input) -> u32 {
65    input.0
66}
67
68pub fn part2(input: &Input) -> u32 {
69    input.1
70}
aoc/year2016/day13.rs

aoc/year2016/
day13.rs
