advent24/Advent24/Day6.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection.Emit;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using System.IO.Compression;
using System.Xml.Serialization;

namespace Advent24
{
    internal class Day6
    {
        private static Boolean simulateGuardPath(String map, ref HashSet<Int32> visited, Int32 newObstacleLinearPosition = -1)
        {
            // get width of line to be able to navigate the text block in
            // both dimensions
            Int32 mapWidth = map.IndexOf('\n');

            Int32 guardLinearPosition = 0;
            Int32 guardDirection = 0; //1 = up, 2 = right, 3 = down, 4 = left

            // counts the number of times we go forward in time without
            Int32 numberOfIterationsWithoutNewVisits = 0;

            Int32 previousNumberOfVisitedPositions = 0;

            Int32 numberOfDirectionChanges = 0;

            Boolean guardIsInMapBoundary = true;

            Boolean wasInfiniteLoop = false;

            // Find the initial position and direction of the guard
            guardLinearPosition = map.IndexOf('^');

            if (guardLinearPosition != -1) // in up direction
            {
                guardDirection = 1;
                // invalid new obstacle position, so return prematurely with
                // the assumption that it didn't lead to an infinite loop
                if (newObstacleLinearPosition == guardLinearPosition)
                    return false; // assumed value of wasInfiniteLoop
            }
            else // not in up direction
            {
                guardLinearPosition = map.IndexOf('>');
                if (guardLinearPosition != -1) // in right direction
                    guardDirection = 2;
                else // not in up or right direction
                {
                    guardLinearPosition = map.IndexOf('v');
                    if (guardLinearPosition != -1) // in down direction
                        guardDirection = 3;
                    else // not in up, right or down direction
                    {
                        guardLinearPosition = map.IndexOf('<');
                        if (guardLinearPosition != -1) // in left direction
                            guardDirection = 4;
                        else // guard not found
                        {
                            guardDirection = -1;
                            guardIsInMapBoundary = false;
                        }
                    }
                }
            }

            // add intiial guard linear position
            if (guardIsInMapBoundary) visited.Add(guardLinearPosition);

            while (guardIsInMapBoundary)
            {
                // check next position of guard

                // top
                if (guardDirection == 1)
                {
                    // if obstacle detected
                    if (guardLinearPosition - (mapWidth + 1) >= 0 &&
                        (
                            map[guardLinearPosition - (mapWidth + 1)] == '#' ||
                            guardLinearPosition - (mapWidth + 1) == newObstacleLinearPosition
                        ))
                    {
                        // turn 90 deg clockwise
                        guardDirection = 2;
                        numberOfDirectionChanges++;
                    }
                    // no obstacle detected
                    else
                        // go up one position
                        guardLinearPosition -= mapWidth + 1;
                }
                // right
                else if (guardDirection == 2)
                {
                    // if obstacle detected
                    if (guardLinearPosition + 1 < map.Length &&
                        (
                            map[guardLinearPosition + 1] == '#' ||
                            guardLinearPosition + 1 == newObstacleLinearPosition
                        ))
                    {
                        // turn 90 deg clockwise
                        guardDirection = 3;
                        numberOfDirectionChanges++;
                    }
                    // no obstacle detected
                    else
                        // go up one position
                        guardLinearPosition += 1;
                }
                // down
                else if (guardDirection == 3)
                {
                    // if obstacle detected
                    if (guardLinearPosition + (mapWidth + 1) < map.Length &&
                        (
                            map[guardLinearPosition + (mapWidth + 1)] == '#' ||
                            guardLinearPosition + (mapWidth + 1) == newObstacleLinearPosition
                        ))
                    {
                        // turn 90 deg clockwise
                        guardDirection = 4;
                        numberOfDirectionChanges++;
                    }
                    // no obstacle detected
                    else
                        // go up one position
                        guardLinearPosition += (mapWidth + 1);
                }
                // left
                else if (guardDirection == 4)
                {
                    // if obstacle detected
                    if (guardLinearPosition - 1 >= 0 &&
                        (
                            map[guardLinearPosition - 1] == '#' ||
                            guardLinearPosition - 1 == newObstacleLinearPosition
                        ))
                    {    
                        // turn 90 deg clockwise
                        guardDirection = 1;
                        numberOfDirectionChanges++;
                    }
                    // no obstacle detected
                    else
                        // go up one position
                        guardLinearPosition -= 1;
                }

                // right and left boundary check
                if (guardLinearPosition > map.Length ||
                    guardLinearPosition < 0 ||
                    map[guardLinearPosition] == '\n')
                    guardIsInMapBoundary = false;

                // top and bottom boundary check
                if (guardLinearPosition < 0 ||
                    guardLinearPosition >= map.Length)
                    guardIsInMapBoundary = false;

                // if boundary check passes, add position to visited
                if (guardIsInMapBoundary)
                {
                    previousNumberOfVisitedPositions = visited.Count;
                    visited.Add(guardLinearPosition);
                }

                // if there is no change in the number of visited positions
                if (previousNumberOfVisitedPositions == visited.Count)
                {
                    numberOfIterationsWithoutNewVisits++;

                    // we've followed the whole path again, of which a good approximation is
                    // that the number of unique visited positions plus the number of times
                    // the direction has changes is equal to the number of iterations without new
                    // visits - this will undercount intersections
                    if (numberOfIterationsWithoutNewVisits > (visited.Count + numberOfDirectionChanges))
                    {
                        // Console.WriteLine("  numberOfIterationsWithoutNewVisits = {0:d}", numberOfIterationsWithoutNewVisits);
                        wasInfiniteLoop = true;
                        break;
                    }
                }
            }

            return wasInfiniteLoop;
        }
        public Day6()
        {
            String fileData = System.IO.File.ReadAllText(@"..\..\..\inputd6.txt");

            
            // set of visited linearPositions
            HashSet<Int32> visited = [];

            simulateGuardPath(fileData, ref visited);

            Int32 numberOfDistinctPositions = visited.Count;

            Console.WriteLine("numberOfDistinctPositions = {0:d}", numberOfDistinctPositions);

            Int32 numberOfViableNewObstaclePositions = 0;

            Boolean wasInfiniteLoop;

            // a set of unchecked linearPositions
            HashSet<Int32> uncheckedLinearPositions = [.. visited];

            // a set of alreaedy-checked linearPositions
            HashSet<Int32> checkedLinearPositions = [];

            Int32 previousUncheckedLinearPositionsCount = uncheckedLinearPositions.Count;

            // while there are unchecked visited positions
            while (uncheckedLinearPositions.Count > 0)
            {
                // clear visited hashset for a fresh start per iteration
                visited.Clear();

                // get first non-checked linear position
                var firstNonCheckedLinearPosition = uncheckedLinearPositions.First();

                wasInfiniteLoop = simulateGuardPath(fileData, ref visited, firstNonCheckedLinearPosition);

                // if the guard is in a loop, we have a viable obstacle position
                if (wasInfiniteLoop)
                    numberOfViableNewObstaclePositions++;

                // update checkedLinearPositions
                checkedLinearPositions.Add(firstNonCheckedLinearPosition);

                // remove already-checked linear positions from visited
                // so it only has new positions to add to our uncheckedLinearPositions
                // This line isn't required because we're only adding one additional obstacle, which
                // will only affect the original path (which we're already checking)
                //visited.ExceptWith(checkedLinearPositions);

                previousUncheckedLinearPositionsCount = uncheckedLinearPositions.Count;

                // update uncheckedLinearPositions to remove firstNonCheckedLinearPosition
                // and add newly visisted linear positions
                uncheckedLinearPositions.Remove(firstNonCheckedLinearPosition);
                
                // This line isn't required because we're only adding one additional obstacle, which
                // will only affect the original path (which we're already checking)
                //uncheckedLinearPositions.UnionWith(visited);

             // if (uncheckedLinearPositions.Count > previousUncheckedLinearPositionsCount)
             //     Console.WriteLine("(change) uncheckedLinearPositions.Count = {0:d}", uncheckedLinearPositions.Count - previousUncheckedLinearPositionsCount);
            }

            Console.WriteLine("numberOfViableNewObstaclePositions = {0:d}", numberOfViableNewObstaclePositions);

            // to keep the console window from closing
            Console.ReadKey();
        }
    }
}