bwc9876.dev
Advent of Code solutions
1use std::{
2 cmp::Ordering,
3 collections::{BinaryHeap, HashMap},
4};
5
6use advent_core::{day_stuff, ex_for_day, Day};
7use utils::{pos::Position, upos};
8
9pub struct Day18;
10
11#[derive(Clone, Eq, PartialEq)]
12struct DState {
13 cost: usize,
14 pos: Position,
15 step_no: usize,
16}
17
18impl Ord for DState {
19 fn cmp(&self, other: &Self) -> Ordering {
20 other.cost.cmp(&self.cost)
21 }
22}
23
24impl PartialOrd for DState {
25 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
26 Some(self.cmp(other))
27 }
28}
29
30impl Day for Day18 {
31 day_stuff!(18, "22", "6,1", ((usize, usize), usize, Vec<Position>));
32
33 fn part_1((bounds, fallen, input): Self::Input) -> Option<String> {
34 let start_pos = Position::zero();
35 let end_pos = upos!(bounds.0 - 1, bounds.1 - 1);
36
37 let mut queue = BinaryHeap::new();
38
39 queue.push(DState {
40 cost: 0,
41 pos: start_pos,
42 step_no: 0,
43 });
44
45 let mut dist = HashMap::<Position, usize>::new();
46
47 while let Some(DState { cost, pos, step_no }) = queue.pop() {
48 if pos == end_pos {
49 return Some(cost.to_string());
50 }
51
52 if dist.get(&pos).is_some_and(|min_score| *min_score < cost) {
53 continue;
54 }
55
56 for (next_pos, _dir) in pos
57 .adjacents_checked(bounds)
58 .filter(|(p, _)| input.iter().take(fallen).all(|op| op != p))
59 {
60 let next_state = DState {
61 cost: cost + 1,
62 pos: next_pos,
63 step_no: step_no + 1,
64 };
65 if next_state.cost < *dist.get(&next_state.pos).unwrap_or(&usize::MAX) {
66 *dist.entry(next_state.pos).or_insert(usize::MAX) = next_state.cost;
67 queue.push(next_state);
68 }
69 }
70 }
71
72 panic!("No Path")
73 }
74
75 fn part_2((bounds, _, input): Self::Input) -> Option<String> {
76 for i in 0..input.len() {
77 let start_pos = Position::zero();
78 let end_pos = upos!(bounds.0 - 1, bounds.1 - 1);
79
80 let mut queue = BinaryHeap::new();
81
82 queue.push(DState {
83 cost: 0,
84 pos: start_pos,
85 step_no: 0,
86 });
87
88 let mut dist = HashMap::<Position, usize>::new();
89 let mut flag = false;
90
91 while let Some(DState { cost, pos, step_no }) = queue.pop() {
92 if pos == end_pos {
93 flag = true;
94 break;
95 }
96
97 if dist.get(&pos).is_some_and(|min_score| *min_score < cost) {
98 continue;
99 }
100
101 for (next_pos, _dir) in pos
102 .adjacents_checked(bounds)
103 .filter(|(p, _)| input.iter().take(i + 1).all(|op| op != p))
104 {
105 let next_state = DState {
106 cost: cost + 1,
107 pos: next_pos,
108 step_no: step_no + 1,
109 };
110 if next_state.cost < *dist.get(&next_state.pos).unwrap_or(&usize::MAX) {
111 *dist.entry(next_state.pos).or_insert(usize::MAX) = next_state.cost;
112 queue.push(next_state);
113 }
114 }
115 }
116 if !flag {
117 return Some(format!("{},{}", input[i].x, input[i].y));
118 }
119 }
120 panic!("All paths are possible!")
121 }
122
123 fn parse_input(input: &str) -> Self::Input {
124 let (bounds, rest) = input.trim().split_once("\n\n").unwrap();
125
126 let mut extra = bounds.split(',').map(|s| s.parse::<usize>().unwrap());
127 let bounds = (extra.next().unwrap(), extra.next().unwrap());
128 let fallen = extra.next().unwrap();
129
130 let input = rest
131 .lines()
132 .map(|l| {
133 let (x, y) = l.split_once(',').unwrap();
134 upos!(x.parse::<usize>().unwrap(), y.parse::<usize>().unwrap())
135 })
136 .collect();
137
138 (bounds, fallen, input)
139 }
140}