aoc/year2015/
day09.rs

1//! # All in a Single Night
2//!
3//! This is a variant of the classic NP-hard
4//! [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem).
5//!
6//! There are 8 locations, so naively it would require checking 8! = 40,320 permutations. We can
7//! reduce this to 7!/2 = 2,520 permutations by arbitrarily choosing one of the locations as the
8//! start, and skipping lexically reversed permutations (since the path a->b->c has the same
9//! length as c->b->a).
10//!
11//! We then compute the distance to complete the trip and return to the original location.
12//! Since the problem does not ask us to end up in the same location we then "break" the cycle.
13//! To compute the shortest journey we remove the longest single journey and to compute the
14//! longest journey we remove the shortest single journey.
15//!
16//! For speed we first convert each location into an index, then store the distances between
17//! every pair of locations in an array for fast lookup. Our utility [`half_permutations`] method uses
18//! [Steinhaus-Johnson-Trotter's algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) for efficiency,
19//! modifying the slice in place.
20//!
21//! [`half_permutations`]: crate::util::slice
22use crate::util::hash::*;
23use crate::util::iter::*;
24use crate::util::parse::*;
25use crate::util::slice::*;
26
27type Result = (u32, u32);
28
29pub fn parse(input: &str) -> Result {
30    let tokens: Vec<_> = input.split_ascii_whitespace().chunk::<5>().collect();
31    let mut indices = FastMap::new();
32
33    for [start, _, end, ..] in &tokens {
34        let size = indices.len();
35        indices.entry(start).or_insert(size);
36
37        let size = indices.len();
38        indices.entry(end).or_insert(size);
39    }
40
41    let stride = indices.len();
42    let mut distances = vec![0; stride * stride];
43
44    for [start, _, end, _, distance] in &tokens {
45        let start = indices[start];
46        let end = indices[end];
47        let distance = distance.unsigned();
48
49        distances[stride * start + end] = distance;
50        distances[stride * end + start] = distance;
51    }
52
53    let mut global_min = u32::MAX;
54    let mut global_max = u32::MIN;
55    let mut indices: Vec<_> = (1..stride).collect();
56
57    indices.half_permutations(|slice| {
58        let mut sum = 0;
59        let mut local_min = u32::MAX;
60        let mut local_max = u32::MIN;
61
62        let mut trip = |from, to| {
63            let distance = distances[stride * from + to];
64            sum += distance;
65            local_min = local_min.min(distance);
66            local_max = local_max.max(distance);
67        };
68
69        // First trip.
70        trip(0, slice[0]);
71        // Last trip.
72        trip(0, slice[slice.len() - 1]);
73        // Intermediate trips.
74        for i in 1..slice.len() {
75            trip(slice[i], slice[i - 1]);
76        }
77
78        global_min = global_min.min(sum - local_max);
79        global_max = global_max.max(sum - local_min);
80    });
81
82    (global_min, global_max)
83}
84
85pub fn part1(input: &Result) -> u32 {
86    input.0
87}
88
89pub fn part2(input: &Result) -> u32 {
90    input.1
91}
aoc/year2015/day09.rs

aoc/year2015/
day09.rs
