AdventOfCode23/Day23/Map.cs

namespace Day23;

public class Map
{
    private readonly int _width;
    private readonly int _height;
    private readonly Tile[,] _tiles;
    private readonly Vec _start;
    private readonly Vec _goal;
    private PathNode? _root;

    public Map(Tile[,] tiles)
    {
        _tiles = tiles;
        _width = _tiles.GetLength(0);
        _height = _tiles.GetLength(1);

        _start = new Vec(1, 0);
        _goal = new Vec(_width - 2, _height - 1);
    }

    public void Print()
    {
        foreach (var t in AllTiles())
        {
            if (t.Position.X == 0 && t.Position.Y != 0)
            {
                Console.WriteLine();
            }
            
            Console.Write(t.Value);
        }

        Console.WriteLine();
    }

    public void Verify()
    {
        Assert(At(_start)?.IsPath ?? false);
        Assert(At(_goal)?.IsPath ?? false);
        
        foreach (var t in AllTiles())
        {
            if (t.IsPath)
            {
                var neighbors = Neighbors(t);
                Assert(neighbors.Count != 0);
                if (neighbors.Count == 1)
                {
                    Assert(t == At(_start) || t == At(_goal));
                }
                else if (neighbors.Count >= 3)
                {
                    Assert(neighbors.All(n => n.IsArrow));
                }
            }
        }
    }

    public void BuildGraph()
    {
        var startTile = At(_start)!;
        _root = BuildPath(startTile, Neighbors(startTile).Single().Position.Subtract(startTile.Position));

        // Assert that we have no cycles in the graph
        var seen = new HashSet<PathNode>();
        foreach (var n in BreadthFirst())
        {
            if (seen.Contains(n))
            {
                throw new Exception("There is a cycle in the graph");
            }

            seen.Add(n);
        }
    }
    
    public int LongestPath()
    {
        Assert(_root != null);

        var longest = 0;
        var queue = new Queue<(PathNode Path, int Length)>();
        queue.Enqueue((_root!, 0));
        while (queue.Count > 0)
        {
            var (current, length) = queue.Dequeue();
            var nextLength = length + current.Tiles.Count + 1;

            if (current.Connected.Count == 0)
            {
                longest = int.Max(longest, nextLength);
            }

            foreach (var next in current.Connected)
            {
                queue.Enqueue((next, nextLength));
            }
        }

        // start should not be counted (-1) and end is counted double (-1) 
        return longest - 2;
    }

    private PathNode BuildPath(Tile start, Vec dir)
    {
        var pathNode = new PathNode();
        pathNode.Tiles.AddRange(Follow(start, dir));

        var crossing = At(pathNode.Tiles.Last().Position.Add(pathNode.Tiles.Last().ArrowDirection()))!;
        crossing.Incoming.Add(pathNode);

        if (crossing != At(_goal))
        {
            foreach (var outgoing in Neighbors(crossing)
                         .Where(x => x.Position.Add(x.ArrowDirection()) != crossing.Position))
            {
                pathNode.Connected.Add(BuildPath(outgoing, outgoing.ArrowDirection()));
            }
        }

        return pathNode;
    }

    private Tile? At(Vec p)
    {
        if (p.X < 0 || p.X >= _width || p.Y < 0 || p.Y >= _height)
        {
            return null;
        }

        return _tiles[p.X, p.Y];
    }

    private IEnumerable<Tile> AllTiles()
    {
        for (int y = 0; y < _height; y++)
        {
            for (int x = 0; x < _width; x++)
            {
                yield return At(new Vec(x, y))!;
            }
        }
    }

    private void Assert(bool condition)
    {
        if (!condition)
        {
            throw new Exception("Assertion FAILED");
        }
    }

    private List<Tile> Neighbors(Tile tile)
    {
        return tile.Neighbors().Select(At).Where(x => x is { IsPath: true }).Cast<Tile>().ToList();
    }

    private IEnumerable<Tile> Follow(Tile start, Vec dir)
    {
        var visited = new HashSet<Vec>();
        visited.Add(start.Position);
        yield return start;

        var current = At(start.Position.Add(dir))!;
        while (!current.IsArrow && current != At(_goal))
        {
            visited.Add(current.Position);
            yield return current;
            current = Neighbors(current)
                .Single(x => !visited.Contains(x.Position));
        }

        yield return current;
    }

    private IEnumerable<PathNode> BreadthFirst()
    {
        Assert(_root != null);
        var queue = new Queue<PathNode>();
        queue.Enqueue(_root!);
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            yield return current;

            foreach (var next in current.Connected)
            {
                queue.Enqueue(next);
            }
        }
    }
}