AoC12
unknown
csharp
4 years ago
4.8 kB
6
Indexable
class AoC12 : AdventOfCode { readonly Dictionary<string, Location> _locations = new Dictionary<string, Location>(); readonly List<Location> _allLocations = new List<Location>(); Location _start; public override void Start() { _start = BuildCaveMap(); } public override void Run1() { Run(false); } public override void Run2() { Run(true); } public void Run(bool allowDouble) { LocationMapper mapper = new LocationMapper(allowDouble); var pathes = mapper.Map(_start); for (int i = 0; i < pathes.Count; i++) { var path = pathes[i]; string pathStr = ""; for (int j = 0; j < path.Count; j++) { pathStr += path[j].Name; if (j < path.Count - 1) pathStr += ","; } WriteLine(pathStr); } 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); } for (int i = 0; i < _allLocations.Count; i++) _allLocations[i].Connection.Sort(); return _locations["start"]; } Location GetCave(string name) { if (!_locations.TryGetValue(name, out var loc)) { loc = new Location(name); _allLocations.Add(loc); _locations[name] = loc; } return loc; } class Location : IComparable<Location> { public Location(string name) { Name = name; IsLarge = char.IsUpper(name[0]); IsEnd = name == "end"; IsStart = name == "start"; } public readonly string Name; public readonly List<Location> Connection = new List<Location>(); public readonly bool IsLarge; public readonly bool IsEnd; public readonly bool IsStart; public override int GetHashCode()=> Name.GetHashCode(); public override string ToString() => Name; public int Length => Connection.Count; public Location this[int key] => Connection[key]; public int CompareTo(Location other) { if (ReferenceEquals(this, other)) return 0; if (ReferenceEquals(null, other)) return 1; return string.Compare(Name, other.Name, StringComparison.Ordinal); } } 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) { 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); } } }
Editor is loading...