bwc9876.dev
Advent of Code solutions
1use advent_core::{day_stuff, ex_for_day, Day};
2use rayon::iter::{IntoParallelIterator, ParallelIterator};
3use utils::{grid::Grid, pos::Position, tiles, upos, yippee};
4
5pub struct Day12;
6
7tiles!(Tile, [
8 '#' => Filled,
9 '.' => Empty,
10]);
11
12type Present = utils::grid::Grid<Tile>;
13type Input = (Vec<[Vec<Position>; 4]>, Vec<((usize, usize), Vec<usize>)>);
14
15pub const KERNS: [Position; 9] = [
16 Position::new(0, 0),
17 Position::new(0, -1),
18 Position::new(0, 1),
19 Position::new(1, 0),
20 Position::new(-1, 0),
21 Position::new(1, 1),
22 Position::new(1, -1),
23 Position::new(-1, 1),
24 Position::new(-1, -1),
25];
26
27fn rot_pos(Position { x, y }: Position) -> Position {
28 let (x, y) = match (x, y) {
29 (0, 0) => (0, 0),
30 (1, 0) => (0, -1),
31 (0, -1) => (-1, 0),
32 (-1, 0) => (0, 1),
33 (0, 1) => (1, 0),
34 (1, 1) => (1, -1),
35 (1, -1) => (-1, -1),
36 (-1, -1) => (-1, 1),
37 (-1, 1) => (1, 1),
38 _ => unreachable!(),
39 };
40 Position::new(x, y)
41}
42
43fn try_place_at(pos: Position, shape: &[Position], grid: &mut Present) -> bool {
44 let empties = grid
45 .relatives(pos, shape)
46 .take_while(|(_, _, t)| **t == Tile::Empty)
47 .map(|(_, p, _)| p)
48 .collect::<Vec<_>>();
49
50 if empties.len() == shape.len() {
51 for pos in empties {
52 *(grid.get_mut(pos).unwrap()) = Tile::Filled;
53 }
54 true
55 } else {
56 false
57 }
58}
59
60fn undo_place(pos: Position, shape: &[Position], grid: &mut Present) {
61 let positions = grid
62 .relatives(pos, shape)
63 .map(|(_, p, _)| p)
64 .collect::<Vec<_>>();
65
66 for pos in positions {
67 *(grid.get_mut(pos).unwrap()) = Tile::Empty;
68 }
69}
70
71fn solve(shapes: &Vec<[Vec<Position>; 4]>, grid: &mut Present, targets: &mut Vec<usize>) -> bool {
72 let next_shape = targets
73 .iter()
74 .enumerate()
75 .find(|(_, amnt)| **amnt != 0)
76 .map(|(f, _)| f);
77
78 let (x, y) = grid.size();
79
80 if let Some(next_shape) = next_shape {
81 let shape_all_rots = shapes.get(next_shape).unwrap();
82 for y in 1..(y - 1) {
83 for x in 1..(x - 1) {
84 for shape in shape_all_rots {
85 if try_place_at(upos!(x, y), shape.as_slice(), grid) {
86 targets[next_shape] -= 1;
87 let inner_res = solve(shapes, grid, targets);
88 if inner_res {
89 return inner_res;
90 } else {
91 targets[next_shape] += 1;
92 undo_place(upos!(x, y), shape.as_slice(), grid);
93 }
94 }
95 }
96 }
97 }
98 false
99 } else {
100 true
101 }
102}
103
104impl Day for Day12 {
105 day_stuff!(12, "2", "🥳", Input);
106
107 fn part_1((shapes, targets): Self::Input) -> Option<String> {
108 let ans = targets
109 .into_par_iter()
110 .filter_map(|((x, y), mut avail)| {
111 let area_needed = shapes
112 .iter()
113 .enumerate()
114 .map(|(i, s)| s[0].len() * avail[i])
115 .sum::<usize>();
116 if area_needed > (x * y) {
117 return None;
118 }
119 let mut grid = Grid::new(vec![vec![Tile::Empty; x]; y]);
120 let can_fit = solve(&shapes, &mut grid, &mut avail);
121 if can_fit {
122 Some(0)
123 } else {
124 None
125 }
126 })
127 .count();
128
129 Some(ans.to_string())
130 }
131
132 yippee!();
133
134 fn parse_input(input: &str) -> Self::Input {
135 let sections = input.split("\n\n").collect::<Vec<_>>();
136 let shapes = sections
137 .iter()
138 .take(sections.len() - 1)
139 .map(|s| {
140 let (_, grid) = s.split_once('\n').unwrap();
141 let grid = Present::parse(grid);
142 let rels = grid
143 .relatives(Position::new(1, 1), &KERNS)
144 .filter(|(_, _, t)| **t == Tile::Filled)
145 .map(|(kern, _, _)| kern)
146 .collect::<Vec<_>>();
147
148 let rels90: Vec<_> = rels.iter().copied().map(rot_pos).collect();
149
150 let rels180: Vec<_> = rels90.iter().copied().map(rot_pos).collect();
151
152 let rels270: Vec<_> = rels180.iter().copied().map(rot_pos).collect();
153
154 [rels, rels90, rels180, rels270]
155 })
156 .collect();
157
158 let targets = sections
159 .last()
160 .unwrap()
161 .lines()
162 .map(|l| {
163 let (size, amnts) = l.split_once(':').unwrap();
164 let (x, y) = size.split_once('x').unwrap();
165 let amnts = amnts
166 .trim()
167 .split(' ')
168 .map(|x| x.parse().unwrap())
169 .collect();
170 ((x.parse().unwrap(), y.parse().unwrap()), amnts)
171 })
172 .collect();
173
174 (shapes, targets)
175 }
176}