bwc9876.dev
Advent of Code solutions
1use std::collections::HashMap;
2
3use advent_core::{day_stuff, ex_for_day, Day};
4use utils::{dir::CARDINALS, pos::Position, tiles};
5
6pub struct Day20;
7
8tiles!(Tile, [
9 '.' => Open,
10 '#' => Wall,
11 'S' => Start,
12 'E' => End,
13]);
14
15type Grid = utils::grid::Grid<Tile>;
16
17impl Day for Day20 {
18 // Technically it's correct :)
19 day_stuff!(20, "0", "0", Grid);
20
21 fn part_1(input: Self::Input) -> Option<String> {
22 let end_pos = input.find_tile(&Tile::End).unwrap();
23 let start_pos = input.find_tile(&Tile::Start).unwrap();
24 let mut costs = HashMap::with_capacity(100);
25 let mut curs = end_pos;
26 let mut cost = 0;
27 while curs != start_pos {
28 costs.insert(curs, cost);
29 let (_, next_pos, _) = input
30 .relatives(curs, &CARDINALS)
31 .find(|(_, p, t)| **t != Tile::Wall && !costs.contains_key(p))
32 .unwrap();
33 curs = next_pos;
34 cost += 1;
35 }
36 costs.insert(start_pos, cost);
37
38 let mut cheat_set = HashMap::<(Position, Position), usize>::with_capacity(costs.len());
39 for (pos_a, cost_a) in costs.iter() {
40 for (pos_b, cost_b) in costs.iter() {
41 if cost_b < cost_a {
42 let diff = *cost_a - *cost_b;
43 let dist = pos_a.manhattan(pos_b).unsigned_abs();
44 if dist <= 2 {
45 cheat_set.insert((*pos_a, *pos_b), diff - dist);
46 }
47 }
48 }
49 }
50
51 let ans = cheat_set.values().filter(|c| **c >= 100).count();
52
53 Some(ans.to_string())
54 }
55
56 fn part_2(input: Self::Input) -> Option<String> {
57 let end_pos = input.find_tile(&Tile::End).unwrap();
58 let start_pos = input.find_tile(&Tile::Start).unwrap();
59 let mut costs = HashMap::with_capacity(100);
60 let mut curs = end_pos;
61 let mut cost = 0;
62 while curs != start_pos {
63 costs.insert(curs, cost);
64 let (_, next_pos, _) = input
65 .relatives(curs, &CARDINALS)
66 .find(|(_, p, t)| **t != Tile::Wall && !costs.contains_key(p))
67 .unwrap();
68 curs = next_pos;
69 cost += 1;
70 }
71 costs.insert(start_pos, cost);
72
73 let mut cheat_set = HashMap::<(Position, Position), usize>::with_capacity(costs.len());
74 for (pos_a, cost_a) in costs.iter() {
75 for (pos_b, cost_b) in costs.iter() {
76 if cost_b < cost_a {
77 let diff = *cost_a - *cost_b;
78 let dist = pos_a.manhattan(pos_b).unsigned_abs();
79 if dist <= 20 {
80 cheat_set.insert((*pos_a, *pos_b), diff - dist);
81 }
82 }
83 }
84 }
85
86 let ans = cheat_set.values().filter(|c| **c >= 100).count();
87
88 Some(ans.to_string())
89 }
90
91 fn parse_input(input: &str) -> Self::Input {
92 Grid::parse(input)
93 }
94}