diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | src/Day12.kt | 70 |
2 files changed, 73 insertions, 3 deletions
@@ -1,7 +1,7 @@ # Advent of Code 2021 in Kotlin  - - + + 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)) +} |