main.rs (4242B)
1 use std::collections::{HashMap, VecDeque};
2
3 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
4 struct Coord(usize, usize);
5
6 fn main() {
7 let input = std::fs::read_to_string("input.txt")
8 .unwrap()
9 .trim()
10 .split('\n')
11 .map(|s| s.chars().collect())
12 .collect();
13 // 437
14 println!("Part 1: {}", part_1(&input).unwrap());
15 // 430
16 println!("Part 2: {}", part_2(&input).unwrap());
17 }
18
19 fn reachable(a: char, b: char) -> bool {
20 let a = match a {
21 'S' => 'a',
22 'E' => 'z',
23 c => c,
24 };
25 let b = match b {
26 'S' => 'a',
27 'E' => 'z',
28 c => c,
29 };
30 b as u8 <= a as u8 + 1
31 }
32
33 fn part_1(input: &Vec<Vec<char>>) -> Option<usize> {
34 let x_max = input.len() - 1;
35 let y_max = input[0].len() - 1;
36 let (start, end) = {
37 let mut start = None;
38 let mut end = None;
39 for x in 0..input.len() {
40 for y in 0..input[0].len() {
41 if input[x][y] == 'S' {
42 start = Some(Coord(x, y));
43 } else if input[x][y] == 'E' {
44 end = Some(Coord(x, y));
45 }
46 }
47 }
48 (start.unwrap(), end.unwrap())
49 };
50 let mut steps = HashMap::new();
51 let mut queue = VecDeque::new();
52 steps.insert(start, 0);
53 queue.push_back((start, 0));
54 'mainloop: while let Some((curr, step_count)) = queue.pop_front() {
55 let mut neighbors = Vec::new();
56 if curr.0 != x_max {
57 neighbors.push(Coord(curr.0 + 1, curr.1));
58 }
59 if curr.0 != 0 {
60 neighbors.push(Coord(curr.0 - 1, curr.1));
61 }
62 if curr.1 != y_max {
63 neighbors.push(Coord(curr.0, curr.1 + 1));
64 }
65 if curr.1 != 0 {
66 neighbors.push(Coord(curr.0, curr.1 - 1));
67 }
68 for next in neighbors {
69 let step_count_next = step_count + 1;
70 let next_elev = input[next.0][next.1];
71 if reachable(input[curr.0][curr.1], next_elev) {
72 let record = steps.get(&next);
73 if record.is_none() {
74 steps.insert(next.clone(), step_count_next);
75 if next_elev == 'E' {
76 break 'mainloop;
77 } else {
78 queue.push_back((next, step_count_next));
79 }
80 }
81 }
82 }
83 }
84 steps.get(&end).copied()
85 }
86
87 fn part_2(input: &Vec<Vec<char>>) -> Option<usize> {
88 let x_max = input.len() - 1;
89 let y_max = input[0].len() - 1;
90 let (_start, end) = {
91 let mut start = None;
92 let mut end = None;
93 for x in 0..input.len() {
94 for y in 0..input[0].len() {
95 if input[x][y] == 'S' {
96 start = Some(Coord(x, y));
97 } else if input[x][y] == 'E' {
98 end = Some(Coord(x, y));
99 }
100 }
101 }
102 (start.unwrap(), end.unwrap())
103 };
104 let mut steps = HashMap::new();
105 let mut queue = VecDeque::new();
106 steps.insert(end, 0);
107 queue.push_back((end, 0));
108 while let Some((curr, step_count)) = queue.pop_front() {
109 let mut neighbors = Vec::new();
110 if curr.0 != x_max {
111 neighbors.push(Coord(curr.0 + 1, curr.1));
112 }
113 if curr.0 != 0 {
114 neighbors.push(Coord(curr.0 - 1, curr.1));
115 }
116 if curr.1 != y_max {
117 neighbors.push(Coord(curr.0, curr.1 + 1));
118 }
119 if curr.1 != 0 {
120 neighbors.push(Coord(curr.0, curr.1 - 1));
121 }
122 for next in neighbors {
123 let step_count_next = step_count + 1;
124 let next_elev = input[next.0][next.1];
125 if reachable(next_elev, input[curr.0][curr.1]) {
126 let record = steps.get(&next);
127 if record.is_none() {
128 steps.insert(next.clone(), step_count_next);
129 if next_elev == 'S' || next_elev == 'a' {
130 return Some(step_count_next);
131 } else {
132 queue.push_back((next, step_count_next));
133 }
134 }
135 }
136 }
137 }
138 None
139 }