From d5e470e26936dbdb321ad8b30a44728f2512c378 Mon Sep 17 00:00:00 2001
From: tchojnacki <tomaszchojnacki2001@gmail.com>
Date: Tue, 14 Dec 2021 14:55:45 +0100
Subject: Finish day 12

---
 README.md    |  6 +++---
 src/Day12.kt | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 73 insertions(+), 3 deletions(-)
 create mode 100644 src/Day12.kt

diff --git a/README.md b/README.md
index 6856421..4ef203e 100644
--- a/README.md
+++ b/README.md
@@ -1,7 +1,7 @@
 # Advent of Code 2021 in Kotlin
 ![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin)
-![](https://img.shields.io/badge/⭐%20stars-22-yellow)
-![](https://img.shields.io/badge/📅%20days-11-blue)
+![](https://img.shields.io/badge/⭐%20stars-24-yellow)
+![](https://img.shields.io/badge/📅%20days-12-blue)
 
 Welcome to the Advent of Code[^aoc] Kotlin project created by [tchojnacki][github] using the [Advent of Code Kotlin Template][template] delivered by JetBrains.
 
@@ -19,7 +19,7 @@ Welcome to the Advent of Code[^aoc] Kotlin project created by [tchojnacki][githu
 | Day 9: Smoke Basin             |   🌟   |   🌟   |
 | Day 10: Syntax Scoring         |   🌟   |   🌟   |
 | Day 11: Dumbo Octopus          |   🌟   |   🌟   |
-| Day 12: ???                    |        |        |
+| Day 12: Passage Pathing        |   🌟   |   🌟   |
 | Day 13: ???                    |        |        |
 | Day 14: ???                    |        |        |
 | Day 15: ???                    |        |        |
diff --git a/src/Day12.kt b/src/Day12.kt
new file mode 100644
index 0000000..57a0390
--- /dev/null
+++ b/src/Day12.kt
@@ -0,0 +1,70 @@
+class CaveGraph {
+    companion object {
+        fun fromLines(input: List<String>): CaveGraph =
+            CaveGraph().apply { input.forEach { addConnection(it) } }
+    }
+
+    private val adjacencyList = mutableMapOf<Node, Set<Node>>()
+
+    fun addConnection(connectionString: String) {
+        val (from, to) = connectionString.split("-").map(Node::fromString)
+
+        adjacencyList.merge(from, setOf(to), Set<Node>::union)
+        adjacencyList.merge(to, setOf(from), Set<Node>::union)
+    }
+
+    fun countPaths(canUseDoubleTraversal: Boolean = false): Int = traverse(Node.Start, setOf(), !canUseDoubleTraversal)
+
+    private fun traverse(from: Node, visitedBefore: Set<Node>, usedUpDoubleTraverse: Boolean): Int {
+        return adjacencyList[from]!!.sumOf {
+            when (it) {
+                is Node.Start -> 0
+                is Node.End -> 1
+                is Node.Big -> traverse(it, visitedBefore + from, usedUpDoubleTraverse)
+                is Node.Small -> {
+                    if (!visitedBefore.contains(it)) {
+                        traverse(it, visitedBefore + from, usedUpDoubleTraverse)
+                    } else if (!usedUpDoubleTraverse) {
+                        traverse(it, visitedBefore + from, true)
+                    } else {
+                        0
+                    }
+                }
+            }
+        }
+    }
+
+    sealed class Node {
+        companion object {
+            fun fromString(text: String): Node = when (text) {
+                "start" -> Start
+                "end" -> End
+                else -> if (text == text.uppercase()) {
+                    Big(text)
+                } else {
+                    Small(text)
+                }
+            }
+        }
+
+        object Start : Node()
+        object End : Node()
+        data class Small(private val identifier: String) : Node()
+        data class Big(private val identifier: String) : Node()
+    }
+}
+
+fun main() {
+    fun part1(input: List<String>): Int = CaveGraph.fromLines(input).countPaths()
+
+    fun part2(input: List<String>): Int = CaveGraph.fromLines(input).countPaths(true)
+
+
+    val testInput = readInputAsLines("Day12_test")
+    check(part1(testInput) == 226)
+    check(part2(testInput) == 3509)
+
+    val input = readInputAsLines("Day12")
+    println(part1(input))
+    println(part2(input))
+}
-- 
cgit v1.2.3