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)!;
        var map = new Dictionary<Vec, PathNode>();
        BuildEdge(startTile, Neighbors(startTile).Single().Position.Subtract(startTile.Position), map);
        _root = map[startTile.Position];
    }
    
    public int LongestPath()
    {
        Assert(_root != null);

        var longest = 0;
        var visited = new HashSet<PathNode>();
        var queue = new Queue<(PathNode Node, int Length)>();
        queue.Enqueue((_root!, 0));
        while (queue.Count > 0)
        {
            var (current, length) = queue.Dequeue();
            if (current.Outgoing.Count > 2)
            {
                throw new Exception("Graph only has T-junctions");
            }
            visited.Add(current);

            if (current.Outgoing.Count == 0)
            {
                longest = int.Max(longest, length);
            }

            foreach (var o in current.Outgoing)
            {
                if (!visited.Contains(o.End))
                {
                    queue.Enqueue((o.End, length + o.Tiles.Count + 1));
                }
            }
        }

        // start should not be counted (-1) and end is counted double (-1) 
        return longest - 2;
    }
    
    public int LongestPathIgnoreDirection()
    {
        Assert(_root != null);
        
        var longest = 0;
        var queue = new Queue<(PathNode Node, int Length, HashSet<PathNode> Visited)>();
        queue.Enqueue((_root!, 0, new HashSet<PathNode>()));
        while (queue.Count > 0)
        {
            var (current, length, visited) = queue.Dequeue();
            //Console.WriteLine(current.Id);
            if (current.Outgoing.Count > 2)
            {
                throw new Exception("Graph only has T-junctions");
            }

            var newVisited = new HashSet<PathNode>(visited) { current };

            if (current.Outgoing.Count == 0 && current != _root)
            {
                longest = int.Max(longest, length);
            }

            foreach (var o in current.Outgoing.Concat(current.Incoming.Select(x => x.Invert())))
            {
                if (!visited.Contains(o.End))
                {
                    queue.Enqueue((o.End, length + o.Tiles.Count + 1, newVisited));
                }
            }
        }

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

    private void BuildEdge(Tile start, Vec dir, IDictionary<Vec, PathNode> map)
    {
        var previous = At(start.Previous())!;
        map.TryAdd(previous.Position, new PathNode());
        var startNode = map[previous.Position];

        var tiles = Follow(start, dir).ToList();
        var next = At(tiles.Last().Next())!;
        map.TryAdd(next.Position, new PathNode());
        var endNode = map[next.Position];

        if (startNode.Outgoing.All(o => o.End != endNode))
        {
            var edge = new PathEdge(startNode, endNode, tiles);
            startNode.Outgoing.Add(edge);
            endNode.Incoming.Add(edge);

            if (next != At(_goal))
            {
                foreach (var outgoing in Neighbors(next)
                             .Where(x => x.Position.Add(x.ArrowDirection()) != next.Position))
                {
                    BuildEdge(outgoing, outgoing.ArrowDirection(), map);
                }
            }
        }
    }

    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;
    }
}