Day 20: Race Condition

pub fn part1(input: &PuzzleInput) -> String {
    let path_grid = shortest_path_grid(&input.maze);
    let cheats = find_cheats(&path_grid);

    let mut result = 0;
    for cheat in cheats.iter() {
        if cheat.2 >= 100 {
            result += 1;
        }
    }

    result.to_string()
}

pub fn find_cheats(grid: &Grid2D<u32>) -> Vec<(Coordinate, Direction, u32)> {
    let mut result = Vec::new();

    for x in 1..(grid.width() - 1) {
        for y in 1..(grid.height() - 1) {
            for dir in Direction::cardinal() {
                let pos = Coordinate::new(x as i32, y as i32);

                if grid[pos] == u32::MAX {
                    continue;
                }

                let neighbor = pos.neighbor(dir);
                let neighbor_neighbor = neighbor.neighbor(dir);

                if grid[neighbor] != u32::MAX {
                    continue;
                }

                if grid.get(neighbor_neighbor).is_none() {
                    continue;
                }

                if grid[neighbor_neighbor] == u32::MAX {
                    continue;
                }

                let cur_val = grid[pos];
                let next_val = grid[neighbor_neighbor];

                if (cur_val.saturating_sub(next_val).saturating_sub(2) > 0) {
                    result.push((pos, dir, (cur_val - next_val).saturating_sub(2)));
                }
            }
        }
    }

    result
}

pub fn shortest_path_grid(grid: &Grid2D<char>) -> Grid2D<u32> {
    let mut result = grid.map(|_| u32::MAX);
    let end = grid.iter().find(|(_, &c)| c == 'E').unwrap().0;

    let mut queue = VecDeque::new();
    queue.push_back((end, 0));

    while let Some((current, distance)) = queue.pop_front() {
        result[current] = distance;

        if grid[current] == 'S' {
            return result;
        }

        for neighbor in current.neighbors() {
            if grid[neighbor] != '#' && result[neighbor] > distance + 1 {
                queue.push_back((neighbor, distance + 1));
            }
        }
    }

    unreachable!()
}

This runs for almost 3 seconds, I'll need to improve that later.

pub fn part2(input: &PuzzleInput) -> String {
    let path_grid = shortest_path_grid(&input.maze);
    let mut cheat_collection: HashMap<u32, HashSet<(Coordinate, Coordinate)>> = HashMap::new();

    for x in 1..(path_grid.width() - 1) {
        for y in 1..(path_grid.height() - 1) {
            let pos = Coordinate::new(x as i32, y as i32);

            let cheats = find_cheats(&path_grid, pos);
            for (dist, pairs) in cheats.iter() {
                cheat_collection.entry(*dist).or_default().extend(pairs);
            }
        }
    }

    let mut result = 0;

    for (dist, pairs) in cheat_collection.iter() {
        if dist >= &100 {
            result += pairs.len();
        }
    }

    result.to_string()
}

fn find_cheats(
    grid: &Grid2D<u32>,
    start_pos: Coordinate,
) -> HashMap<u32, HashSet<(Coordinate, Coordinate)>> {
    if grid[start_pos] == u32::MAX {
        return HashMap::new();
    }

    let mut q = VecDeque::new();
    q.push_back((start_pos, 0u32));

    let mut result: HashMap<u32, HashSet<(Coordinate, Coordinate)>> = HashMap::new();
    let mut visited = HashSet::new();

    while let Some((pos, dist)) = q.pop_front() {
        if dist >= 20 {
            break;
        }

        if !visited.insert((pos, dist)) {
            continue;
        }

        for dir in Direction::cardinal() {
            let neighbor = pos.neighbor(dir);

            if grid.get(neighbor).is_none() {
                continue;
            }

            if grid[neighbor] != u32::MAX {
                let saved = grid[start_pos]
                    .saturating_sub(grid[neighbor])
                    .saturating_sub(start_pos.manhattan_distance(neighbor) as u32);

                if saved > 0 {
                    result
                        .entry(saved)
                        .or_default()
                        .insert((start_pos, neighbor));
                }
            }

            q.push_back((neighbor, dist + 1));
        }
    }

    result
}

Class {
	#name : 'Day20Solver',
	#superclass : 'AoCSolver',
	#instVars : [ 'startPos', 'endPos', 'walls', 'goal', 'width', 'height', 'endDistance' ],
	#category : 'AoCDay20',
	#package : 'AoCDay20'
}

Day20Solver >> parseRawData [
	height := rawData lines size.
	width := (rawData lines at: 1) size.
	walls := Set new.
	rawData lines withIndexDo: [ :row :r |
		row withIndexDo: [ :val :c |
			val = $# ifTrue: [ walls add: r @ c ].
			val = $S ifTrue: [ startPos := r @ c ].
			val = $E ifTrue: [ endPos := r @ c ] ] ].
	self buildEndDistance
]

Day20Solver >> buildEndDistance [
	| curr dist |
	endDistance := Dictionary new.
	curr := Set newFrom: { endPos }.
	dist := 0.
	[ curr isEmpty ] whileFalse: [
		curr do: [ :pos | endDistance at: pos put: dist ].
		dist := dist + 1.
		curr := ((curr flatCollect: [ :pos | pos fourNeighbors ])
			select: [ :pos | self canMove: pos ]) 
			reject: [ :pos | endDistance includesKey: pos ] ]
]

Day20Solver >> canMove: pos [
	^ (pos between: 1 @ 1 and: height @ width) and: [ (walls includes: pos) not ]
]

Day20Solver >> neighborsOf: aPoint distance: dist [
	| neighbors |
	neighbors := (aPoint x - dist to: aPoint x + dist) flatCollect: [ :r |
		             (aPoint y - dist to: aPoint y + dist) collect: [ :c | r @ c ] ].
	^ neighbors select: [ :pos | (self canMove: pos) and: [ (aPoint manhattanDistanceTo: pos) <= dist ] ]
]

Day20Solver >> solveWithJumpSize: jumpSize [
	| cheatValues jumpStarts |
	jumpStarts := (1 to: height) flatCollect: [ :r | (1 to: width) collect: [ :c | r @ c ] ].
	jumpStarts := jumpStarts select: [ :pos | self canMove: pos ].
	cheatValues := jumpStarts flatCollect: [ :jumpStart |
		               (self neighborsOf: jumpStart distance: jumpSize) collect: [ :jumpEnd |
				               (endDistance at: jumpStart)
				               - (endDistance at: jumpEnd)
				               - (jumpStart manhattanDistanceTo: jumpEnd) ] ].
	^ cheatValues count: [ :cheatVal | cheatVal >= goal ]
]

Day20Solver >> solvePart1 [
	^ self solveWithJumpSize: 2
]

Day20Solver >> solvePart2 [
	^ self solveWithJumpSize: 20
]

/* Advent of Code 2024
 * Day 20: Race Condition
 */

#import "Basic";
#import "File";
#import "Flat_Pool";
#import "Hash";
#import "Hash_Table";
#import "Math";
#import "String";

Vector2_Int :: struct {
    x, y: int;
}

Node :: struct {
    cost: int;
    position: Vector2_Int;
}

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    #procedure_of_call(operator ==(Vector2_Int.{}, Vector2_Int.{}))
);

operator == :: (a: Vector2_Int, b: Vector2_Int) -> bool {
    return a.x == b.x && a.y == b.y;
}

// Traverse the whole track and fill a (flattened two-dimensional) array with
// the distances from a given start position to every other position.
fill_distances_array :: (
    track: [][..] bool,
    width: int,
    start: Vector2_Int,
    distances: [] int
) {
    queue: [..] *Node;
    defer array_free(queue);

    start_node := New(Node);
    start_node.position = start;
    array_add(*queue, start_node);

    seen: Vector2_Int_Set;
    table_add(*seen, start, #run {});
    defer deinit(*seen);

    while queue.count {
        current := queue[0];
        array_ordered_remove_by_index(*queue, 0);

        index := current.position.y * width + current.position.x;
        if distances[index] == 0 {
            distances[index] = current.cost;
        }

        for Vector2_Int.[
            .{current.position.x - 1, current.position.y},
            .{current.position.x + 1, current.position.y},
            .{current.position.x, current.position.y - 1},
            .{current.position.x, current.position.y + 1}
        ] {
            if !track[it.y][it.x] && !table_contains(*seen, it) {
                new_node := New(Node);
                new_node.cost = current.cost + 1;
                new_node.position = it;

                array_add(*queue, new_node);
                table_add(*seen, it, #run {});
            }
        }
    }
}

find_efficient_cheats :: (
    track: [][..] bool,
    width: int,
    height: int,
    fastest_time: int,
    distances_from_start: [] int,
    distances_to_end: [] int,
    cheat_distance: int
) -> int {
    efficient_cheats := 0;
    for x1: 1..width - 2 {
        for y1: 1..height - 2 {
            for x2: x1 - cheat_distance..x1 + cheat_distance {
                for y2: y1 - cheat_distance..y1 + cheat_distance {
                    if
                        x2 <= 0 || x2 >= width - 1
                        || y2 <= 0 || y2 >= height - 1
                    {
                        continue;
                    }

                    distance := abs(x2 - x1) + abs(y2 - y1);
                    if
                        distance <= cheat_distance
                        && !track[y1][x1] && !track[y2][x2]
                        && fastest_time - (
                            distances_from_start[y1 * width + x1]
                            + distance
                            + distances_to_end[y2 * width + x2]
                        ) >= 100
                    {
                        efficient_cheats += 1;
                    }
                }
            }
        }
    }

    return efficient_cheats;
}

main :: () {
    input, success := read_entire_file("inputs/day_20.txt");
    assert(success);

    lines := split(input, "\n");
    defer array_free(lines);

    track: [..][..] bool;
    defer {
        for track {
            array_free(it);
        }

        array_free(track);
    }

    start, end: Vector2_Int;

    for line, y: lines {
        if line == "" {
            continue;
        }

        row: [..] bool;
        for char, x: line {
            array_add(*row, char == #char "#");

            if char == #char "S" {
                start = .{x, y};
            } else if char == #char "E" {
                end = .{x, y};
            }
        }

        array_add(*track, row);
    }

    width := track[0].count;
    height := track.count;

    distances_size := width * height;
    distances_from_start := NewArray(distances_size, int);
    distances_to_end := NewArray(distances_size, int);
    defer array_free(distances_from_start);
    defer array_free(distances_to_end);

    // Yet again, it's faster to use a pool when we're doing a bunch of graph
    // traversal (though the performance gain in this case is probably
    // negligable, since we're only running BFS twice).
    pool: Flat_Pool;
    defer reset(*pool);

    new_context := context;
    new_context.allocator.proc = flat_pool_allocator_proc;
    new_context.allocator.data = *pool;

    push_context new_context {
        fill_distances_array(track, width, start, distances_from_start);
        fill_distances_array(track, width, end, distances_to_end);
    }

    fastest_time := distances_to_end[start.y * width + start.x];
    print(
        "Part 1: %\nPart 2: %\n",
        find_efficient_cheats(
            track,
            width,
            height,
            fastest_time,
            distances_from_start,
            distances_to_end,
            2
        ),
        find_efficient_cheats(
            track,
            width,
            height,
            fastest_time,
            distances_from_start,
            distances_to_end,
            20
        )
    );
}