AoC12 Perf

mail@pastecode.io avatar
unknown
csharp
3 years ago
2.7 kB
3
Indexable
Never
class AoC12 : AdventOfCode
{
    Cave _start;
    public override void Start() { _start = BuildCaveMap(); }
    public override void Run1() { }
    public override void Run2() { Run(); }
    void Run()
    {
        var sw = Stopwatch.StartNew();
        SpecialCaveMapper mapper = new SpecialCaveMapper();
        int pathCount = mapper.Map(_start);
        sw.Stop();
        WriteLine($"Number of path found:{pathCount} in {sw.Elapsed.TotalMilliseconds}ms");
    }
    Cave BuildCaveMap()
    {
        Dictionary<string, Cave> locations = new Dictionary<string, Cave>();
        for (int i = 0; i < inputFile.Length; i++)
        {
            var caves = inputFile[i].Split('-');
            if (!locations.TryGetValue(caves[0], out var c1))
                locations[caves[0]] = c1 = new Cave(caves[0]);
            if (!locations.TryGetValue(caves[1], out var c2))
                locations[caves[1]] = c2 = new Cave(caves[1]);
            if(!c2.IsStart) c1.Add(c2);
            if (!c1.IsStart) c2.Add(c1);
        }
        return locations["start"];
    }
    class Cave
    {
        public Cave(string name)
        {
            IsLarge = char.IsUpper(name[0]);
            IsEnd = name == "end";
            IsStart = name == "start";
        }
        public readonly bool IsLarge;
        public readonly bool IsEnd;
        public readonly bool IsStart;

        Cave[] _connection = new Cave[0];
        public void Add(Cave c)
        {
            Array.Resize(ref _connection, _connection.Length + 1);
            _connection[_connection.Length - 1] = c;
        }
        public int Length => _connection.Length;
        public Cave this[int key] => _connection[key];

        public int VisitCount;
    }
    class SpecialCaveMapper
    {
        int _pathFound;
        public int Map(in Cave start)
        {
            _pathFound = 0;
            Expand(start);
            return _pathFound;
        }
        Cave _doubleNode;
        bool TryExpand(in Cave node)
        {
            if (node.IsEnd)
            {
                ++_pathFound;
                return false;
            }
            if (node.IsLarge || node.VisitCount == 0)
                return true;
            if (_doubleNode != null) 
                return false;
            _doubleNode = node;
            return true;
        }
        void Expand(Cave node)
        {
            ++node.VisitCount;
            for (int i = 0; i < node.Length; i++)
                if (TryExpand(node[i]))
                    Expand(node[i]);
            --node.VisitCount;
            if (node == _doubleNode)
                _doubleNode = null;
        }
    }
}