year2016/
day13.rs

1use std::collections::VecDeque;
2use utils::geometry::Vec2;
3use utils::hash::FastSet;
4use utils::prelude::*;
5
6/// Finding the shortest path.
7#[derive(Clone, Debug)]
8pub struct Day13 {
9    part1: u32,
10    part2: u32,
11}
12
13impl Day13 {
14    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
15        let favorite_number = parser::u32().parse_complete(input)?;
16        let target: Vec2<u32> = if input_type == InputType::Real {
17            Vec2::new(31, 39)
18        } else {
19            Vec2::new(7, 4)
20        };
21
22        // Use a hashset to store visited nodes to avoid having a fixed grid size, as theoretically
23        // the shortest route to the target may first go a long way down/right.
24        let mut visited = FastSet::with_capacity(512);
25        visited.insert(Vec2::new(1, 1));
26        let mut queue = VecDeque::new();
27        queue.push_back((Vec2::new(1, 1), 0));
28
29        let (mut part1, mut part2) = (0, 0);
30        while let Some((p, steps)) = queue.pop_front() {
31            if p == target {
32                part1 = steps;
33            }
34
35            if steps <= 50 {
36                part2 += 1;
37            } else if part1 != 0 {
38                break;
39            }
40
41            for next @ Vec2 { x, y } in [
42                Vec2::new(p.x.saturating_sub(1), p.y),
43                Vec2::new(p.x.saturating_add(1), p.y),
44                Vec2::new(p.x, p.y.saturating_sub(1)),
45                Vec2::new(p.x, p.y.saturating_add(1)),
46            ] {
47                let n = (x * x) + (3 * x) + (2 * x * y) + y + (y * y) + favorite_number;
48                if n.count_ones().is_multiple_of(2) && !visited.contains(&next) {
49                    visited.insert(next);
50                    queue.push_back((next, steps + 1));
51                }
52            }
53        }
54
55        Ok(Self { part1, part2 })
56    }
57
58    #[must_use]
59    pub fn part1(&self) -> u32 {
60        self.part1
61    }
62
63    #[must_use]
64    pub fn part2(&self) -> u32 {
65        self.part2
66    }
67}
68
69examples!(Day13 -> (u32, u32) [
70    {input: "10", part1: 11},
71]);
year2016/day13.rs

year2016/
day13.rs
