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 3 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    // Add padding to avoid boundary checks.
45    let mut time = Grid::new(grid.width + 20, grid.height + 20, i32::MAX);
46    let mut elapsed = 0;
47
48    // Find starting direction, assuming start position is surrounded by 3 walls.
49    let mut position = start;
50    let mut direction = ORTHOGONAL.into_iter().find(|&o| grid[position + o] != b'#').unwrap();
51
52    while position != end {
53        time[position] = elapsed;
54        elapsed += 1;
55
56        // There are no branches so we only ever need to go straight ahead or turn left or right.
57        direction = [direction, direction.clockwise(), direction.counter_clockwise()]
58            .into_iter()
59            .find(|&d| grid[position + d] != b'#')
60            .unwrap();
61        position += direction;
62    }
63
64    time[end] = elapsed;
65    time
66}
67
68pub fn part1(time: &Grid<i32>) -> u32 {
69    [Point::new(2, 0), Point::new(0, 2)].iter().map(|&delta| cheats(time, delta)).sum()
70}
71
72/// Searches for all cheats up to distance 20, parallelizing the work over multiple threads.
73pub fn part2(time: &Grid<i32>) -> u32 {
74    let mut deltas = Vec::with_capacity(419);
75
76    for x in 2..21 {
77        deltas.push(Point::new(x, 0));
78    }
79
80    for y in 1..21 {
81        for x in (y - 20)..(21 - y) {
82            deltas.push(Point::new(x, y));
83        }
84    }
85
86    // // Use as many cores as possible to parallelize the remaining search.
87    spawn_parallel_iterator(&deltas, |iter| iter.map(|&delta| cheats(time, delta)).sum::<u32>())
88        .into_iter()
89        .sum()
90}
91
92/// Compare two slices against each other so that the compiler can auto-vectorize the loops.
93/// Boundary checks are not needed due to the padding on the right and bottom of the grid.
94fn cheats(time: &Grid<i32>, delta: Point) -> u32 {
95    let start = Point::new(1, 1);
96    let maximum = time.width * time.height;
97    let threshold = 100 + delta.manhattan(ORIGIN);
98    let slice_from = |point: Point| &time.bytes[(time.width * point.y + point.x) as usize..];
99
100    slice_from(start)
101        .iter()
102        .zip(slice_from(start + delta))
103        .map(|(&from, &to)| {
104            let saved = (from - to).abs();
105            u32::from(threshold <= saved && saved <= maximum)
106        })
107        .sum()
108}
aoc/year2024/day20.rs

aoc/year2024/
day20.rs
