bwc9876.dev
Advent of Code solutions
1use std::collections::HashSet;
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use utils::{dir::Direction, pos::Position, prelude::GridCursor, tiles};
5
6pub struct Day6;
7
8tiles!(Tile, [
9'.' => Floor,
10'#' => Wall,
11'^' => GuardStart
12]);
13
14impl Tile {
15 fn is_open(&self) -> bool {
16 matches!(self, Self::Floor | Self::GuardStart)
17 }
18}
19
20type Grid = utils::grid::Grid<Tile>;
21
22/// Returns true if we get into a loop
23fn crawl_grid_with_obs(mut curs: GridCursor<Tile, Direction>, obs_pos: Position) -> bool {
24 let mut visited = HashSet::new();
25
26 while let Some((pos, tile)) = curs.peek_forward() {
27 visited.insert(curs.state());
28 if tile.is_open() && pos != obs_pos {
29 curs.move_forward();
30 } else {
31 curs.turn(true);
32 }
33
34 if visited.contains(&curs.state()) {
35 return true;
36 }
37 }
38
39 false
40}
41
42impl Day for Day6 {
43 day_stuff!(6, "41", "6", Grid);
44
45 fn part_1(input: Self::Input) -> Option<String> {
46 let mut curs = input
47 .cursor_at_tile(&Tile::GuardStart, Direction::North)
48 .unwrap();
49
50 let mut visited = HashSet::with_capacity(input.width() * input.height());
51
52 while let Some((_next_pos, tile)) = curs.peek_forward() {
53 visited.insert(curs.pos);
54 if tile.is_open() {
55 curs.move_forward();
56 } else {
57 curs.turn(true);
58 }
59 }
60
61 // While let means we'll be missing one
62 visited.insert(curs.pos);
63
64 Some(visited.len().to_string())
65 }
66
67 fn part_2(input: Self::Input) -> Option<String> {
68 let mut curs = input
69 .cursor_at_tile(&Tile::GuardStart, Direction::North)
70 .unwrap();
71
72 let start_curs = curs;
73
74 let mut obs = HashSet::with_capacity(input.width() * input.height());
75
76 while let Some((possible, tile)) = curs.peek_forward() {
77 if !obs.contains(&possible) {
78 let curs_2 = start_curs;
79 if crawl_grid_with_obs(curs_2, possible) {
80 obs.insert(possible);
81 }
82 }
83
84 if tile.is_open() {
85 curs.move_forward();
86 } else {
87 curs.turn(true);
88 }
89 }
90
91 Some(obs.len().to_string())
92 }
93
94 fn parse_input(input: &str) -> Self::Input {
95 Grid::parse(input)
96 }
97}
98
99// - ORIGINAL PART 2 : BRUTE FORCE APPROACH (Im so sad i had to do this) -
100
101// let mut c = 0;
102
103// let start_pos = input
104// .iter()
105// .find_map(|(pos, c)| {
106// if matches!(c, Tile::GuardStart) {
107// Some(pos)
108// } else {
109// None
110// }
111// })
112// .unwrap();
113
114// for x in 0..input.width() {
115// for y in 0..input.height() {
116// let pos = mpos!(x as isize, y as isize);
117// if matches!(input.get(pos).unwrap(), Tile::Floor) {
118// let mut i2 = input.clone();
119// i2.iter_mut().for_each(|(pt, r)| if pt == pos { *r = Tile::Wall; });
120// let mut curs = GridCursor::new(&i2, start_pos, Direction::North);
121
122// let mut visited = HashSet::with_capacity(i2.width());
123
124// loop {
125// visited.insert((curs.pos, curs.dir));
126// if let Some(val_ahead) = i2.get(curs.pos.move_dir(curs.dir)) {
127// if val_ahead.is_open() {
128// curs.move_forward();
129// } else {
130// curs.turn(true);
131// }
132// if visited.contains(&(curs.pos, curs.dir)) {
133// c += 1;
134// break;
135// }
136// } else {
137// break;
138// }
139// }
140// }
141// }
142// }
143
144// Some(c.to_string())