aoc/year2016/
day24.rs

1//! # Air Duct Spelunking
2//!
3//! This is a variant of the classic
4//! [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) and
5//! is similar to [`Year 2015 Day 13`].
6//!
7//! We first simplify the problem by finding the distance between all locations using multiple
8//! [BFS](https://en.wikipedia.org/wiki/Breadth-first_search)
9//! searches starting from each location.
10//!
11//! For speed we convert each location into an index, then store the distances between
12//! every pair of locations in a vec for fast lookup. Our utility [`half_permutations`] method uses
13//! [Steinhaus-Johnson-Trotter's algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm) for efficiency,
14//! modifying the slice in place.
15//!
16//! There are 8 locations, however since we always start at `0` this requires checking only
17//! 7!/2 = 2,520 permutations. We find the answer to both part one and two simultaneously.
18//!
19//! [`half_permutations`]: crate::util::slice
20//! [`Year 2015 Day 13`]: crate::year2015::day13
21use crate::util::grid::*;
22use crate::util::parse::*;
23use crate::util::slice::*;
24use std::collections::VecDeque;
25
26type Input = (u32, u32);
27
28pub fn parse(input: &str) -> Input {
29    let grid = Grid::parse(input);
30    let found: Vec<_> =
31        grid.bytes.iter().enumerate().filter(|(_, b)| b.is_ascii_digit()).map(|(i, _)| i).collect();
32
33    let width = grid.width as isize;
34    // There are 8 locations.
35    let mut distance = [[0; 8]; 8];
36
37    // BFS from each location. As minor optimizations we reuse `todo` and `seen`,
38    // and short-circuit each BFS once it will not learn anything new.
39    let mut todo = VecDeque::new();
40    let mut seen = vec![0; grid.bytes.len()];
41
42    for (rank, &start) in found.iter().skip(1).enumerate() {
43        let from = grid.bytes[start].to_decimal() as usize;
44        let mut need = found.len() - rank;
45
46        todo.clear();
47        todo.push_back((start, 0));
48        seen[start] = start;
49
50        while let Some((index, steps)) = todo.pop_front() {
51            if grid.bytes[index].is_ascii_digit() {
52                let to = grid.bytes[index].to_decimal() as usize;
53                if distance[from][to] == 0 {
54                    distance[from][to] = steps;
55                    distance[to][from] = steps;
56                    need -= 1;
57                    // Short-circuit once we found all needed pairs
58                    if need == 0 {
59                        break;
60                    }
61                }
62            }
63
64            // All interesting points (digits and junctions) are at odd locations,
65            // so we step by 2 spaces in each direction.
66            for delta in [1, -1, width, -width] {
67                let first = index.wrapping_add_signed(delta);
68                if grid.bytes[first] != b'#' {
69                    let second = index.wrapping_add_signed(2 * delta);
70                    if seen[second] != start {
71                        seen[second] = start;
72                        todo.push_back((second, steps + 2));
73                    }
74                }
75            }
76        }
77    }
78
79    // Solve both parts simultaneously.
80    let mut part_one = u32::MAX;
81    let mut part_two = u32::MAX;
82    let mut indices: Vec<_> = (1..found.len()).collect();
83
84    indices.half_permutations(|slice| {
85        let first = distance[0][slice[0]];
86        let middle = slice.windows(2).map(|w| distance[w[0]][w[1]]).sum::<u32>();
87        let last = distance[slice[slice.len() - 1]][0];
88
89        part_one = part_one.min(first + middle).min(middle + last);
90        part_two = part_two.min(first + middle + last);
91    });
92
93    (part_one, part_two)
94}
95
96pub fn part1(input: &Input) -> u32 {
97    input.0
98}
99
100pub fn part2(input: &Input) -> u32 {
101    input.1
102}
aoc/year2016/day24.rs

aoc/year2016/
day24.rs
