year2016/
day24.rs

1use std::collections::VecDeque;
2use utils::graph::explore_hamiltonian_paths;
3use utils::grid;
4use utils::prelude::*;
5
6/// Finding the shortest path and cycle.
7///
8/// Very similar to [2015 Day 9](../year2015/struct.Day09.html) and
9/// [2015 Day 13](../year2015/struct.Day13.html).
10#[derive(Clone, Debug)]
11pub struct Day24 {
12    part1: u32,
13    part2: u32,
14}
15
16impl Day24 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let mut digit_positions = [None; 10];
19
20        // The actual input has a solid border of walls, but pad the input with an extra layer of
21        // wall anyway to ensure index manipulation doesn't need checks for any input
22        let (_, cols, grid) = grid::parse(
23            input,
24            1,
25            b'#',
26            |b| b,
27            |b| matches!(b, b'.' | b'#'),
28            |i, b| match b {
29                b'0'..=b'9' => {
30                    let d = (b - b'0') as usize;
31                    if digit_positions[d].is_some() {
32                        return Err(format!("duplicate {d} digit"));
33                    }
34                    digit_positions[d] = Some(i);
35                    Ok(b)
36                }
37                _ => Err("expected '.', '#' or digit".to_string()),
38            },
39        )?;
40
41        let digits = digit_positions
42            .iter()
43            .position(Option::is_none)
44            .unwrap_or(10);
45        if digits == 0 {
46            return Err(InputError::new(input, 0, "expected 0 in grid"));
47        }
48        if digit_positions[digits..].iter().any(Option::is_some) {
49            return Err(InputError::new(input, 0, format!("missing {digits} digit")));
50        }
51
52        let digit_positions = digit_positions.map(Option::unwrap_or_default);
53        let digit_positions = &digit_positions[..digits];
54
55        // Find the distance from each point of interest to every other one
56        let mut dist_matrix = vec![u32::MAX; digits * digits];
57        'digits: for (start_digit, &start_index) in digit_positions.iter().enumerate() {
58            let mut visited = vec![false; grid.len()];
59            visited[start_index] = true;
60
61            let mut queue = VecDeque::new();
62            queue.push_back((start_index, 0));
63
64            while let Some((index, dist)) = queue.pop_front() {
65                if grid[index].is_ascii_digit() {
66                    let end_digit = (grid[index] - b'0') as usize;
67                    dist_matrix[(start_digit * digits) + end_digit] = dist;
68                    dist_matrix[(end_digit * digits) + start_digit] = dist;
69
70                    // Stop BFS early if this row of the matrix is now complete
71                    if dist_matrix[start_digit * digits..(start_digit + 1) * digits]
72                        .iter()
73                        .all(|&c| c != u32::MAX)
74                    {
75                        continue 'digits;
76                    }
77                }
78
79                for next in [index - 1, index + 1, index - cols, index + cols] {
80                    if grid[next] != b'#' && !visited[next] {
81                        queue.push_back((next, dist + 1));
82                        visited[next] = true;
83                    }
84                }
85            }
86
87            return Err(InputError::new(input, 0, "unreachable digit"));
88        }
89
90        // Find the shortest path and the shortest cycle
91        let (mut part1, mut part2) = (u32::MAX, u32::MAX);
92        explore_hamiltonian_paths(
93            digits as u32,
94            0,
95            0,
96            |a, b| dist_matrix[(a as usize * digits) + b as usize],
97            |a, b| a + b,
98            |total, loop_edge| {
99                part1 = part1.min(total);
100                part2 = part2.min(total + loop_edge);
101            },
102        );
103
104        Ok(Self { part1, part2 })
105    }
106
107    #[must_use]
108    pub fn part1(&self) -> u32 {
109        self.part1
110    }
111
112    #[must_use]
113    pub fn part2(&self) -> u32 {
114        self.part2
115    }
116}
117
118examples!(Day24 -> (u32, u32) [
119    {file: "day24_example0.txt", part1: 14, part2: 20},
120]);
year2016/day24.rs

year2016/
day24.rs
