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