AoC12 Perf

mail@pastecode.io avatar
unknown
csharp
2 years ago
2.9 kB
2
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();
        int pathCount = SpecialCaveMapper.CaveMap(_start);
        sw.Stop();
        WriteLine($"Number of path found:{pathCount} in {sw.Elapsed.TotalMilliseconds}ms");
    }
    Cave BuildCaveMap()
    {
        var caves = new Dictionary<string, Cave>();
        for (int i = 0; i < inputFile.Length; i++)
        {
            var caveNames = inputFile[i].Split('-');
            if (!caves.TryGetValue(caveNames[0], out var c1)) caves[caveNames[0]] = c1 = new Cave(caveNames[0]);
            if (!caves.TryGetValue(caveNames[1], out var c2)) caves[caveNames[1]] = c2 = new Cave(caveNames[1]);
            c1.Add(c2);
            c2.Add(c1);
        }
        return caves["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;
        public bool HasEnd;

        public int Length => _connection.Length;
        public Cave this[int key] => _connection[key];
        Cave[] _connection = new Cave[0];
        public void Add(Cave c)
        {
            if (c.IsStart) return;
            if (c.IsEnd)
            {
                HasEnd = true;
                return;
            }
            Array.Resize(ref _connection, _connection.Length + 1);
            _connection[_connection.Length - 1] = c;
        }
        public int VisitCount;
    }
    class SpecialCaveMapper
    {
        public static int CaveMap(Cave start) => new SpecialCaveMapper().Map(start);
        int _pathFound;
        int Map(Cave start)
        {
            _pathFound = 0;
            Expand(start);
            return _pathFound;
        }
        Cave _doubleCave;
        void Expand(Cave fromCave)
        {
            ++fromCave.VisitCount;
            for (int i = 0; i < fromCave.Length; ++i)
            {
                var nextCave = fromCave[i];
                if (nextCave.IsLarge || nextCave.VisitCount == 0)
                {
                    Expand(nextCave);
                    continue;
                }
                if (_doubleCave != null)
                    continue;
                _doubleCave = nextCave;
                Expand(nextCave);
            }
            if(fromCave.HasEnd)
                ++_pathFound;
            --fromCave.VisitCount;
            if (fromCave == _doubleCave)
                _doubleCave = null;
        }
    }
}