Advent of Code - 2024 - Day 12

var input = await File.ReadAllLinesAsync("input.txt");

var gridSize = input.Length;
var grid = new Node[gridSize, gridSize];
var regions = new List<(char Value, HashSet<Node> Nodes)>();

for (var row = 0; row < gridSize; row++)
{
    for (var col = 0; col < gridSize; col++)
    {
        grid[row, col] = new Node(input[row][col], new Position(row, col), []);
    }
}

for (var row = 0; row < gridSize; row++)
{
    for (var col = 0; col < gridSize; col++)
    {
        //Populate all neighbors, including those that are out of bounds.
        AddNeighbor(row - 1, col); //Up
        AddNeighbor(row + 1, col); //Down
        AddNeighbor(row, col - 1); //Left
        AddNeighbor(row, col + 1); //Right

        continue;

        void AddNeighbor(int r, int c)
        {
            var position = new Position(r, c);
            var neighbor = position.OutOfBounds(gridSize) ? new Node('#', position, []) : grid[r, c];

            grid[row, col].Neighbors.Add(neighbor);
            neighbor.Neighbors.Add(grid[row, col]);
        }
    }
}

for (var row = 0; row < gridSize; row++)
{
    for (var col = 0; col < gridSize; col++)
    {
        var node = grid[row, col];
        var region = regions.FirstOrDefault(r => r.Nodes.Contains(node));

        if (region == default)
        {
            //Node does not belong to any region, so we create a new one and do a simple BFS flood fill.
            region = (node.Value, [node]);

            var queue = new Queue<Node>();
            queue.Enqueue(node);

            while (queue.Count > 0)
            {
                var current = queue.Dequeue();
                foreach (var neighbor in current.Neighbors.Where(n => n.Value == region.Value))
                {
                    if (region.Nodes.Add(neighbor))
                    {
                        queue.Enqueue(neighbor);
                    }
                }
            }

            regions.Add(region);
        }
    }
}

var part1 = 0;
var part2 = 0;

foreach (var region in regions)
{
    //We will store the collection of nodes outside the region and the direction from the region to the node.
    //Every node in this list can represent a fence, so the perimeter (number of fences) is the number of nodes.
    //We will use the direction in order to walk alongside the perimeter and count the sides.
    var outerPerimeter = new List<(Node Node, Direction Direction)>();

    foreach (var node in region.Nodes)
    {
        outerPerimeter.AddRange(node.Neighbors.Where(n => n.Value != region.Value)
            .Select(neighbor => (node, node.Position.DirectionTo(neighbor.Position))));
    }

    var area = region.Nodes.Count;
    part1 += area * outerPerimeter.Count;

    var sides = 0;

    while (outerPerimeter.Count > 0)
    {
        //Walk the current section of the outer perimeter in both directions until we reach a corner.
        //The visited nodes represent a single side of the polygon.
        //We remove the visited nodes from the outer perimeter list and increase the sides counter.

        var (node, direction) = outerPerimeter[0];
        outerPerimeter.RemoveAt(0);

        WalkSide(direction.TurnLeft());
        WalkSide(direction.TurnRight());

        sides++;

        continue;

        void WalkSide(Direction dir)
        {
            var next = node.Position.Move(dir);
            var nextNode = outerPerimeter.FirstOrDefault(n => n.Node.Position == next && n.Direction == direction);
            while (nextNode != default)
            {
                outerPerimeter.Remove(nextNode);
                next = next.Move(dir);
                nextNode = outerPerimeter.FirstOrDefault(n => n.Node.Position == next && n.Direction == direction);
            }
        }
    }

    part2 += area * sides;
}


Console.WriteLine($"Part 1: {part1}");
Console.WriteLine($"Part 2: {part2}");

internal record Node(char Value, Position Position, HashSet<Node> Neighbors);

internal record Direction(int Row, int Col)
{
    public Direction TurnLeft()
    {
        return new Direction(-Col, Row);
    }

    public Direction TurnRight()
    {
        return new Direction(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)
    {
        return new Position(Row + dir.Row, Col + dir.Col);
    }

    public Direction DirectionTo(Position other)
    {
        return new Direction(other.Row - Row, other.Col - Col);
    }

    public bool OutOfBounds(int size)
    {
        return OutOfBounds(0, size);
    }

    public bool OutOfBounds(int start, int end)
    {
        return Row < start || Row >= end || Col < start || Col >= end;
    }
}