Advent of Code - 2024 - Day 16

var timer = System.Diagnostics.Stopwatch.StartNew();
var input = await File.ReadAllLinesAsync("input.txt");

var start = new Position(-1, -1);
var end = new Position(-1, -1);

var gridSize = input.Length;
var grid = new bool[gridSize, gridSize];

for (var row = 0; row < gridSize; row++)
{
    for (var col = 0; col < gridSize; col++)
    {
        grid[row, col] = true;

        switch (input[row][col])
        {
            case 'S':
                start = new Position(row, col);
                break;
            case 'E':
                end = new Position(row, col);
                break;
            case '#':
                grid[row, col] = false;
                break;
        }
    }
}

var seen = new Dictionary<(Position Position, Direction direction), int>();
var queue = new PriorityQueue<(Position Position, Direction Direction, HashSet<Position> Moves), int>();
queue.Enqueue((start, Direction.Right, []), 0);

var shortestPaths = new HashSet<Position> { start };
var shortestPathLength = 0;

while (queue.TryDequeue(out var current, out var cost))
{
    var (position, direction, moves) = current;

    if (position == end)
    {
        if (shortestPathLength == 0)
        {
            Console.WriteLine($"Part 1: {cost}");
            shortestPathLength = cost;
        }

        if (cost > shortestPathLength)
        {
            break;
        }

        shortestPaths.UnionWith(moves);
    }

    if (seen.GetValueOrDefault((position, direction), int.MaxValue) < cost)
    {
        continue;
    }

    seen[(position, direction)] = cost;

    var next = position.Move(direction);
    if (grid[next.Row, next.Col])
    {
        var nextMoves = new HashSet<Position>(moves) { next };
        queue.Enqueue((next, direction, nextMoves), cost + 1);
    }

    var left = direction.TurnLeft();
    next = position.Move(left);
    if (grid[next.Row, next.Col])
    {
        var nextMoves = new HashSet<Position>(moves) { next };
        queue.Enqueue((next, left, nextMoves), cost + 1001);
    }

    var right = direction.TurnRight();
    next = position.Move(right);
    if (grid[next.Row, next.Col])
    {
        var nextMoves = new HashSet<Position>(moves) { next };
        queue.Enqueue((next, right, nextMoves), cost + 1001);
    }
}

Console.WriteLine($"Part 2: {shortestPaths.Count}");
Console.WriteLine($"{timer.ElapsedMilliseconds}ms");

internal record Direction(int Row, int Col)
{
    public Direction TurnLeft() => new(-Col, Row);

    public Direction TurnRight() => new(Col, -Row);

    public static readonly Direction Up = new(-1, 0);
    public static readonly Direction Down = new(1, 0);
    public static readonly Direction Left = new(0, -1);
    public static readonly Direction Right = new(0, 1);
}

internal record Position(int Row, int Col)
{
    public Position Move(Direction dir) => new(Row + dir.Row, Col + dir.Col);
}