diff options
Diffstat (limited to 'aoc-2021-kotlin')
| -rw-r--r-- | aoc-2021-kotlin/README.md | 8 | ||||
| -rw-r--r-- | aoc-2021-kotlin/src/Day23.kt | 279 |
2 files changed, 283 insertions, 4 deletions
diff --git a/aoc-2021-kotlin/README.md b/aoc-2021-kotlin/README.md index 5a5e967..dc27235 100644 --- a/aoc-2021-kotlin/README.md +++ b/aoc-2021-kotlin/README.md @@ -1,7 +1,7 @@ # Advent of Code 2021 in Kotlin  - - + + Welcome to the Advent of Code Kotlin project created by [tchojnacki][github] using the [Advent of Code Kotlin Template][template] delivered by JetBrains. @@ -32,9 +32,9 @@ Welcome to the Advent of Code Kotlin project created by [tchojnacki][github] usi | Day 20: Trench Map | 🌟 | 🌟 | | Day 21: Dirac Dice | 🌟 | 🌟 | | Day 22: Reactor Reboot | 🌟 | 🌟 | -| Day 23: Amphipod | | | +| Day 23: Amphipod | 🌟 | 🌟 | | Day 24: Arithmetic Logic Unit | 🌟 | 🌟 | -| Day 25: Sea Cucumber | 🌟 | | +| Day 25: Sea Cucumber | 🌟 | 🌟 | [aoc]: https://adventofcode.com diff --git a/aoc-2021-kotlin/src/Day23.kt b/aoc-2021-kotlin/src/Day23.kt new file mode 100644 index 0000000..232434a --- /dev/null +++ b/aoc-2021-kotlin/src/Day23.kt @@ -0,0 +1,279 @@ +import java.util.Comparator +import java.util.PriorityQueue +import kotlin.math.absoluteValue +import kotlin.math.max +import kotlin.math.min + +object Day23 { + private enum class Amphipod(val energyPerStep: Int) { + Amber(1), + Bronze(10), + Copper(100), + Desert(1000); + + companion object { + fun fromChar(char: Char) = when (char) { + 'A' -> Amber + 'B' -> Bronze + 'C' -> Copper + 'D' -> Desert + else -> null + } + } + + override fun toString(): String { + return super.toString().first().toString() + } + } + + private sealed class Position { + abstract fun pop(): Position + abstract fun push(amphipod: Amphipod): Position + abstract fun peek(): Amphipod + + data class Room(val targetType: Amphipod, val occupants: List<Amphipod>) : Position() { + override fun pop() = copy(occupants = occupants.dropLast(1)) + override fun push(amphipod: Amphipod) = copy(occupants = occupants + amphipod) + override fun peek() = occupants.last() + val isSettled get() = occupants.all { it == targetType } + } + + data class Hallway(val occupant: Amphipod?) : Position() { + override fun pop() = copy(occupant = null) + override fun push(amphipod: Amphipod) = copy(occupant = amphipod) + override fun peek() = occupant!! + } + } + + private data class State(val roomDepth: Int, val positions: List<Position>) { + companion object { + fun fromString(input: String) = + input + .split("\n").filter { it.isNotBlank() }.drop(1).dropLast(1) + .map { line -> line.drop(1).dropLast(1) } + .let { lines -> + State( + lines.size - 1, + (0..10).map { position -> + if (lines[1][position] == '#') + Position.Hallway(Amphipod.fromChar(lines.first()[position])) + else + Position.Room( + when (position) { + 2 -> Amphipod.Amber + 4 -> Amphipod.Bronze + 6 -> Amphipod.Copper + 8 -> Amphipod.Desert + else -> throw IllegalStateException() + }, + lines.indices + .drop(1) + .reversed() + .mapNotNull { Amphipod.fromChar(lines[it][position]) } + ) + } + ) + } + } + + override fun toString(): String { + val stringBuilder = StringBuilder() + + stringBuilder.append("#".repeat(positions.size + 2)) + stringBuilder.append('\n') + + stringBuilder.append('#') + positions.forEach { + stringBuilder.append( + if (it is Position.Hallway) it.occupant?.toString() ?: '.' + else '.' + ) + } + stringBuilder.append('#') + stringBuilder.append('\n') + + stringBuilder.append('#') + positions.forEach { + stringBuilder.append( + if (it is Position.Room) it.occupants.getOrNull(roomDepth - 1)?.toString() ?: '.' + else '#' + ) + } + stringBuilder.append('#') + stringBuilder.append('\n') + + val hallwayStart = (positions.indexOfFirst { it is Position.Room } - 1) + val hallwayEnd = (positions.indexOfLast { it is Position.Room } + 1) + (roomDepth - 2 downTo 0).forEach { depth -> + stringBuilder.append(" ".repeat(hallwayStart + 1)) + (hallwayStart..hallwayEnd).map { positions[it] }.forEach { + stringBuilder.append( + if (it is Position.Room) it.occupants.getOrNull(depth)?.toString() ?: '.' + else '#' + ) + } + stringBuilder.append('\n') + } + + stringBuilder.append(" ".repeat(hallwayStart + 1)) + stringBuilder.append("#".repeat(hallwayEnd - hallwayStart + 1)) + stringBuilder.append('\n') + + return stringBuilder.toString() + } + + val isFinished + get() = positions.all { + when (it) { + is Position.Hallway -> hasEmpty(it) + is Position.Room -> hasFull(it) && it.occupants.all { a -> a == it.targetType } + } + } + + private fun withMove(from: Int, to: Int) = positions[from].peek().let { amphipod -> + val horizontalDistance = (to - from).absoluteValue + val outDistance = (positions[from] as? Position.Room)?.let { roomDepth - it.occupants.size + 1 } ?: 0 + val inDistance = (positions[to] as? Position.Room)?.let { roomDepth - it.occupants.size } ?: 0 + val energy = (outDistance + horizontalDistance + inDistance) * amphipod.energyPerStep + + energy to copy(positions = positions.mapIndexed { index, position -> + when (index) { + from -> position.pop() + to -> position.push(amphipod) + else -> position + } + }) + } + + private fun hasHallwayBlocked(from: Int, to: Int) = positions + .subList(min(from, to) + 1, max(from, to)) + .any { it is Position.Hallway && it.occupant != null } + + private fun hasEmpty(position: Position) = when (position) { + is Position.Room -> position.occupants.isEmpty() + is Position.Hallway -> position.occupant == null + } + + private fun hasFull(position: Position) = when (position) { + is Position.Room -> position.occupants.size == roomDepth + is Position.Hallway -> position.occupant != null + } + + fun allNextStates() = sequence { + for ((fromPair, toPair) in combinations(positions.withIndex())) { + val (startIndex, start) = fromPair + val (endIndex, end) = toPair + + if ( + startIndex == endIndex || + hasEmpty(start) || + hasFull(end) || + hasHallwayBlocked(startIndex, endIndex) + ) + continue + + val afterMove = withMove(startIndex, endIndex) + + when (end) { + is Position.Room -> { + if (start.peek() == end.targetType && end.isSettled) + yield(afterMove) + } + + is Position.Hallway -> { + if (start is Position.Room && !start.isSettled) + yield(afterMove) + } + } + } + } + } + + private class UniquePriorityQueue<T>(comparator: Comparator<T>) { + private val internalQueue = PriorityQueue(comparator) + private val internalSet = mutableSetOf<T>() + + constructor(initialValue: T, comparator: Comparator<T>) : this(comparator) { + add(initialValue) + } + + fun add(value: T) { + if (value !in internalSet) { + internalQueue.add(value) + internalSet.add(value) + } + } + + fun poll(): T { + val value = internalQueue.poll() + internalSet.remove(value) + return value + } + + fun isNotEmpty() = internalQueue.isNotEmpty() + } + + fun part1(input: String): Int { + val state = State.fromString(input) + + val visited = mutableSetOf<State>() + val distances = mutableMapOf(state to 0) + val queue = UniquePriorityQueue(state, compareBy { distances[it]!! }) + + queue.add(state) + + while (queue.isNotEmpty()) { + val current = queue.poll() + + for ((cost, neighbour) in current.allNextStates()) { + if (neighbour !in visited) { + val newCost = distances[current]!! + cost + if (newCost < distances.getOrDefault(neighbour, Int.MAX_VALUE)) { + distances[neighbour] = newCost + queue.add(neighbour) + } + + queue.add(neighbour) + } + } + + visited.add(current) + } + + return distances[visited.find { it.isFinished }]!! + } + + fun part2(input: String): Int { + val list = input.split("\n").toMutableList() + list.addAll( + 3, + """ + | #D#C#B#A# + | #D#B#A#C# + """.trimMargin().split("\n") + ) + return part1(list.joinToString("\n")) + } +} + +fun main() { + val testInput = """ + ############# + #...........# + ###B#C#B#D### + #A#D#C#A# + ######### + """.trimIndent() + check(Day23.part1(testInput) == 12521) + check(Day23.part2(testInput) == 44169) + + val input = """ + ############# + #...........# + ###D#B#A#C### + #B#D#A#C# + ######### + """.trimIndent() + println(Day23.part1(input)) + println(Day23.part2(input)) +} |