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 is 50, we can bound
8//! the maze to 2 + 50 = 52 in each dimension and used a fixed size array.
9
10use crate::util::parse::*;
11use std::collections::VecDeque;
12
13type Input = (u32, u32);
14
15pub fn parse(input: &str) -> Input {
16    let favorite: usize = input.unsigned();
17    let mut maze = [[false; 52]; 52];
18
19    for (x, row) in maze.iter_mut().enumerate() {
20        for (y, cell) in row.iter_mut().enumerate() {
21            let n = (x * x) + (3 * x) + (2 * x * y) + y + (y * y) + favorite;
22            *cell = n.count_ones().is_multiple_of(2);
23        }
24    }
25
26    let mut part_one = 0;
27    let mut part_two = 0;
28    let mut todo = VecDeque::new();
29
30    todo.push_back((1, 1, 0));
31    maze[1][1] = false;
32
33    while let Some((x, y, cost)) = todo.pop_front() {
34        if x == 31 && y == 39 {
35            part_one = cost;
36        }
37        if cost <= 50 {
38            part_two += 1;
39        }
40
41        if x > 0 && maze[x - 1][y] {
42            todo.push_back((x - 1, y, cost + 1));
43            maze[x - 1][y] = false;
44        }
45        if y > 0 && maze[x][y - 1] {
46            todo.push_back((x, y - 1, cost + 1));
47            maze[x][y - 1] = false;
48        }
49        if x < 51 && maze[x + 1][y] {
50            todo.push_back((x + 1, y, cost + 1));
51            maze[x + 1][y] = false;
52        }
53        if y < 51 && maze[x][y + 1] {
54            todo.push_back((x, y + 1, cost + 1));
55            maze[x][y + 1] = false;
56        }
57    }
58
59    (part_one, part_two)
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
