aoc/year2024/
day20.rs

1//! # Race Condition
2//!
3//! Examining the input shows that there is only a single path from start to finish with
4//! no branches. This simplifies checking for shortcuts as any empty space will be on the shortest
5//! path from start to end. The cheating rules allow us to "warp" up to `n` squares away to any
6//! empty space as measured by [manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry).
7//!
8//! For part one this is a distance of 2. When checking surrounding squares we make 2 optimizations:
9//!
10//! * Don't check any squares only 1 away as we can always just move to these normally.
11//! * Checking from point `p => q` is always the negative of `q => p`, e.g if `p = 30, q = 50` then
12//!   `p => q = 20` and `q => p = -20`. This means we only ever need to check any pair once.
13//! * Additionally we only need to check down and right. Previous rows and columns will already
14//!   have checked points above and to the left when we reach an empty square.
15//!
16//! ```none
17//!       #         .
18//!      ###       ...
19//!     ##P## =>  ....#
20//!      ###       ...
21//!       #         #
22//! ```
23//!
24//! For part two the distance is increased to 20 and the shape now resembles a wonky diamond.
25//! This shape ensures complete coverage without duplicating checks.
26//!
27//! ```none
28//!      #        .
29//!     ###      ...
30//!    ##P## => ..P##
31//!     ###      ###
32//!      #        #
33//! ```
34use crate::util::grid::*;
35use crate::util::point::*;
36use crate::util::thread::*;
37
38/// Create a grid the same size as input with the time taken from start to any location.
39pub fn parse(input: &str) -> Grid<i32> {
40    let grid = Grid::parse(input);
41    let start = grid.find(b'S').unwrap();
42    let end = grid.find(b'E').unwrap();
43
44    let mut time = grid.same_size_with(i32::MAX);
45    let mut elapsed = 0;
46
47    // Find starting direction, assuming start position is surrounded by 3 walls.
48    let mut position = start;
49    let mut direction = ORTHOGONAL.into_iter().find(|&o| grid[position + o] != b'#').unwrap();
50
51    while position != end {
52        time[position] = elapsed;
53        elapsed += 1;
54
55        // There are no branches so we only ever need to go straight ahead or turn left or right.
56        direction = [direction, direction.clockwise(), direction.counter_clockwise()]
57            .into_iter()
58            .find(|&d| grid[position + d] != b'#')
59            .unwrap();
60        position += direction;
61    }
62
63    time[end] = elapsed;
64    time
65}
66
67pub fn part1(time: &Grid<i32>) -> u32 {
68    let mut cheats = 0;
69
70    for y in 1..time.height - 1 {
71        for x in 1..time.width - 1 {
72            let point = Point::new(x, y);
73
74            // We only need to check 2 points to the right and down as previous empty squares
75            // have already checked up and to the left.
76            if time[point] != i32::MAX {
77                cheats += check(time, point, Point::new(2, 0));
78                cheats += check(time, point, Point::new(0, 2));
79            }
80        }
81    }
82
83    cheats
84}
85
86/// Searches for all cheats up to distance 20, parallelizing the work over multiple threads.
87pub fn part2(time: &Grid<i32>) -> u32 {
88    let mut items = Vec::with_capacity(10_000);
89
90    for y in 1..time.height - 1 {
91        for x in 1..time.width - 1 {
92            let point = Point::new(x, y);
93
94            if time[point] != i32::MAX {
95                items.push(point);
96            }
97        }
98    }
99
100    // Use as many cores as possible to parallelize the remaining search.
101    let result = spawn_parallel_iterator(&items, |iter| worker(time, iter));
102    result.into_iter().sum()
103}
104
105fn worker(time: &Grid<i32>, iter: ParIter<'_, Point>) -> u32 {
106    let mut cheats = 0;
107
108    // (p1, p2) is the reciprocal of (p2, p1) so we only need to check each pair once.
109    for &point in iter {
110        for x in 2..21 {
111            cheats += check(time, point, Point::new(x, 0));
112        }
113
114        for y in 1..21 {
115            for x in (y - 20)..(21 - y) {
116                cheats += check(time, point, Point::new(x, y));
117            }
118        }
119    }
120
121    cheats
122}
123
124// Check if we save enough time warping to another square.
125#[inline]
126fn check(time: &Grid<i32>, first: Point, delta: Point) -> u32 {
127    let second = first + delta;
128
129    (time.contains(second)
130        && time[second] != i32::MAX
131        && (time[first] - time[second]).abs() - first.manhattan(second) >= 100) as u32
132}
aoc/year2024/day20.rs

aoc/year2024/
day20.rs
