advent_of_code_2024/Level6/Level6Solver.cs

namespace AoC24;

using AoC24.Common;
using AoCLevelInputProvider;
using Parsing;
using Parsing.Data;
using Parsing.Schema;

public class LoopDetectionException : Exception
{
    public LoopDetectionException(string message) : base(message)
    {}
}

public class GuardRunner
{
    public IDataIndex<int> currentPosition;
    public IDataIndex<int> initialCurrentPosition;
    public int TraversedTiles;
    public IDictionary<int, Dictionary<int, List<Direction>>> traversalMap = new Dictionary<int, Dictionary<int, List<Direction>>>();
    public Direction currentDirection;
    public Direction initialDirection;
    public List<SearchResult<int>> obstacles;
    private DefaultTwoDimensionalManipulator<string> manipulator;
    private DefaultDataSetIndexer<string> indexer;
    private List<List<string>> dataSet;

    public GuardRunner(IDataIndex<int> startingPosition, string guardChar, List<SearchResult<int>> obstacles, List<List<string>> dataSet)
    {
        switch(guardChar)
        {
            case "^":
                this.currentDirection = Direction.Up;
                break;
            case ">":
                this.currentDirection = Direction.Right;
                break;
            case "v":
                this.currentDirection = Direction.Down;
                break;
            case "<":
                this.currentDirection = Direction.Left;
                break;
            default:
                throw new ArgumentException("Invalid directional parameter given");
        }

        this.initialDirection = currentDirection;
        this.currentPosition = startingPosition;
        this.initialCurrentPosition = startingPosition;
        this.obstacles = obstacles;
        this.manipulator = new DefaultTwoDimensionalManipulator<string>(dataSet);
        this.indexer = new DefaultDataSetIndexer<string>();
        this.dataSet = dataSet;
    }

    private void VisitTile(int x, int y, Direction d)
    {
        if(!this.traversalMap.ContainsKey(x))
        {
            this.traversalMap[x] = new Dictionary<int, List<Direction>>();
        }
        if(!this.traversalMap[x].ContainsKey(y))
        {
            this.traversalMap[x][y] = new List<Direction>();
        }
        this.traversalMap[x][y].Add(d);
        var dirStringList = new List<string>();
        foreach(var direction in this.traversalMap[x][y])
        {
            dirStringList.Add(direction.ToString());
        }
        //Console.WriteLine($"Check tile ({x},{y}): " + string.Join(",", dirStringList));
    }

    private Direction TurnRight(Direction d)
    {
        switch(d)
        {
            case Direction.Up:
                return Direction.Right;
            case Direction.Right:
                return Direction.Down;
            case Direction.Down:
                return Direction.Left;
            case Direction.Left:
                return Direction.Up;
            default:
                throw new InvalidOperationException("This default case should never be reached!");
        }
    }

    private bool AreEqual(DirectionalSearchResult<int> di1, DirectionalSearchResult<int> di2)
    {
        return di1.Direction == di2.Direction 
                && di1.DataIndex.GetIndices()[0] == di2.DataIndex.GetIndices()[0] 
                && di1.DataIndex.GetIndices()[1] == di2.DataIndex.GetIndices()[1];
    }

    public void Run()
    {
        TraversedTiles = 1;
        currentPosition = initialCurrentPosition;
        traversalMap = new Dictionary<int, Dictionary<int, List<Direction>>>();
        currentDirection = initialDirection;
        
        while(true)
        {
            var nextPosition = currentPosition;

            while(nextPosition == currentPosition)
            {
                var nextPositionCandidate = manipulator.Move(currentPosition, currentDirection);

                if(!manipulator.IsValidIndex(nextPositionCandidate))
                {
                    // we just went off the map
                    return;
                }
                // if we added an extra obstacle it will be at the beginning of the list
                if(this.obstacles[0].DataIndex.GetIndices()[0] == nextPositionCandidate.GetIndices()[0]
                   && this.obstacles[0].DataIndex.GetIndices()[1] == nextPositionCandidate.GetIndices()[1])
                {
                    currentDirection = TurnRight(currentDirection);
                }
                else if(indexer.Get(dataSet, nextPositionCandidate) == "#")
                {
                    currentDirection = TurnRight(currentDirection);
                }
                else
                {
                    nextPosition = nextPositionCandidate;
                }
            }

            // we just moved, take into account the tile we just moved on
            currentPosition = nextPosition;

            // if we have been here before we have entered a loop
            if(this.traversalMap.ContainsKey(currentPosition.GetIndices()[0])
                && this.traversalMap[currentPosition.GetIndices()[0]].ContainsKey(currentPosition.GetIndices()[1])
                && this.traversalMap[currentPosition.GetIndices()[0]][currentPosition.GetIndices()[1]].Contains(currentDirection))
            {
                throw new LoopDetectionException("");
            }

            VisitTile(currentPosition.GetIndices()[0], currentPosition.GetIndices()[1], currentDirection);
        }
    }
}

public class Level6Solver : FullTextLevelSolverBase
{
    public override int LevelNumber
    {
        get { return 6; }
    }

    protected override InputSchemaBuilder DefineInputSchema(InputSchemaBuilder schemaBuilder)
    {
        return schemaBuilder
                    .Repeat()
                        .Expect(InputType.Char)
                    .EndRepetition();
    }

    public override string SolveFirstStar()
    {
        var data = this.GetData()
                       .AsListRows<string>();

        var manipulator = DefaultTwoDimensionalManipulator.Create(data);
        var obstacles = manipulator.FindInSet("#");
        var possibleGuardCharacters = new List<string>() { ">", "<", "v", "^" };
        var obstacleList = manipulator.FindInSet("#");
        SearchResult<int> guard = null;
        foreach(var gchar in possibleGuardCharacters)
        {
            guard = manipulator.FindInSet(gchar).SingleOrDefault();
            if (guard != null)
            {
                break;
            }
        }
        var dataAccessor = new DefaultDataSetIndexer<string>();
        var guardChar = dataAccessor.Get(data, guard.DataIndex);

        var guardRunner = new GuardRunner(guard.DataIndex, guardChar, obstacleList, data);
        guardRunner.Run();

        var count = 1;
        foreach(var xCoord in guardRunner.traversalMap.Keys)
        {
            count += guardRunner.traversalMap[xCoord].Count;
        }

        return count.ToString();
    }

    public override string SolveSecondStar()
    {
        var data = this.GetData()
                       .AsListRows<string>();

        var manipulator = DefaultTwoDimensionalManipulator.Create(data);
        var possibleGuardCharacters = new List<string>() { ">", "<", "v", "^" };
        var obstacleList = manipulator.FindInSet("#");
        SearchResult<int> guard = null;
        foreach(var gchar in possibleGuardCharacters)
        {
            guard = manipulator.FindInSet(gchar).SingleOrDefault();
            if (guard != null)
            {
                break;
            }
        }
        var dataAccessor = new DefaultDataSetIndexer<string>();
        var guardChar = dataAccessor.Get(data, guard.DataIndex);

        // first determine regular taken path
        var guardRunner = new GuardRunner(guard.DataIndex, guardChar, obstacleList, data);
        guardRunner.Run();

        // now for each visited tile, place an obstacle there and see if we run into a loop
        int loopCount = 0;
        foreach(var xCoord in guardRunner.traversalMap.Keys)
        {
            foreach(var yCoord in guardRunner.traversalMap[xCoord].Keys)
            {
                //Console.WriteLine($"Trying obstacle at ({xCoord},{yCoord})");
                var newObstacleList = new List<SearchResult<int>>();
                newObstacleList.Add(new SearchResult<int>(new DefaultPositionalDataIndex(xCoord, yCoord)));
                newObstacleList.AddRange(obstacleList);
                var testRunner = new GuardRunner(guard.DataIndex, guardChar, newObstacleList, data);
                try
                {
                    testRunner.Run();
                }
                catch(LoopDetectionException)
                {
                    loopCount += 1;
                }
            }
        }

        return loopCount.ToString();
    }
}