-
Notifications
You must be signed in to change notification settings - Fork 4
/
day09.rs
88 lines (72 loc) · 2.78 KB
/
day09.rs
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//! # All in a Single Night
//!
//! This is a variant of the classic NP-hard
//! [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem).
//!
//! There are 8 locations, so naively it would require checking 8! = 40,320 permutations. We can
//! reduce this to 7! = 5,040 permutations by arbitrarily choosing one of the locations as the
//! start.
//!
//! We then compute the distance to complete the trip and return to the original location.
//! Since the problem does not ask us to end up in the same location we then "break" the cycle.
//! To compute the shortest journey we remove the longest single journey and to compute the
//! longest journey we remove the shortest single journey.
//!
//! For speed we first convert each location into an index, then store the distances between
//! every pair of locations in an array for fast lookup. Our utility [`permutations`] method uses
//! [Heap's algorithm](https://en.wikipedia.org/wiki/Heap%27s_algorithm) for efficiency,
//! modifying the slice in place.
//!
//! [`permutations`]: crate::util::slice
use crate::util::hash::*;
use crate::util::iter::*;
use crate::util::parse::*;
use crate::util::slice::*;
type Result = (u32, u32);
pub fn parse(input: &str) -> Result {
let tokens: Vec<_> = input.split_ascii_whitespace().chunk::<5>().collect();
let mut indices = FastMap::new();
for [start, _, end, ..] in &tokens {
let size = indices.len();
indices.entry(start).or_insert(size);
let size = indices.len();
indices.entry(end).or_insert(size);
}
let stride = indices.len();
let mut distances = vec![0; stride * stride];
for [start, _, end, _, distance] in &tokens {
let start = indices[start];
let end = indices[end];
let distance = distance.unsigned();
distances[stride * start + end] = distance;
distances[stride * end + start] = distance;
}
let mut global_min = u32::MAX;
let mut global_max = u32::MIN;
let mut indices: Vec<_> = (1..stride).collect();
indices.permutations(|slice| {
let mut sum = 0;
let mut local_min = u32::MAX;
let mut local_max = u32::MIN;
let mut trip = |from, to| {
let distance = distances[stride * from + to];
sum += distance;
local_min = local_min.min(distance);
local_max = local_max.max(distance);
};
trip(0, slice[0]);
trip(0, slice[slice.len() - 1]);
for i in 1..slice.len() {
trip(slice[i], slice[i - 1]);
}
global_min = global_min.min(sum - local_max);
global_max = global_max.max(sum - local_min);
});
(global_min, global_max)
}
pub fn part1(input: &Result) -> u32 {
input.0
}
pub fn part2(input: &Result) -> u32 {
input.1
}