bwc9876.dev
Advent of Code solutions
1use std::collections::HashSet;
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use utils::{
5 dir::{Direction, Movement, CARDINALS},
6 pos::Position,
7 prelude::GridCursor,
8};
9
10pub struct Day12;
11
12type Grid = utils::grid::Grid<char>;
13
14fn trace_perim(
15 grid: &Grid,
16 starting_pos: Position,
17 initial_dir: Direction,
18 c: char,
19) -> (usize, HashSet<Position>) {
20 let mut perims = HashSet::with_capacity(100);
21 let mut turns = 0;
22 let mut curs = GridCursor::new(grid, starting_pos, initial_dir);
23 let mut init = false;
24
25 while (curs.pos, curs.dir) != (starting_pos, initial_dir) || !init {
26 perims.insert(curs.pos);
27
28 let look_left = curs.pos.add(&curs.dir.ninety_deg(false).get_kernel());
29
30 if grid.get(look_left).is_some_and(|c2| *c2 == c) {
31 // Interior corner, turn left!
32 curs.turn(false);
33 curs.move_forward();
34 turns += 1;
35 } else if curs.peek_forward().is_none_or(|(_, c2)| *c2 != c) {
36 // Exterior corner, turn right!
37 curs.turn(true);
38 turns += 1;
39 } else {
40 // Valid, keep going!
41 curs.move_forward();
42 }
43
44 init = true;
45 }
46
47 (turns, perims)
48}
49
50impl Day for Day12 {
51 fn part_1(input: Self::Input) -> Option<String> {
52 let mut visited = HashSet::with_capacity(50);
53 let mut total = 0;
54
55 for (pos, c) in input.iter() {
56 if !visited.contains(&pos) {
57 let mut flood = vec![pos];
58
59 let (mut area, mut perim) = (0, 0);
60
61 while !flood.is_empty() {
62 let mut next = vec![];
63
64 for pos2 in flood.iter() {
65 if let Some(c2) = input.get(*pos2)
66 && c2 == c
67 && !visited.contains(pos2)
68 {
69 area += 1;
70 let mut rel = input
71 .relatives(*pos2, &CARDINALS)
72 .filter_map(
73 |(_, pos3, c3)| if c2 == c3 { Some(pos3) } else { None },
74 )
75 .collect::<Vec<_>>();
76
77 if rel.len() != 4 {
78 perim += 4 - rel.len();
79 }
80
81 visited.insert(*pos2);
82 next.append(&mut rel);
83 }
84 }
85
86 flood = next;
87 }
88
89 total += area * perim;
90
91 visited.insert(pos);
92 }
93 }
94
95 Some(total.to_string())
96 }
97
98 // TODO: Still working on the ""nice"" way of doing this one
99 fn part_2(input: Self::Input) -> Option<String> {
100 let mut visited = HashSet::with_capacity(50);
101 let mut shapes = Vec::<(usize, usize, HashSet<Position>)>::with_capacity(30);
102
103 for (pos, c) in input.iter() {
104 if !visited.contains(&pos) {
105 let (turns, perimeters) = trace_perim(&input, pos, Direction::East, *c);
106
107 let mut all_tiles = HashSet::with_capacity(turns);
108
109 let mut flood = vec![pos];
110
111 while !flood.is_empty() {
112 let mut next = vec![];
113
114 for pos2 in flood.iter() {
115 if let Some(c2) = input.get(*pos2)
116 && c2 == c
117 && !visited.contains(pos2)
118 {
119 all_tiles.insert(*pos2);
120
121 let mut rel = input
122 .relatives(*pos2, &CARDINALS)
123 .filter_map(
124 |(_, pos3, c3)| if c2 == c3 { Some(pos3) } else { None },
125 )
126 .collect::<Vec<_>>();
127
128 if !perimeters.contains(pos2) {
129 let _inner_shape = if input
130 .get(pos2.add(&Direction::East.get_kernel()))
131 .is_some_and(|c2| c2 != c)
132 {
133 Some(trace_perim(&input, *pos2, Direction::North, *c))
134 } else if input
135 .get(pos2.add(&Direction::North.get_kernel()))
136 .is_some_and(|c2| c2 != c)
137 {
138 Some(trace_perim(&input, *pos2, Direction::East, *c))
139 } else {
140 None
141 };
142 }
143
144 visited.insert(*pos2);
145 next.append(&mut rel);
146 }
147 }
148
149 flood = next;
150 }
151
152 shapes.push((all_tiles.len(), turns, all_tiles))
153 }
154 }
155
156 Some(
157 shapes
158 .into_iter()
159 .map(|(area, turns, _)| area * turns)
160 .sum::<usize>()
161 .to_string(),
162 )
163 }
164
165 day_stuff!(12, "1930", "1206", Grid);
166
167 fn parse_input(input: &str) -> Self::Input {
168 Grid::parse(input.trim())
169 }
170}