Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit bd50d62

Browse filesBrowse files
LuisFadiniLuisFadini
committed
Added day 16 Rust based solution
1 parent 6dfe923 commit bd50d62
Copy full SHA for bd50d62

File tree

5 files changed

+389
-1
lines changed
Filter options

5 files changed

+389
-1
lines changed

‎2024/day16/Cargo.toml

Copy file name to clipboard
+11Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
[package]
2+
name = "day16"
3+
version = "0.1.0"
4+
edition = "2021"
5+
6+
[dependencies]
7+
utils = { workspace = true }
8+
9+
[[bin]]
10+
name = "day16"
11+
path = "day16.rs"

‎2024/day16/day16.rs

Copy file name to clipboard
+315Lines changed: 315 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,315 @@
1+
use std::{
2+
cmp::Reverse,
3+
collections::{BinaryHeap, HashMap, HashSet},
4+
};
5+
6+
use utils::coordinates::{self, Point};
7+
8+
#[derive(PartialEq, Clone)]
9+
enum Tiles {
10+
Start,
11+
Empty,
12+
End,
13+
Wall,
14+
}
15+
16+
#[derive(Eq, Ord, PartialEq, PartialOrd)]
17+
enum Direction {
18+
UP,
19+
DOWN,
20+
LEFT,
21+
RIGHT,
22+
}
23+
24+
#[derive(Eq, Ord, PartialEq, PartialOrd)]
25+
struct Location {
26+
point: Point<i32>,
27+
cost: i32,
28+
direction: Direction,
29+
current_path: Vec<Point<i32>>,
30+
}
31+
32+
impl Location {
33+
fn new(
34+
point: Point<i32>,
35+
current_cost: i32,
36+
direction: Direction,
37+
current_path: Vec<Point<i32>>,
38+
) -> Location {
39+
Location {
40+
point,
41+
cost: current_cost,
42+
direction,
43+
current_path,
44+
}
45+
}
46+
}
47+
48+
fn get_next_locations(location: &Location) -> Vec<Location> {
49+
let mut up_path = location.current_path.clone();
50+
let mut down_path = location.current_path.clone();
51+
let mut right_path = location.current_path.clone();
52+
let mut left_path = location.current_path.clone();
53+
54+
up_path.push(location.point + coordinates::Direction::UP);
55+
down_path.push(location.point + coordinates::Direction::DOWN);
56+
left_path.push(location.point + coordinates::Direction::LEFT);
57+
right_path.push(location.point + coordinates::Direction::RIGHT);
58+
59+
match location.direction {
60+
Direction::UP => vec![
61+
Location::new(
62+
location.point + coordinates::Direction::UP,
63+
location.cost + 1,
64+
Direction::UP,
65+
up_path,
66+
),
67+
Location::new(
68+
location.point + coordinates::Direction::LEFT,
69+
location.cost + 1001,
70+
Direction::LEFT,
71+
left_path,
72+
),
73+
Location::new(
74+
location.point + coordinates::Direction::RIGHT,
75+
location.cost + 1001,
76+
Direction::RIGHT,
77+
right_path,
78+
),
79+
],
80+
Direction::DOWN => vec![
81+
Location::new(
82+
location.point + coordinates::Direction::DOWN,
83+
location.cost + 1,
84+
Direction::DOWN,
85+
down_path,
86+
),
87+
Location::new(
88+
location.point + coordinates::Direction::LEFT,
89+
location.cost + 1001,
90+
Direction::LEFT,
91+
left_path,
92+
),
93+
Location::new(
94+
location.point + coordinates::Direction::RIGHT,
95+
location.cost + 1001,
96+
Direction::RIGHT,
97+
right_path,
98+
),
99+
],
100+
Direction::LEFT => vec![
101+
Location::new(
102+
location.point + coordinates::Direction::UP,
103+
location.cost + 1001,
104+
Direction::UP,
105+
up_path,
106+
),
107+
Location::new(
108+
location.point + coordinates::Direction::DOWN,
109+
location.cost + 1001,
110+
Direction::DOWN,
111+
down_path,
112+
),
113+
Location::new(
114+
location.point + coordinates::Direction::LEFT,
115+
location.cost + 1,
116+
Direction::LEFT,
117+
left_path,
118+
),
119+
],
120+
Direction::RIGHT => vec![
121+
Location::new(
122+
location.point + coordinates::Direction::UP,
123+
location.cost + 1001,
124+
Direction::UP,
125+
up_path,
126+
),
127+
Location::new(
128+
location.point + coordinates::Direction::DOWN,
129+
location.cost + 1001,
130+
Direction::DOWN,
131+
down_path,
132+
),
133+
Location::new(
134+
location.point + coordinates::Direction::RIGHT,
135+
location.cost + 1,
136+
Direction::RIGHT,
137+
right_path,
138+
),
139+
],
140+
}
141+
}
142+
143+
fn get_distance_from_end(current_point: Point<i32>, end_point: Point<i32>) -> i32 {
144+
(end_point.x - current_point.x).abs() + (end_point.y - current_point.y).abs()
145+
}
146+
147+
fn a_star(
148+
map_grid: HashMap<Point<i32>, Tiles>,
149+
start_pos: Point<i32>,
150+
end_pos: Point<i32>,
151+
start_direction: Direction,
152+
) -> i32 {
153+
let start_location = Location::new(start_pos, 0, start_direction, vec![start_pos]);
154+
let mut to_visit: Vec<Location> = vec![start_location];
155+
156+
let max_point = *map_grid
157+
.iter()
158+
.max_by_key(|(point, _)| (point.x, point.y))
159+
.unwrap()
160+
.0;
161+
162+
let mut visited: HashSet<Point<i32>> = HashSet::new();
163+
164+
while !to_visit.is_empty() {
165+
let location = to_visit.remove(0);
166+
if *map_grid.get(&location.point).unwrap() == Tiles::End {
167+
return location.cost;
168+
}
169+
170+
visited.insert(location.point);
171+
let next_locations = get_next_locations(&location);
172+
173+
for l in next_locations {
174+
if l.point <= max_point
175+
&& *map_grid.get(&l.point).unwrap() != Tiles::Wall
176+
&& !visited.contains(&l.point)
177+
{
178+
to_visit.push(l);
179+
}
180+
}
181+
182+
to_visit.sort_by(|x, y| {
183+
let hx = get_distance_from_end(x.point, end_pos);
184+
let hy = get_distance_from_end(y.point, end_pos);
185+
186+
let diff = (x.cost + hx) - (y.cost + hy);
187+
if diff == 0 {
188+
return std::cmp::Ordering::Equal;
189+
}
190+
if diff < 0 {
191+
return std::cmp::Ordering::Less;
192+
}
193+
return std::cmp::Ordering::Greater;
194+
});
195+
}
196+
197+
0
198+
}
199+
200+
fn create_grid(map: Vec<&str>) -> (HashMap<Point<i32>, Tiles>, Point<i32>, Point<i32>) {
201+
let mut map_grid = HashMap::with_capacity(map.len() * map[0].len());
202+
let mut current_pos = Point { x: 0, y: 0 };
203+
let mut end_pos = Point { x: 0, y: 0 };
204+
205+
for (y, line) in map.iter().enumerate() {
206+
for (x, tile) in line.chars().enumerate() {
207+
let point = Point { x: x as i32, y: y as i32 };
208+
209+
let tile_type = match tile {
210+
'S' => {
211+
current_pos = point;
212+
Tiles::Start
213+
}
214+
'.' => Tiles::Empty,
215+
'E' => {
216+
end_pos = point;
217+
Tiles::End
218+
}
219+
'#' => Tiles::Wall,
220+
_ => unreachable!(),
221+
};
222+
223+
map_grid.insert(point, tile_type);
224+
}
225+
}
226+
227+
(map_grid, current_pos, end_pos)
228+
}
229+
230+
fn part1(input_map: String) -> i32 {
231+
let map = input_map.lines().collect::<Vec<_>>();
232+
let (map_grid, current_pos, end_pos) = create_grid(map);
233+
234+
a_star(map_grid, current_pos, end_pos, Direction::RIGHT)
235+
}
236+
237+
fn find_all_paths(
238+
map_grid: HashMap<Point<i32>, Tiles>,
239+
start_pos: Point<i32>,
240+
end_pos: Point<i32>,
241+
start_direction: Direction,
242+
total_cost: i32,
243+
) -> i32 {
244+
let start_location = Location::new(start_pos, 0, start_direction, vec![start_pos]);
245+
let mut to_visit = BinaryHeap::new();
246+
to_visit.push(Reverse((0, start_location)));
247+
248+
let max_point = map_grid
249+
.keys()
250+
.max_by_key(|point| (point.x, point.y))
251+
.cloned()
252+
.unwrap();
253+
254+
let mut grid = vec![vec![i32::MAX; max_point.x as usize + 1]; max_point.y as usize + 1];
255+
let mut paths: Vec<Vec<Point<i32>>> = Vec::new();
256+
257+
while let Some(Reverse((_, location))) = to_visit.pop() {
258+
let current_len = location.current_path.len() as i32;
259+
let (x, y) = (location.point.x as usize, location.point.y as usize);
260+
261+
if grid[y][x] < current_len {
262+
continue;
263+
}
264+
grid[y][x] = current_len;
265+
266+
for next_location in get_next_locations(&location) {
267+
let next_point = next_location.point;
268+
269+
if next_point > max_point {
270+
continue;
271+
}
272+
273+
match map_grid.get(&next_point) {
274+
Some(Tiles::End) if location.cost == total_cost - 1 => {
275+
paths.push(next_location.current_path);
276+
}
277+
Some(Tiles::Wall) => continue,
278+
Some(_) if location.cost < total_cost => {
279+
let heuristic = get_distance_from_end(next_point, end_pos) as i32;
280+
to_visit.push(Reverse((location.cost + heuristic, next_location)));
281+
}
282+
_ => {}
283+
}
284+
}
285+
}
286+
287+
paths.into_iter().flatten().collect::<HashSet<_>>().len() as i32
288+
}
289+
290+
fn part2(input_map: String) -> i32 {
291+
let map = input_map.lines().collect::<Vec<_>>();
292+
let (map_grid, current_pos, end_pos) = create_grid(map);
293+
294+
let total_cost = a_star(map_grid.clone(), current_pos, end_pos, Direction::RIGHT);
295+
find_all_paths(map_grid, current_pos, end_pos, Direction::RIGHT, total_cost)
296+
}
297+
298+
#[cfg(test)]
299+
mod test {
300+
use super::*;
301+
302+
#[test]
303+
fn test1() {
304+
assert_eq!(part1(utils::read_file("./sample1.txt")), 7036)
305+
}
306+
307+
#[test]
308+
fn test2() {
309+
assert_eq!(part2(utils::read_file("./sample1.txt")), 45)
310+
}
311+
}
312+
313+
fn main() {
314+
utils::run(16, vec!["sample1.txt", "input.txt"], &part1, &part2);
315+
}

‎2024/day16/sample1.txt

Copy file name to clipboard
+15Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
###############
2+
#.......#....E#
3+
#.#.###.#.###.#
4+
#.....#.#...#.#
5+
#.###.#####.#.#
6+
#.#.#.......#.#
7+
#.#.#####.###.#
8+
#...........#.#
9+
###.#.#####.#.#
10+
#...#.....#.#.#
11+
#.#.#.###.#.#.#
12+
#.....#...#.#.#
13+
#.###.#.#.#.#.#
14+
#S..#.....#...#
15+
###############

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.