bwc9876.dev
Advent of Code solutions
1use std::collections::{HashMap, HashSet, VecDeque};
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use utils::{dir::Direction, pos::Position, tiles};
5
6pub struct Day7;
7
8tiles!(Tile, [
9 'S' => Start,
10 '^' => Splitter,
11 '.' => Empty,
12]);
13
14type Grid = utils::grid::Grid<Tile>;
15
16impl Day for Day7 {
17 day_stuff!(7, "21", "40", Grid);
18
19 fn part_1(input: Self::Input) -> Option<String> {
20 let (start, _) = input.iter().find(|(_, t)| **t == Tile::Start).unwrap();
21 let mut queue = VecDeque::<Position>::new();
22 let mut seen = HashSet::<Position>::with_capacity(input.size().1);
23
24 queue.push_back(start);
25
26 let mut splits = 0;
27
28 while let Some(pos) = queue.pop_front() {
29 if seen.contains(&pos) {
30 continue;
31 }
32 seen.insert(pos);
33 let next_pos = Position::new(pos.x, pos.y + 1);
34 match input.get(next_pos) {
35 Some(Tile::Splitter) => {
36 splits += 1;
37 queue.push_back(Position::new(pos.x + 1, pos.y));
38 queue.push_back(Position::new(pos.x - 1, pos.y));
39 }
40 Some(Tile::Empty) => {
41 queue.push_back(next_pos);
42 }
43 _ => {}
44 }
45 }
46
47 Some(splits.to_string())
48 }
49
50 fn part_2(input: Self::Input) -> Option<String> {
51 let (start, _) = input.iter().find(|(_, t)| **t == Tile::Start).unwrap();
52 let mut queue = VecDeque::<Position>::new();
53 let mut seen = HashMap::<Position, usize>::new();
54
55 seen.insert(start, 1);
56 queue.push_front(start);
57
58 let mut splits = 0;
59
60 while let Some(pos) = queue.pop_front() {
61 let amnt = seen.get(&pos).copied().unwrap_or_default();
62 let next_pos = pos.move_dir(Direction::South);
63 match input.get(next_pos) {
64 Some(Tile::Splitter) => {
65 for (next_pos, _) in next_pos.relatives(&[Direction::West, Direction::East]) {
66 if let Some(curr) = seen.get_mut(&next_pos) {
67 *curr += amnt;
68 } else {
69 seen.insert(next_pos, amnt);
70 queue.push_back(next_pos);
71 }
72 }
73 }
74 Some(Tile::Empty) => {
75 if let Some(curr) = seen.get_mut(&next_pos) {
76 *curr += amnt;
77 } else {
78 seen.insert(next_pos, amnt);
79 queue.push_back(next_pos);
80 }
81 }
82 None => {
83 splits += amnt;
84 }
85 _ => {}
86 }
87 }
88
89 Some(splits.to_string())
90 }
91
92 fn parse_input(input: &str) -> Self::Input {
93 Grid::parse(input)
94 }
95}