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_counts = [0usize; 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::from_str_padded(input, 1, b'#', |b| match b {
23            b'.' | b'#' => Some(b),
24            b'0'..=b'9' => {
25                digit_counts[(b - b'0') as usize] += 1;
26                Some(b)
27            }
28            _ => None,
29        })?;
30
31        let digits = digit_counts.iter().position(|&c| c == 0).unwrap_or(10);
32        if let Some(d) = digit_counts.iter().position(|&c| c > 1) {
33            return Err(InputError::new(input, 0, format!("duplicate {d} digit")));
34        }
35        if digits == 0 {
36            return Err(InputError::new(input, 0, "expected 0 in grid"));
37        }
38        if digit_counts[digits..].iter().any(|&c| c > 0) {
39            return Err(InputError::new(input, 0, format!("missing {digits} digit")));
40        }
41
42        let mut digit_positions = vec![0; digits];
43        for (i, &c) in grid.iter().enumerate() {
44            if c.is_ascii_digit() {
45                digit_positions[(c - b'0') as usize] = i;
46            }
47        }
48
49        // Find the distance from each point of interest to every other one
50        let mut dist_matrix = vec![u32::MAX; digits * digits];
51        'digits: for (start_digit, &start_index) in digit_positions.iter().enumerate() {
52            let mut visited = vec![false; grid.len()];
53            visited[start_index] = true;
54
55            let mut queue = VecDeque::new();
56            queue.push_back((start_index, 0));
57
58            while let Some((index, dist)) = queue.pop_front() {
59                if grid[index].is_ascii_digit() {
60                    let end_digit = (grid[index] - b'0') as usize;
61                    dist_matrix[(start_digit * digits) + end_digit] = dist;
62                    dist_matrix[(end_digit * digits) + start_digit] = dist;
63
64                    // Stop BFS early if this row of the matrix is now complete
65                    if dist_matrix[start_digit * digits..(start_digit + 1) * digits]
66                        .iter()
67                        .all(|&c| c != u32::MAX)
68                    {
69                        continue 'digits;
70                    }
71                }
72
73                for next in [index - 1, index + 1, index - cols, index + cols] {
74                    if grid[next] != b'#' && !visited[next] {
75                        queue.push_back((next, dist + 1));
76                        visited[next] = true;
77                    }
78                }
79            }
80
81            return Err(InputError::new(input, 0, "unreachable digit"));
82        }
83
84        // Find the shortest path and the shortest cycle
85        let (mut part1, mut part2) = (u32::MAX, u32::MAX);
86        explore_hamiltonian_paths(
87            digits as u32,
88            0,
89            0,
90            |a, b| dist_matrix[(a as usize * digits) + b as usize],
91            |a, b| a + b,
92            |total, loop_edge| {
93                part1 = part1.min(total);
94                part2 = part2.min(total + loop_edge);
95            },
96        );
97
98        Ok(Self { part1, part2 })
99    }
100
101    #[must_use]
102    pub fn part1(&self) -> u32 {
103        self.part1
104    }
105
106    #[must_use]
107    pub fn part2(&self) -> u32 {
108        self.part2
109    }
110}
111
112examples!(Day24 -> (u32, u32) [
113    {file: "day24_example0.txt", part1: 14, part2: 20},
114]);
year2016/day24.rs

year2016/
day24.rs
