Day 18: RAM Run

Class {
	#name : 'Day18Solver',
	#superclass : 'AoCSolver',
	#instVars : [ 'gridSize', 'bytes', 'part1Size' ],
	#category : 'AoCDay18',
	#package : 'AoCDay18'
}

Day18Solver >> parseRawData [
	| coords |
	bytes := rawData lines collect: [ :line |
		         coords := (line splitOn: $,) collect: #asInteger.
		         coords first @ coords second ]
]

Day18Solver >> pathLengthWithFallen: fallenCount [
	| steps queue currPos fallen |
	fallen := (bytes first: fallenCount) asSet.
	steps := Dictionary newFromPairs: { 0 @ 0 . 0 }.
	queue := { 0 @ 0 } asOrderedCollection.
	[ queue isNotEmpty ] whileTrue: [
		currPos := queue removeFirst.
		currPos fourNeighbors
			select: [ :neighbor | self validPosition: neighbor withFallen: fallen ]
			thenDo: [ :neighbor |
				(steps includesKey: neighbor) ifFalse: [
					steps at: neighbor put: (steps at: currPos) + 1.
					queue add: neighbor ] ] ].
	^ steps at: gridSize @ gridSize ifAbsent: 0
]

Day18Solver >> solvePart1 [
	^ self pathLengthWithFallen: part1Size
]

Day18Solver >> solvePart2 [
	| lower upper mid |
	lower := part1Size.
	upper := bytes size.
	[ lower < upper ] whileTrue: [
		mid := upper + lower // 2.
		(self pathLengthWithFallen: mid) = 0
			ifTrue: [ upper := mid - 1 ]
			ifFalse: [ lower := mid + 1 ] ].
	^ bytes at: lower
]

Day18Solver >> validPosition: pos withFallen: fallen [
	^ (pos between: 0 @ 0 and: gridSize @ gridSize) & (fallen includes: pos) not
]

/* Advent of Code 2024
 * Day 18: RAM Run
 */

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

// These need to be configurable to make using the sample input easy.
GRID_SIZE :: 71;
PART_1_BYTES :: 1024;

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

Node :: struct {
    parent: *Node;
    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;
}

solve_grid :: (grid: [GRID_SIZE][GRID_SIZE] bool) -> int {
    queue: [..] *Node;
    array_add(*queue, New(Node));
    defer array_free(queue);

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

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

        if current.position == .{GRID_SIZE - 1, GRID_SIZE - 1} {
            path_length := 0;
            while current != null {
                path_length += 1;
                current = current.parent;
            }

            return path_length - 1;
        }

        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
                it.x >= 0 && it.x < GRID_SIZE && it.y >= 0 && it.y < GRID_SIZE
                && !grid[it.y][it.x]
                && !table_contains(*seen, it)
            {
                new_node := New(Node);
                new_node.parent = current;
                new_node.position = it;

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

    return -1;
}

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

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

    grid: [GRID_SIZE][GRID_SIZE] bool;
    dropped_bytes := 0;

    for lines {
        position := split(it, ",");
        defer array_free(position);

        grid[string_to_int(position[1])][string_to_int(position[0])] = true;

        dropped_bytes += 1;
        if (dropped_bytes == PART_1_BYTES) {
            break;
        }
    }

    // Using a pool saves us time doing memory allocations in the solving
    // procedure. It's not a huge performance gain, but it's just about
    // noticeable.
    pool: Flat_Pool;
    defer reset(*pool);

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

    print("Part 1: %\n", solve_grid(grid));

    for dropped_bytes..lines.count - 2 {
        position := split(lines[it], ",");
        defer array_free(position);

        grid[string_to_int(position[1])][string_to_int(position[0])] = true;

        if solve_grid(grid) == -1 {
            print("Part 2: %\n", lines[it]);
            break;
        } else {
            // We'll run out of memory if we don't do this. With a smaller input
            // this might not be required, but for the size we're given the
            // program will crash if we don't do it.
            reset(*pool);
        }
    }
}

A straightforward Breadth-First Search to find the path.

pub fn part1(input: &PuzzleInput) -> String {
    let mut memory = Grid2D::new(input.width, input.height, '.');

    // Mark the fallen bytes
    for c in input.bytes.iter().take(input.to_simulate) {
        memory.set(*c, '#');
    }

    // And find the shortest path to the bottom right using Breadth-First Search
    let mut q = VecDeque::new();
    q.push_back((Coordinate::new(0, 0), 0));

    while let Some((c, cost)) = q.pop_front() {
        if c == Coordinate::new(input.width as i32 - 1, input.height as i32 - 1) {
            return cost.to_string();
        }

        for nc in c.neighbors() {
            if memory.get(nc) == Some(&'.') {
                memory.set(nc, 'o');
                q.push_back((nc, cost + 1));
            }
        }
    }

    unreachable!()
}

That's where the trap hit. I tried to compute the set of all valid paths as a Dijkstra-Map, and then tried to repair it when an obstacle appears. I'm sure this is possible somehow (there are decremental-connectivity data structures, after all), but it is entirely unnecessary for this problem. You just A* repeatedly whenever a new obstacle falls onto the previous best path...

pub fn part2(input: &PuzzleInput) -> String {
    let mut memory = Grid2D::new(input.width, input.height, false);
    let mut path: Option<HashSet<Coordinate>> = None;

    // Simulate the falling bytes
    for byte_coord in input.bytes.iter() {
        // If the byte falls on our exit, we're trapped!
        if byte_coord.x == input.width as i32 - 1 && byte_coord.y == input.height as i32 - 1 {
            return format!("{},{}", byte_coord.x, byte_coord.y);
        }

        // Mark the byte as fallen
        memory.set(*byte_coord, true);

        // If we don't have a valid path (either because this is the first invocation, or because a byte fell onto our path),
        // find the shortest path to the bottom right using A*
        if path.is_none() || path.clone().unwrap().contains(byte_coord) {
            let start = Coordinate::new(0, 0);
            let end = Coordinate::new(input.width as i32 - 1, input.height as i32 - 1);
            let mut visited = memory.map(|_| false);

            // This is a bit ugly, but it appeases the borrow checker
            let m2 = memory.clone();

            // Define the successors function that returns the valid neighbors of the current coordinate
            let successors = move |c: &Coordinate| {
                if *c == end {
                    return vec![];
                }

                let neighbors = c
                    .neighbors()
                    .filter(|n| m2.get(*n).is_some())
                    .filter(|n| *m2.get(*n).unwrap() == false)
                    .filter(|n| *visited.get(*n).unwrap() == false)
                    .map(|n| (n, 1))
                    .collect_vec();

                // Mark the neighbors as visited
                neighbors.iter().for_each(|n| {
                    visited.set(n.0, true);
                });

                neighbors
            };

            // And then just A* and convert the path into a set of coordinates
            path = astar(
                &start,
                successors,
                |c| *c == end,
                |c| c.manhattan_distance(end),
            )
            .map(|(path, cost)| path.iter().cloned().collect::<HashSet<_>>());
        }

        // If we don't have a valid path, the last byte that fell is our puzzle answer.
        if path.is_none() {
            return format!("{},{}", byte_coord.x, byte_coord.y);
        }
    }

    unreachable!()
}

The astar function is from my AoC helper library, but you could just as well use a different implementation (e.g. the pathfinding crate's).

pub fn part2(input: &PuzzleInput) -> String {
    // This solution uses UnionFind again. I thought of trying this myself, but
    // concluded that it wouldn't work -- and it doesn't in the forward
    // direction. But I later found out on Reddit that you can just reverse
    // everything, and it works marvelously.

    // Step 1: Find all obstacle coordinates and make a map
    let mut grid = Grid2D::new(input.width, input.height, '.');

    for b in input.bytes.iter() {
        grid.set(*b, '#');
    }

    // Step 2: Prepare the UnionFind datastructure
    let mut union_find = UnionFind::default();
    let mut sets = grid.map(|_| 0);

    for (c, _) in grid.iter() {
        sets[c] = union_find.make_set();
    }

    // Step 3: Union all coordinates that never have obstacles
    for (c, _) in grid.iter() {
        if grid.get(c) != Some(&'.') {
            continue;
        }

        for dir in [Direction::Right, Direction::Down] {
            let n = c.neighbor(dir);

            if grid.get(n) == Some(&'.') {
                union_find.union(sets[c], sets[n]).unwrap();
            }
        }
    }

    // Step 4: Iterate over the obstacles in reverse, and union the coordinates.
    // This is the non-obvious part. Instead of adding obstacles one by one,
    // we start with all obstacles and then remove them one by one, unioning
    // the free space.
    let start = Coordinate::new(0, 0);
    let end = Coordinate::new(input.width as i32 - 1, input.height as i32 - 1);

    for b in input.bytes.iter().rev() {
        grid.set(*b, '.');

        for n in b.neighbors() {
            if grid.get(n) == Some(&'.') {
                union_find.union(sets[*b], sets[n]).unwrap();
            }
        }

        // Step 5: If the start and end coordinates are connected, the last
        // obstacle we removed must have been the one blocking the path.
        if union_find.find(sets[start]) == union_find.find(sets[end]) {
            return format!("{},{}", b.x, b.y);
        }
    }

    unreachable!()
}

This runs about twice as fast on my machine as using a binary search, 150µs vs. ~300µs.