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 an vec for fast lookup. Our utility [`permutations`] method uses
13//! [Heap's algorithm](https://en.wikipedia.org/wiki/Heap%27s_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! = 5,040 permutations. We find the answer to both part one and two simultaneously.
18//!
19//! [`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 usize;
34    let stride = found.len();
35    let mut distance = vec![0; stride * stride];
36
37    // BFS from each location. As a minor optimization we reuse `todo` and `visited`.
38    let mut todo = VecDeque::new();
39    let mut visited = vec![0; grid.bytes.len()];
40
41    for start in found {
42        let from = grid.bytes[start].to_decimal() as usize;
43
44        todo.push_back((start, 0));
45        visited[start] = start;
46
47        while let Some((index, steps)) = todo.pop_front() {
48            if grid.bytes[index].is_ascii_digit() {
49                let to = grid.bytes[index].to_decimal() as usize;
50                distance[stride * from + to] = steps;
51            }
52
53            for next in [index + 1, index - 1, index + width, index - width] {
54                if grid.bytes[next] != b'#' && visited[next] != start {
55                    visited[next] = start;
56                    todo.push_back((next, steps + 1));
57                }
58            }
59        }
60    }
61
62    // Solve both parts simultaneously.
63    let mut part_one = u32::MAX;
64    let mut part_two = u32::MAX;
65    let mut indices: Vec<_> = (1..stride).collect();
66
67    indices.permutations(|slice| {
68        let link = |from, to| distance[stride * from + to];
69
70        let first = link(0, slice[0]);
71        let middle = slice.windows(2).map(|w| link(w[0], w[1])).sum::<u32>();
72        let last = link(slice[slice.len() - 1], 0);
73
74        part_one = part_one.min(first + middle);
75        part_two = part_two.min(first + middle + last);
76    });
77
78    (part_one, part_two)
79}
80
81pub fn part1(input: &Input) -> u32 {
82    input.0
83}
84
85pub fn part2(input: &Input) -> u32 {
86    input.1
87}
aoc/year2016/day24.rs

aoc/year2016/
day24.rs
