AoC12

class AoC12 : AdventOfCode
{
    readonly Dictionary<string, Location> _locations = new Dictionary<string, Location>();
    Location _start;
    public override void Start() { _start = BuildCaveMap(); }
    public override void Run1() { Run(false); }
    public override void Run2() { Run(true); }
    void Run(bool allowDouble)
    {
        LocationMapper mapper = new LocationMapper(allowDouble);
        var pathes = mapper.Map(_start);
        for (int i = 0; i < pathes.Count; i++)
            WriteLine(pathes[i].ToString(','));
        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);
        }

        foreach(var kvp in _locations)
            kvp.Value.Connection.Sort((l1, l2) => string.Compare(l1.Name, l2.Name, StringComparison.Ordinal));

        return _locations["start"];
    }

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

    class Location
    {
        public Location(string name)
        {
            Name = name;
            IsLarge = char.IsUpper(name[0]);
            IsEnd = name == "end";
            IsStart = name == "start";
        }
        public readonly string Name;
        public override string ToString() => Name;

        public readonly List<Location> Connection = new List<Location>();
        public readonly bool IsLarge;
        public readonly bool IsEnd;
        public readonly bool IsStart;
        
        public int Length => Connection.Count;
        public Location this[int key] => Connection[key];
    }
    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)
        {
            _pathFound.Clear();
            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);
        }
    }
}