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            let ones = n.count_ones();
26            maze[x][y] = ones % 2 == 0;
27        }
28    }
29
30    let mut part_one = 0;
31    let mut part_two = 0;
32    let mut todo = VecDeque::new();
33
34    todo.push_back((1, 1, 0));
35    maze[1][1] = false;
36
37    while let Some((x, y, cost)) = todo.pop_front() {
38        if x == 31 && y == 39 {
39            part_one = cost;
40        }
41        if cost <= 50 {
42            part_two += 1;
43        }
44
45        if x > 0 && maze[x - 1][y] {
46            todo.push_back((x - 1, y, cost + 1));
47            maze[x - 1][y] = false;
48        }
49        if y > 0 && maze[x][y - 1] {
50            todo.push_back((x, y - 1, cost + 1));
51            maze[x][y - 1] = false;
52        }
53        if x < 51 && maze[x + 1][y] {
54            todo.push_back((x + 1, y, cost + 1));
55            maze[x + 1][y] = false;
56        }
57        if y < 51 && maze[x][y + 1] {
58            todo.push_back((x, y + 1, cost + 1));
59            maze[x][y + 1] = false;
60        }
61    }
62
63    (part_one, part_two)
64}
65
66pub fn part1(input: &Input) -> u32 {
67    input.0
68}
69
70pub fn part2(input: &Input) -> u32 {
71    input.1
72}
aoc/year2016/day13.rs

aoc/year2016/
day13.rs
