AoC12

class AoC12 : AdventOfCode
{
    readonly Dictionary<string, Location> _locations = new Dictionary<string, Location>();
    readonly List<Location> _allLocations = new List<Location>();
    Location _start;
    public override void Start() { _start = BuildCaveMap(); }
    public override void Run1() { Run(false); }
    public override void Run2() { Run(true); }
    public void Run(bool allowDouble)
    {
        LocationMapper mapper = new LocationMapper(allowDouble);
        var pathes = mapper.Map(_start);
        for (int i = 0; i < pathes.Count; i++)
        {
            var path = pathes[i];
            string pathStr = "";
            for (int j = 0; j < path.Count; j++)
            {
                pathStr += path[j].Name;
                if (j < path.Count - 1)
                    pathStr += ",";
            }
            WriteLine(pathStr);
        }
        WriteLine($"Number of path found:{pathes.Count}");
    }

    Location BuildCaveMap()
    {
        for (int i = 0; i < inputFile.Length; i++)
        {
            var caves = inputFile[i].Split('-');
            var c1 = GetCave(caves[0]);
            var c2 = GetCave(caves[1]);
            c1.Connection.Add(c2);
            c2.Connection.Add(c1);
        }

        for (int i = 0; i < _allLocations.Count; i++)
            _allLocations[i].Connection.Sort();

        return _locations["start"];
    }

    Location GetCave(string name)
    {
        if (!_locations.TryGetValue(name, out var loc))
        {
            loc = new Location(name);
            _allLocations.Add(loc);
            _locations[name] = loc;
        }
        return loc;
    }

    class Location : IComparable<Location>
    {
        public Location(string name)
        {
            Name = name;
            IsLarge = char.IsUpper(name[0]);
            IsEnd = name == "end";
            IsStart = name == "start";
        }
        public readonly string Name;
        public readonly List<Location> Connection = new List<Location>();
        public readonly bool IsLarge;
        public readonly bool IsEnd;
        public readonly bool IsStart;

        public override int GetHashCode()=> Name.GetHashCode();
        public override string ToString() => Name;

        public int Length => Connection.Count;
        public Location this[int key] => Connection[key];

        public int CompareTo(Location other)
        {
            if (ReferenceEquals(this, other)) return 0;
            if (ReferenceEquals(null, other)) return 1;
            return string.Compare(Name, other.Name, StringComparison.Ordinal);
        }
    }
    class LocationMapper
    {
        public LocationMapper(bool allowOnceDouble = false) => _allowOnceDouble = allowOnceDouble;
        readonly Stack<Location> _currentPath = new Stack<Location>();
        readonly List<List<Location>> _pathFound = new List<List<Location>>();
        readonly bool _allowOnceDouble;

        public List<List<Location>> Map(in Location start)
        {
            for (int i = 0; i < start.Length; i++)
                ExpandStart(start, i);

            return _pathFound;
        }

        void ExpandStart(in Location start, int index)
        {
            _currentPath.Clear();
            _currentPath.Push(start);
            Expand(start[index]);
        }

        Location _doubleNode;
        bool TryExpand(in Location node)
        {
            if (node.IsStart) 
                return false;
            if (node.IsEnd || node.IsLarge)
                return true;

            bool exists = _currentPath.Contains(node);
            if (!exists) return true;
            if (!_allowOnceDouble || _doubleNode != null)
                return false;
            
            _doubleNode = node;
            return true;
        }

        
        void Expand(Location node)
        {
            if (node.IsEnd)
            {
                AddPath(node);
                return;
            }
            _currentPath.Push(node);
            for (int i = 0; i < node.Length; i++)
                if (TryExpand(node[i]))
                    Expand(node[i]);
            _currentPath.Pop();
            if (node == _doubleNode)
                _doubleNode = null;
        }

        readonly Stack<Location> _reversePath = new Stack<Location>();
        void AddPath(Location end)
        {
            List<Location> path = new List<Location>();
            _reversePath.Clear();
            foreach (var l in _currentPath)
                _reversePath.Push(l);
            path.AddRange(_reversePath);
            path.Add(end);
            _pathFound.Add(path);
        }
    }
}