blob: 685a17872d18c5d47333ee224a51dd6e1ee922e7 (
plain)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
use std::collections::{HashMap, HashSet};
use regex::Regex;
use itertools::Itertools;
fn main() {
let input = advent::read_lines(9);
println!("9a: {}", shortest_route(&input));
println!("9b: {}", longest_route(&input));
}
fn parse_routes<T: AsRef<str>>(input: &[T]) -> HashMap<String, HashMap<String, u32>> {
let re = Regex::new(r"^([A-Za-z]+) to ([A-Za-z]+) = ([0-9]+)$").unwrap();
let mut routes = HashMap::new();
for line in input {
let cap = re.captures(line.as_ref()).unwrap();
let from = cap[1].to_string();
let to = cap[2].to_string();
let distance = cap[3].parse::<u32>().unwrap();
let entry = routes.entry(from.clone()).or_insert_with(HashMap::new);
entry.insert(to.clone(), distance);
let entry = routes.entry(to).or_insert_with(HashMap::new);
entry.insert(from, distance);
}
routes
}
fn distances<T: AsRef<str>>(input: &[T]) -> HashSet<u32> {
let routes = parse_routes(input);
let mut distances = HashSet::new();
for route in routes.keys().permutations(routes.keys().len()) {
let mut distance = 0;
let mut prev_city = (*route.first().unwrap()).clone();
for city in route.iter().skip(1).cloned().cloned() {
let reachable_from_prev = routes.get(&prev_city).unwrap();
distance += reachable_from_prev.get(&city).unwrap();
prev_city = city;
}
distances.insert(distance);
}
distances
}
fn shortest_route<T: AsRef<str>>(input: &[T]) -> u32 {
*distances(input).iter().min().unwrap()
}
fn longest_route<T: AsRef<str>>(input: &[T]) -> u32 {
*distances(input).iter().max().unwrap()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let input = [
"London to Dublin = 464",
"London to Belfast = 518",
"Dublin to Belfast = 141",
];
assert_eq!(shortest_route(&input), 605);
assert_eq!(longest_route(&input), 982);
}
}
|
