Finish the last puzzle

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
 ![Kotlin](https://img.shields.io/badge/Kotlin-grey?logo=Kotlin)
-![47/50 stars](https://img.shields.io/badge/🌟%20stars-47/50-orange)
-![24/25 days](https://img.shields.io/badge/📅%20days-24/25-blue)
+![50/50 stars](https://img.shields.io/badge/🌟%20stars-50/50-orange)
+![25/25 days](https://img.shields.io/badge/📅%20days-25/25-blue)
 
 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))
+}