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 std::collections::VecDeque;
12
13use crate::util::parse::*;
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 visit = |x: usize, y: usize| {
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::from([(1, 1, 0)]);
34
35    while let Some((x, y, cost)) = todo.pop_front() {
36        // Target is at least 68 moves from the start. Since we're doing a BFS we're guaranteed
37        // to have checked all locations less than or equal to 50 before reaching the target.
38        if x == 31 && y == 39 {
39            return (cost, part_two);
40        }
41        if cost <= 50 {
42            part_two += 1;
43        }
44
45        if x > 0 && visit(x - 1, y) {
46            todo.push_back((x - 1, y, cost + 1));
47        }
48        if y > 0 && visit(x, y - 1) {
49            todo.push_back((x, y - 1, cost + 1));
50        }
51        if visit(x + 1, y) {
52            todo.push_back((x + 1, y, cost + 1));
53        }
54        if visit(x, y + 1) {
55            todo.push_back((x, y + 1, cost + 1));
56        }
57    }
58
59    unreachable!()
60}
61
62pub fn part1(input: &Input) -> u32 {
63    input.0
64}
65
66pub fn part2(input: &Input) -> u32 {
67    input.1
68}
aoc/year2016/day13.rs

aoc/year2016/
day13.rs
