1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#![feature(iter_next_chunk)]
use std::collections::HashMap;
static INPUT: &str = include_str!("input.txt");
fn main() {
let valueified = INPUT.split('\n').filter(|s| !s.is_empty())
.flat_map(|s| {
let [rhs, dist] = s.split(" = ").next_chunk::<2>().unwrap();
let [from, to] = rhs.split(" to ").next_chunk::<2>().unwrap();
let dist = dist.parse::<usize>().unwrap();
[(from, to, dist), (to, from, dist)]
});
let paths: HashMap<&'static str, Vec<(&'static str, usize)>> = valueified
.map(|(a,b,c)| (a, (b, c)))
.fold(HashMap::new(), |mut map, (k, v)| {map.entry(k).or_default().push(v); map});
let mut path = Vec::new();
let mut bestpath = Vec::new();
let mut bestdist = usize::MAX;
let mut worstpath = Vec::new();
let mut worstdist = 0;
for start in paths.keys() {
path.clear();
path.push(*start);
walk_steps(&mut path, 0, &mut bestpath, &mut bestdist, &mut worstpath, &mut worstdist, &paths);
}
println!("Best route: {} with dist = {bestdist}", bestpath.join(" => "));
println!("Worst route: {} with dist = {worstdist}", worstpath.join(" => "));
}
fn walk_steps(path: &mut Vec<&'static str>, dist: usize, bestpath: &mut Vec<&'static str>, bestdist: &mut usize, worstpath: &mut Vec<&'static str>, worstdist: &mut usize, steps: &HashMap<&'static str, Vec<(&'static str, usize)>>) {
if path.len() != steps.len() {
let prev = path.last().unwrap();
for (step, stepdist) in &steps[prev] {
if path.contains(step) { continue; }
path.push(step);
walk_steps(path, dist + stepdist, bestpath, bestdist, worstpath, worstdist, steps);
path.pop();
}
}
else if dist < *bestdist {
*bestpath = path.clone();
*bestdist = dist;
} else if dist > *worstdist {
*worstpath = path.clone();
*worstdist = dist;
}
}
|
