Day 16: Reindeer Maze

/* Advent of Code 2024
 * Day 16: Reindeer Maze
 */

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

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

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

// This is used for the table of seen states. The direction isn't stored in Node
// because it is inferred from the parent's position, but we have to store it
// here.
Reindeer_State :: struct {
    position, direction: Vector2_Int;
}

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

array_free_2d :: (array: [..][..] $T) {
    for array {
        array_free(it);
    }

    array_free(array);
}

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

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

    map: [..][..] bool;
    defer array_free_2d(map);

    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(*map, row);
    }

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

    heap: Heap(*Node, (left: *Node, right: *Node) -> bool {
        return left.cost <= right.cost;
    });

    seen: Table(
        Reindeer_State,
        int,
        (state: Reindeer_State) -> u32 {
            return inline sdbm_hash(xx *state, size_of(Reindeer_State));
        },
        (a: Reindeer_State, b: Reindeer_State) -> bool {
            return a.position == b.position && a.direction == b.direction;
        }
    );

    defer heap_free(heap);
    defer deinit(*seen);

    start_node := New(Node);
    start_node.position = start;
    heap_add(*heap, start_node);
    table_set(*seen, .{start_node.position, .{1, 0}}, 0);

    minimum_cost := -1;

    best_paths: [..][..] Vector2_Int;
    defer array_free_2d(best_paths);

    while !heap_is_empty(heap) {
        current := heap_pop(*heap);

        if current.position == end {
            if minimum_cost == -1 {
                minimum_cost = current.cost;
                print("Part 1: %\n", minimum_cost);
            }

            if current.cost == minimum_cost {
                path: [..] Vector2_Int;
                while current != null {
                    array_insert_at(*path, current.position, 0);
                    current = current.parent;
                }

                array_add(*best_paths, path);
                continue;
            } else {
                // We're using Djikstra's algorithm, so we know there will be no
                // more best paths after this.
                break;
            }
        }

        for Vector2_Int.[.{-1, 0}, .{1, 0}, .{0, -1}, .{0, 1}] {
            last_direction: Vector2_Int;
            if current.parent == null {
                last_direction = .{1, 0};
            } else {
                last_direction = .{
                    current.position.x - current.parent.position.x,
                    current.position.y - current.parent.position.y
                };
            }

            backwards: bool;
            if      last_direction == .{-1, 0} backwards = (it == .{1, 0});
            else if last_direction == .{1, 0}  backwards = (it == .{-1, 0});
            else if last_direction == .{0, -1} backwards = (it == .{0, 1});
            else if last_direction == .{0, 1}  backwards = (it == .{0, -1});

            new_cost := (
                current.cost + ifx last_direction == it then 1 else 1001
            );

            new_position := Vector2_Int.{
                current.position.x + it.x,
                current.position.y + it.y
            };

            new_state := Reindeer_State.{new_position, last_direction};
            seen_cost, success := table_find(*seen, new_state);

            // No need for bounds checking; the map is completely surrounded by
            // walls.
            if
                !map[new_position.y][new_position.x]
                && !backwards
                && (!success || seen_cost >= new_cost)
            {
                new := New(Node);
                memcpy(new, current, size_of(Node));

                new.parent = current;
                new.cost = new_cost;
                new.position = new_position;

                heap_add(*heap, new);
                table_set(*seen, new_state, new_cost);
            }
        }
    }

    places_to_sit: 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.{}))
    );

    defer deinit(*places_to_sit);

    for best_paths {
        for it {
            if !table_contains(*places_to_sit, it) {
                table_add(*places_to_sit, it, #run {});
            }
        }
    }

    print("Part 2: %\n", places_to_sit.count);
}

// order_test is used to determine the order of the values in the queue. It
// should return whether the first passed value should be given higher priority
// than the second passed value.
Heap :: struct (
    Value_Type: Type,
    order_test: (Value_Type, Value_Type) -> bool
) {
    values: [..] Value_Type;
}

heap_add :: (heap: *Heap, value: heap.Value_Type) {
    array_add(*heap.values, value);

    current_index := heap.values.count - 1;
    while current_index > 0 {
        parent_index := (current_index - 1) / 2;

        current_value := heap.values[current_index];
        parent_value := heap.values[parent_index];

        if heap.order_test(parent_value, current_value) {
            break;
        }

        heap.values[current_index] = parent_value;
        heap.values[parent_index] = current_value;
        current_index = parent_index;
    }
}

heap_pop :: (heap: *Heap) -> heap.Value_Type {
    assert(!heap_is_empty(heap), "cannot pop from an empty heap");

    root_value := heap.values[0];
    heap.values[0] = pop(*heap.values);

    current_index := 0;
    while true {
        left_index := current_index * 2 + 1;
        right_index := left_index + 1;

        has_left := left_index < heap.values.count;
        has_right := right_index < heap.values.count;

        if !has_left && !has_right {
            break;
        }

        child_index: int;
        if !has_left {
            child_index = right_index;
        } else if !has_right {
            child_index = left_index;
        } else if heap.order_test(
            heap.values[left_index],
            heap.values[right_index]
        ) {
            child_index = left_index;
        } else {
            child_index = right_index;
        }

        current_value := heap.values[current_index];
        child_value := heap.values[child_index];

        if heap.order_test(current_value, child_value) {
            break;
        }

        heap.values[current_index] = child_value;
        heap.values[child_index] = current_value;
        current_index = child_index;
    }

    return root_value;
}

// These last two procedures don't require the heap be passed as a pointer,
// since they do not modify it.
heap_is_empty :: inline (heap: Heap) -> bool {
    return heap.values.count == 0;
}

heap_free :: inline (heap: Heap) {
    for heap.values {
        free(it);
    }

    array_free(heap.values);
}

#scope_file

#import "Basic";

This is a fairly basic application of A* search. In retrospect, there was nothing really difficult about this, but I still managed to break it in seven hundred different ways because I thought I could code pathfinding up from scratch by now, instead of using a library or even reference material. Ah, the programmer virtue of hubris strikes again.

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct State {
    pub position: Coordinate,
    pub direction: Direction,
    pub heuristic: usize,
    pub straight_steps: usize,
    pub number_of_turns: usize,
    pub waypoints: Vec<Coordinate>,
}

impl State {
    pub fn score(&self) -> usize {
        self.straight_steps + self.number_of_turns * 1000
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

// Ordering function for the priority queue -- we want to prioritize states with
// lower scores + heuristic values to get the A* algorithm. Since BinaryHeap is
// a max-heap, we invert the comparison.
impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        (other.score() + other.heuristic).cmp(&(self.score() + self.heuristic))
    }
}


// Follows a given straight path until it either hits a junction, the end, or a wall.
pub fn follow_path(
    cur: Coordinate,
    dir: Direction,
    grid: &Grid2D<char>,
    junctions: &HashSet<Coordinate>,
) -> (Coordinate, usize) {
    let mut cur = cur;
    let mut len = 1;

    loop {
        let next = cur + dir;

        if junctions.contains(&next) {
            return (next, len);
        }

        if grid.get(next) == Some(&'E') {
            return (next, len);
        }

        if grid.get(next) == Some(&'#') {
            return (cur, len - 1);
        }

        len += 1;
        cur = next;
    }
}

// Heuristic function for the A* algorithm.
//
// We need to take at least manhattan_distance(end) straight steps, but since the end
// is in the top-right corner, we need to turn at least once if we are currently looking
// leftwards or downwards.
fn heuristic(cur: Coordinate, dir: Direction, end: Coordinate) -> usize {
    let mut h = cur.manhattan_distance(end) as usize;

    if dir == Direction::Left {
        h += 1000;
    }

    if dir == Direction::Down {
        h += 1000;
    }

    h
}

// Runs the A* algorithm to find the shortest path from start to end.
pub fn search(input: &PuzzleInput) -> Vec<State> {
    let junctions = junctions(&input.maze);

    let start = input.maze.iter().find(|(_, &c)| c == 'S').unwrap().0;
    let end = input.maze.iter().find(|(_, &c)| c == 'E').unwrap().0;

    let mut q = BinaryHeap::new();
    let mut visited = BTreeMap::new();

    // Starting states
    q.push(State {
        position: start,
        direction: Direction::Right,
        straight_steps: 0,
        number_of_turns: 0,
        waypoints: vec![start],
        heuristic: heuristic(start, Direction::Right, end),
    });

    let mut best: Vec<State> = vec![];

    while let Some(state) = q.pop() {
        // Skip if we've already seen this state with a better score
        if let Some(prev_g) = visited.get(&(state.position, state.direction)) {
            if state.score() > *prev_g {
                continue;
            }
        }

        // Mark this state as visited
        visited.insert((state.position, state.direction), state.score());

        // If we've reached the end, add this state to the best list. We are guaranteed
        // to only add shortest paths to the best list because we are using a priority queue
        // and an admissible heuristic. Also, we break out of the loop below if we've found
        // all shortest paths, so we can't reach this point if we've already found all
        // shortest paths.
        if state.position == end {
            if best.len() == 0 || state.score() == best[0].score() {
                best.push(state.clone());
            }

            continue;
        }

        // Follow the current corridor until we hit a junction, the end, or a wall.
        let (next, len) = follow_path(state.position, state.direction, &input.maze, &junctions);

        // Did we hit a wall?
        let hit_a_wall = len == 0;

        // If we didn't hit a wall, this is a junction, and we can proceed forwards.
        if !hit_a_wall {
            // Update the list of waypoints
            let mut waypoints = state.waypoints.clone();
            waypoints.push(next);

            // Add the new state to the queue
            let fwd = State {
                position: next,
                straight_steps: state.straight_steps + len,
                heuristic: heuristic(next, state.direction, end),
                waypoints,
                ..state.clone()
            };

            q.push(fwd);
        }

        // If we are at a junction or corner, we can try to turn left or right.
        if junctions.contains(&state.position) || hit_a_wall {
            let left_dir = state.direction.turn_left_90();
            let right_dir = state.direction.turn_right_90();

            let left_coord = state.position.neighbor(left_dir);
            let right_coord = state.position.neighbor(right_dir);

            let left_free = input.maze.get(left_coord) == Some(&'.')
                || input.maze.get(left_coord) == Some(&'E');
            let right_free = input.maze.get(right_coord) == Some(&'.')
                || input.maze.get(right_coord) == Some(&'E');

            if left_free {
                let turn_left = State {
                    direction: left_dir,
                    number_of_turns: state.number_of_turns + 1,
                    ..state.clone()
                };

                q.push(turn_left);
            }

            if right_free {
                let turn_right = State {
                    direction: right_dir,
                    number_of_turns: state.number_of_turns + 1,
                    ..state.clone()
                };

                q.push(turn_right);
            }
        }

        // If the current state is worse than the best state we've found, we can stop early,
        // because we are guaranteed to have found all shortest paths (due to the properties
        // of A* and the admissable heuristic).
        if !best.is_empty() && state.score() > best[0].score() {
            break;
        }
    }

    best
}

// Finds all junctions in the maze.
pub fn junctions(maze: &Grid2D<char>) -> HashSet<Coordinate> {
    let mut junctions = HashSet::new();

    junctions.insert(maze.iter().find(|(_, &c)| c == 'S').unwrap().0);

    for (coord, &c) in maze.iter() {
        if c != '.' {
            continue;
        }

        let mut count = 0;
        for neighbors in coord.neighbors() {
            if maze.get(neighbors) == Some(&'.') {
                count += 1;
            }
        }

        if count > 2 {
            junctions.insert(coord);
        }
    }

    junctions
}

pub fn part1(input: &PuzzleInput) -> String {
    search(input)[0].score().to_string()
}

Part 2 was fairly easy, because all you have to do is wait until A* delivers you all shortest paths. By the properties of priority queues ordered by an adissable heuristic, you get all shortest paths before all longer paths. If your A* is subtly broken, though, you may need a long time to recover...

pub fn part2(input: &PuzzleInput) -> String {
    let best = search(input);
    covered(input, &best).to_string()
}

// Counts the number of positions covered by the best path by following the
// waypoints in the best paths.
fn covered(input: &PuzzleInput, best: &[State]) -> usize {
    let mut covered = input.maze.map(|_| false);

    for b in best.iter() {
        for path in b.waypoints.windows(2) {
            let towards = path[0].towards(path[1]);
            covered.set(path[0], true);

            for c in successors(Some(path[0]), |&c| Some(c.neighbor(towards))) {
                covered.set(c, true);
                if c == path[1] {
                    break;
                }
            }
        }
    }

    covered.iter().filter(|(_, &c)| c).count()
}

Pretty slow, because I have to lug around all those waypoints. :/

day_16    fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ part1  175.1 ms      │ 267.8 ms      │ 182.3 ms      │ 186.9 ms      │ 100     │ 100
╰─ part2  174.8 ms      │ 226.1 ms      │ 181.7 ms      │ 183.5 ms      │ 100     │ 100