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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
use std::collections::VecDeque;
use std::fs;
use itertools::Itertools;
fn to_grid(lines: Vec<&str>) -> Vec<Vec<char>> {
let mut grid: Vec<Vec<char>> = Vec::new();
for line in lines {
let mut row = Vec::new();
for ch in line.chars() {
row.push(ch);
}
grid.push(row);
}
grid
}
fn find_goals(grid: &Vec<Vec<char>>) -> Vec<(usize, usize)> {
let mut result = Vec::new();
// The goal locations are represented by digits in the grid
for (y, row) in grid.iter().enumerate() {
for (x, ch) in row.iter().enumerate() {
if ch.is_ascii_digit() {
result.push((x, y));
}
}
}
result
}
fn goal_distances(grid: &Vec<Vec<char>>, goals: &Vec<(usize, usize)>) -> Vec<Vec<usize>> {
let mut dists = Vec::new();
for _i in 0..goals.len() {
dists.push([0].repeat(goals.len()));
}
// For each goal location, find the distance to each other goal
for (i, &g) in goals.iter().enumerate() {
let mut visited = vec![g];
let mut queue = VecDeque::from([(g, 0)]);
// Do a breadth-first search to find the shortest paths
while queue.len() > 0 {
let (loc, depth) = queue.pop_front().unwrap();
// Have we reached another goal? If so, which one?
let oj = goals.iter().position(|&xy| xy == loc);
if oj.is_some() {
let j = oj.unwrap();
dists[i][j] = depth;
}
// Which adjacent locations are accessible?
let mut adjs = Vec::new();
let u = (loc.0, loc.1 - 1); // up
let d = (loc.0, loc.1 + 1); // down
let l = (loc.0 - 1, loc.1); // left
let r = (loc.0 + 1, loc.1); // right
if grid[u.1][u.0] != '#' {
adjs.push(u);
}
if grid[d.1][d.0] != '#' {
adjs.push(d);
}
if grid[l.1][l.0] != '#' {
adjs.push(l);
}
if grid[r.1][r.0] != '#' {
adjs.push(r);
}
// Standard breadth-first search stuff
for adj in adjs {
if !visited.contains(&adj) {
visited.push(adj);
queue.push_back((adj, depth + 1));
}
}
}
}
dists
}
fn solve_puzzle(grid: &Vec<Vec<char>>, go_back: bool) -> usize {
let goals = find_goals(&grid);
let dists = goal_distances(&grid, &goals);
// This is the travelling salesman problem, so we must try all paths.
// We just brute-force the total distance for every order of the goals,
// and only keep the result if the path started at "0" as it should.
let mut shortest = 13371337;
for p in (0..goals.len()).permutations(goals.len()) {
let mut total = 0;
for i in 1..p.len() {
total += dists[p[i - 1]][p[i]];
}
// Part 2: go back to the start too
if go_back {
total += dists[p[p.len() - 1]][p[0]];
}
// Is this the shortest path we've seen that start at "0"?
let first = goals[p[0]];
if grid[first.1][first.0] == '0' && total < shortest {
shortest = total;
}
}
shortest
}
fn main() {
// Read layout from input text file
let input = fs::read_to_string("input.txt").unwrap();
let lines = input.lines().collect();
let grid = to_grid(lines);
// Part 1 gives 430 for me
println!("Part 1 solution: {}", solve_puzzle(&grid, false));
// Part 2 gives 700 for me
println!("Part 2 solution: {}", solve_puzzle(&grid, true));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn part1_example1() {
let lines = vec![
"###########",
"#0.1.....2#",
"#.#######.#",
"#4.......3#",
"###########",
];
let grid = to_grid(lines);
assert_eq!(solve_puzzle(&grid, false), 14);
}
}
|
