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.
11use crate::util::parse::*;
12use std::collections::VecDeque;
13
14type Input = (u32, u32);
15
16pub fn parse(input: &str) -> Input {
17    let favorite: usize = input.unsigned();
18
19    // Lazy evaluation. Set maze[x][y] to true once a point is visited.
20    let mut maze = [[false; 52]; 52];
21    maze[1][1] = true;
22    let mut at = |x: usize, y: usize| -> bool {
23        if maze[x][y] {
24            return false;
25        }
26        maze[x][y] = true;
27        let n = (x * x) + (3 * x) + (2 * x * y) + y + (y * y) + favorite;
28        n.count_ones().is_multiple_of(2)
29    };
30
31    let mut part_two = 0;
32    let mut todo = VecDeque::new();
33
34    todo.push_back((1, 1, 0));
35
36    while let Some((x, y, cost)) = todo.pop_front() {
37        // Target is at least 68 moves from the start. Since we're doing a BFS we're guaranteed
38        // to have checked all locations less than or equal to 50 before reaching the target.
39        if x == 31 && y == 39 {
40            return (cost, part_two);
41        }
42        if cost <= 50 {
43            part_two += 1;
44        }
45
46        if x > 0 && at(x - 1, y) {
47            todo.push_back((x - 1, y, cost + 1));
48        }
49        if y > 0 && at(x, y - 1) {
50            todo.push_back((x, y - 1, cost + 1));
51        }
52        if at(x + 1, y) {
53            todo.push_back((x + 1, y, cost + 1));
54        }
55        if at(x, y + 1) {
56            todo.push_back((x, y + 1, cost + 1));
57        }
58    }
59
60    unreachable!()
61}
62
63pub fn part1(input: &Input) -> u32 {
64    input.0
65}
66
67pub fn part2(input: &Input) -> u32 {
68    input.1
69}
aoc/year2016/day13.rs

aoc/year2016/
day13.rs
