day 12

4 files changed, 103 insertions, 0 deletions

diff --git a/aoc2021.test/DayTests.cs b/aoc2021.test/DayTests.cs
index 5d22b13..723205e 100644
--- a/aoc2021.test/DayTests.cs
+++ b/aoc2021.test/DayTests.cs
@@ -15,6 +15,7 @@ public class DayTests
     [DataRow(typeof(Day09), "478", "1327014")]
     [DataRow(typeof(Day10), "288291", "820045242")]
     [DataRow(typeof(Day11), "1613", "510")]
+    [DataRow(typeof(Day12), "4549", "120535")]
     public void CheckAllDays(Type dayType, string part1, string part2)
     {
         var s = Stopwatch.StartNew();
@@ -56,6 +57,7 @@ public class DayTests
     [DataRow(typeof(Day09), "15", "1134")]
     [DataRow(typeof(Day10), "26397", "288957")]
     [DataRow(typeof(Day11), "1656", "195")]
+    [DataRow(typeof(Day12), "226", "3509")]
     public void CheckTestInputs(Type dayType, string part1, string part2)
     {
         Day.UseTestInput = true;
diff --git a/aoc2021/Day12.cs b/aoc2021/Day12.cs
new file mode 100644
index 0000000..7413206
--- /dev/null
+++ b/aoc2021/Day12.cs
@@ -0,0 +1,62 @@
+namespace aoc2021;
+
+/// <summary>
+/// Day 12: <see href="https://adventofcode.com/2021/day/12"/>
+/// </summary>
+public sealed class Day12 : Day
+{
+    private readonly Dictionary<string, List<string>> _edges = new();
+
+    public Day12() : base(12, "Passage Pathing")
+    {
+        foreach (var line in Input)
+        {
+            var s = line.Split('-', 2);
+
+            if (_edges.ContainsKey(s[0])) _edges[s[0]].Add(s[1]);
+            else _edges[s[0]] = new() { s[1] };
+
+            if (_edges.ContainsKey(s[1])) _edges[s[1]].Add(s[0]);
+            else _edges[s[1]] = new() { s[0] };
+        }
+    }
+
+    private static int WalkGraph(IReadOnlyDictionary<string, List<string>> edges, string point,
+        Dictionary<string, bool> seen)
+    {
+        if (point == "end") return 1;
+        if (char.IsLower(point[0]) && seen.GetValueOrDefault(point, false)) return 0;
+
+        seen[point] = true;
+        return edges[point].Sum(path => WalkGraph(edges, path, seen.ToDictionary(k => k.Key, v => v.Value)));
+    }
+
+    private static int TraverseGraph(IReadOnlyDictionary<string, List<string>> edges, string point,
+        Dictionary<string, bool> seen)
+    {
+        if (point == "end") return 1;
+        if (!TwiceCheck(point, seen)) return 0;
+
+        seen[point] = true;
+        return edges[point].Sum(path => TraverseGraph(edges, path, seen.ToDictionary(k => k.Key, v => v.Value)));
+    }
+
+    private static bool TwiceCheck(string point, Dictionary<string, bool> seen)
+    {
+        if (point == "start" && seen.GetValueOrDefault(point, false))
+            return false;
+        if (!char.IsLower(point[0]) || !seen.GetValueOrDefault(point, false))
+            return true;
+        if (seen.GetValueOrDefault("_twice", false))
+            return false;
+        
+        seen["_twice"] = true;
+        return true;
+    }
+
+    public override string Part1() =>
+        $"{WalkGraph(_edges, "start", new())}";
+
+    public override string Part2() =>
+        $"{TraverseGraph(_edges, "start", new())}";
+}
\ No newline at end of file
diff --git a/aoc2021/input/day12.in b/aoc2021/input/day12.in
new file mode 100644
index 0000000..1aafa7a
--- /dev/null
+++ b/aoc2021/input/day12.in
@@ -0,0 +1,21 @@
+ma-start
+YZ-rv
+MP-rv
+vc-MP
+QD-kj
+rv-kj
+ma-rv
+YZ-zd
+UB-rv
+MP-xe
+start-MP
+zd-end
+ma-UB
+ma-MP
+UB-xe
+end-UB
+ju-MP
+ma-xe
+zd-UB
+start-xe
+YZ-end
\ No newline at end of file
diff --git a/aoc2021/input/test12.in b/aoc2021/input/test12.in
new file mode 100644
index 0000000..4f28403
--- /dev/null
+++ b/aoc2021/input/test12.in
@@ -0,0 +1,18 @@
+fs-end
+he-DX
+fs-he
+start-DX
+pj-DX
+end-zg
+zg-sl
+zg-pj
+pj-he
+RW-he
+fs-DX
+pj-RW
+zg-RW
+start-pj
+he-WI
+zg-he
+pj-fs
+start-RW
\ No newline at end of file