year2015/
day09.rs

1use std::collections::HashMap;
2use utils::graph::explore_hamiltonian_paths;
3use utils::prelude::*;
4
5/// Finding the shortest and longest path.
6///
7/// Traverse each route from the first location, adding on the edge from the last location back to
8/// the first location to find the shortest/longest loop. The shortest/longest route starting and
9/// ending at different locations is then the shortest/longest loop minus the longest/shortest edge.
10#[derive(Clone, Debug)]
11pub struct Day09 {
12    part1: u32,
13    part2: u32,
14}
15
16type Visited = u32;
17
18impl Day09 {
19    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
20        let location = parser::take_while1(u8::is_ascii_alphabetic).error_msg("expected location");
21        let parsed = location
22            .then(location.with_prefix(" to ").with_suffix(" = "))
23            .then(parser::u32())
24            .parse_lines(input)?;
25
26        let mut indexes = HashMap::new();
27        parsed.iter().for_each(|&(start, end, _)| {
28            let len = indexes.len();
29            indexes.entry(start).or_insert(len);
30            let len = indexes.len();
31            indexes.entry(end).or_insert(len);
32        });
33
34        let locations = indexes.len();
35        if locations > Visited::BITS as usize {
36            return Err(InputError::new(input, 0, "too many locations"));
37        }
38
39        let mut matrix = vec![0; indexes.len() * indexes.len()];
40        parsed.iter().for_each(|&(start, end, dist)| {
41            let start = indexes[start];
42            let end = indexes[end];
43            matrix[indexes.len() * start + end] = dist;
44            matrix[indexes.len() * end + start] = dist;
45        });
46
47        let (mut part1, mut part2) = (u32::MAX, 0);
48        explore_hamiltonian_paths(
49            indexes.len() as u32,
50            0,
51            (0, u32::MAX, 0),
52            |a, b| matrix[a as usize * locations + b as usize],
53            |(total, min_edge, max_edge), edge| {
54                (total + edge, min_edge.min(edge), max_edge.max(edge))
55            },
56            |(total, min_edge, max_edge), loop_edge| {
57                part1 = part1.min(total + loop_edge - max_edge.max(loop_edge));
58                part2 = part2.max(total + loop_edge - min_edge.min(loop_edge))
59            },
60        );
61
62        Ok(Self { part1, part2 })
63    }
64
65    #[must_use]
66    pub fn part1(&self) -> u32 {
67        self.part1
68    }
69
70    #[must_use]
71    pub fn part2(&self) -> u32 {
72        self.part2
73    }
74}
75
76examples!(Day09 -> (u32, u32) [
77    {
78        input: "London to Dublin = 464\n\
79            London to Belfast = 518\n\
80            Dublin to Belfast = 141",
81        part1: 605,
82        part2: 982,
83    },
84]);
year2015/day09.rs

year2015/
day09.rs
