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
10// Explicit syntax is cleaner for this case.
11#![allow(clippy::needless_range_loop)]
12
13use crate::util::parse::*;
14use std::collections::VecDeque;
15
16type Input = (u32, u32);
17
18pub fn parse(input: &str) -> Input {
19    let favorite: usize = input.unsigned();
20    let mut maze = [[false; 52]; 52];
21
22    for x in 0..52 {
23        for y in 0..52 {
24            let n = (x * x) + (3 * x) + (2 * x * y) + y + (y * y) + favorite;
25            maze[x][y] = n.count_ones().is_multiple_of(2);
26        }
27    }
28
29    let mut part_one = 0;
30    let mut part_two = 0;
31    let mut todo = VecDeque::new();
32
33    todo.push_back((1, 1, 0));
34    maze[1][1] = false;
35
36    while let Some((x, y, cost)) = todo.pop_front() {
37        if x == 31 && y == 39 {
38            part_one = cost;
39        }
40        if cost <= 50 {
41            part_two += 1;
42        }
43
44        if x > 0 && maze[x - 1][y] {
45            todo.push_back((x - 1, y, cost + 1));
46            maze[x - 1][y] = false;
47        }
48        if y > 0 && maze[x][y - 1] {
49            todo.push_back((x, y - 1, cost + 1));
50            maze[x][y - 1] = false;
51        }
52        if x < 51 && maze[x + 1][y] {
53            todo.push_back((x + 1, y, cost + 1));
54            maze[x + 1][y] = false;
55        }
56        if y < 51 && maze[x][y + 1] {
57            todo.push_back((x, y + 1, cost + 1));
58            maze[x][y + 1] = false;
59        }
60    }
61
62    (part_one, part_two)
63}
64
65pub fn part1(input: &Input) -> u32 {
66    input.0
67}
68
69pub fn part2(input: &Input) -> u32 {
70    input.1
71}
aoc/year2016/day13.rs

aoc/year2016/
day13.rs
