91 lines
3.0 KiB
C#
91 lines
3.0 KiB
C#
// #define Day12
|
|
#if Day12
|
|
using System.Collections.Immutable;
|
|
using AoC2021;
|
|
const string START = "start";
|
|
const string END = "end";
|
|
var paths = new Dictionary<string, ImmutableHashSet<string>>();
|
|
|
|
File.ReadAllLines("day12/input")
|
|
.Select(l => l.Split("-"))
|
|
.ForEachAsList(x => {
|
|
if (x[0] != END && x[1] != START) {
|
|
if (paths.ContainsKey(x[0])) {
|
|
paths[x[0]] = paths[x[0]].Add(x[1]);
|
|
} else {
|
|
paths.Add(x[0], ImmutableHashSet.Create(x[1]));
|
|
}
|
|
}
|
|
|
|
if (x[1] != END && x[0] != START) {
|
|
if (paths.ContainsKey(x[1])) {
|
|
paths[x[1]] = paths[x[1]].Add(x[0]);
|
|
} else {
|
|
paths.Add(x[1], ImmutableHashSet.Create(x[0]));
|
|
}
|
|
}
|
|
});
|
|
|
|
Console.WriteLine(PathCountPart1(paths, ImmutableHashSet.Create(START), START));
|
|
Console.WriteLine(PathCountPart2(paths, ImmutableHashSet.Create(START), START, false));
|
|
|
|
long PathCountPart1(Dictionary<string, ImmutableHashSet<string>> paths, ImmutableHashSet<string> visitedSmallCaves, string current) {
|
|
long count = paths[current].Contains(END) ? 1 : 0;
|
|
ImmutableHashSet<string> adjacent;
|
|
adjacent = paths[current].Except(visitedSmallCaves).Remove(END);
|
|
foreach (var a in adjacent) {
|
|
if (a.ToLower() == a) {
|
|
count += PathCountPart1(paths, visitedSmallCaves.Add(a), a);
|
|
} else {
|
|
count += PathCountPart1(paths, visitedSmallCaves, a);
|
|
}
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
long PathCountPart2(Dictionary<string, ImmutableHashSet<string>> paths, ImmutableHashSet<string> visitedSmallCaves, string current, bool twice) {
|
|
long count = paths[current].Contains(END) ? 1 : 0;
|
|
ImmutableHashSet<string> adjacent;
|
|
if (twice) {
|
|
adjacent = paths[current].Except(visitedSmallCaves).Remove(END);
|
|
} else {
|
|
adjacent = paths[current].Remove(END);
|
|
}
|
|
|
|
foreach (var a in adjacent) {
|
|
if (a.ToLower() == a) {
|
|
count += PathCountPart2(paths, visitedSmallCaves.Add(a), a, twice || visitedSmallCaves.Contains(a));
|
|
} else {
|
|
count += PathCountPart2(paths, visitedSmallCaves, a, twice);
|
|
}
|
|
}
|
|
|
|
return count;
|
|
}
|
|
|
|
// Part Two iteratively
|
|
long count = 0;
|
|
var states = new Stack<State>();
|
|
states.Push(new State(ImmutableHashSet.Create(START), START, false));
|
|
while (states.Count > 0) {
|
|
var s = states.Pop();
|
|
count += paths[s.current].Contains(END) ? 1 : 0;
|
|
ImmutableHashSet<string> adjacent;
|
|
if (s.twice) {
|
|
adjacent = paths[s.current].Except(s.visitedSmallCaves).Remove(END);
|
|
} else {
|
|
adjacent = paths[s.current].Remove(END);
|
|
}
|
|
foreach (var a in adjacent) {
|
|
if (Char.IsLower(a[0])) {
|
|
states.Push(new State(s.visitedSmallCaves.Add(a), a, s.twice || s.visitedSmallCaves.Contains(a)));
|
|
} else {
|
|
states.Push(new State(s.visitedSmallCaves, a, s.twice));
|
|
}
|
|
}
|
|
}
|
|
Console.WriteLine(count);
|
|
|
|
record State(ImmutableHashSet<string> visitedSmallCaves, string current, bool twice);
|
|
#endif |