advent_of_code/year2016/
day24.rs

1use crate::common::permutation::all_permutations;
2use crate::input::Input;
3use std::cmp::Reverse;
4use std::collections::{BinaryHeap, HashMap, HashSet};
5
6struct Grid {
7    cols: usize,
8    data: Vec<bool>,
9    locations: Vec<(usize, usize)>,
10}
11
12impl Grid {
13    fn parse(input: &str) -> Result<Self, String> {
14        let rows = input.lines().count();
15        let cols = input.lines().next().ok_or("Empty input")?.len();
16        let mut locations = Vec::new();
17        let mut data = vec![true; rows * cols];
18
19        for (y, line) in input.lines().enumerate() {
20            if line.len() != cols {
21                return Err("Not all rows have equal length".into());
22            }
23            for (x, &c) in line.as_bytes().iter().enumerate() {
24                data[y * cols + x] = match c {
25                    b'#' => false,
26                    b'.' => true,
27                    b'0'..=b'7' => {
28                        if x == 0 || y == 0 || x + 1 == cols || y + 1 == rows {
29                            return Err("Number at edge".into());
30                        }
31                        let number = (c - b'0') as usize;
32                        if number >= locations.len() {
33                            locations.resize(number + 1, (0, 0));
34                        }
35                        locations[number] = (x, y);
36                        true
37                    }
38                    _ => {
39                        return Err(format!("Invalid char in input: '{}'", c as char));
40                    }
41                };
42            }
43        }
44
45        Ok(Self {
46            cols,
47            data,
48            locations,
49        })
50    }
51
52    fn is_open(&self, location: (usize, usize)) -> bool {
53        self.data[location.1 * self.cols + location.0]
54    }
55}
56
57pub fn solve(input: &Input) -> Result<usize, String> {
58    let grid = Grid::parse(input.text)?;
59    let mut distances: HashMap<(usize, usize), usize> = HashMap::new();
60
61    for from in 0..grid.locations.len() {
62        'toloop: for to in 0..grid.locations.len() {
63            if to <= from {
64                continue;
65            }
66
67            let starting_location = grid.locations[from];
68            let target_location = grid.locations[to];
69            if starting_location == (0, 0) || target_location == (0, 0) {
70                return Err("Not all digits in grid".into());
71            }
72
73            let mut visited = HashSet::new();
74            let mut to_visit = BinaryHeap::new();
75            to_visit.push(Reverse((0, 0, starting_location)));
76
77            while let Some(Reverse((_heuristic, distance, location))) = to_visit.pop() {
78                if location == target_location {
79                    distances.insert((from, to), distance);
80                    continue 'toloop;
81                }
82
83                for diff in [(1_i32, 0_i32), (-1, 0), (0, 1), (0, -1)] {
84                    if diff.0 == -1 && location.0 == 0 || diff.1 == -1 && location.1 == 0 {
85                        continue;
86                    }
87                    let new_location = (
88                        (location.0 as i32 + diff.0) as usize,
89                        (location.1 as i32 + diff.1) as usize,
90                    );
91                    if grid.is_open(new_location) && visited.insert(new_location) {
92                        let new_distance = distance + 1;
93                        let heuristic = (new_location.0 as i32 - target_location.0 as i32)
94                            .unsigned_abs() as usize
95                            + (new_location.1 as i32 - target_location.1 as i32).unsigned_abs()
96                                as usize;
97                        to_visit.push(Reverse((
98                            new_distance + heuristic,
99                            new_distance,
100                            new_location,
101                        )));
102                    }
103                }
104            }
105        }
106    }
107
108    let mut initial_order = (1..grid.locations.len()).collect::<Vec<usize>>();
109    let mut answer = usize::MAX;
110    all_permutations(
111        &mut initial_order,
112        &mut |order: &[usize]| -> Result<(), String> {
113            let mut current_location = 0_usize;
114            let mut total_distance = 0;
115            for &n in order.iter() {
116                let key = (
117                    std::cmp::min(current_location, n),
118                    std::cmp::max(current_location, n),
119                );
120                total_distance += distances.get(&key).unwrap_or(&0);
121                current_location = n;
122            }
123            if input.is_part_two() {
124                total_distance += distances.get(&(0, current_location)).unwrap_or(&0);
125            }
126            answer = std::cmp::min(answer, total_distance);
127            Ok(())
128        },
129    )?;
130
131    Ok(answer)
132}
133
134#[test]
135pub fn tests() {
136    use crate::input::{test_part_one, test_part_two};
137
138    test_part_one!("###########\n#0.1.....2#\n#.#######.#\n#4.......3#\n###########" => 14);
139
140    let real_input = include_str!("day24_input.txt");
141    test_part_one!(real_input => 412);
142    test_part_two!(real_input => 664);
143}
advent_of_code/year2016/day24.rs

advent_of_code/year2016/
day24.rs
