AoC12 Perf
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; } } }