year2016/
day13.rs

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

year2016/
day13.rs
