Finish day 15

2 files changed, 133 insertions, 5 deletions

diff --git a/README.md b/README.md
index cdd7198..7893928 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-26-yellow)
-![](https://img.shields.io/badge/📅%20days-13-blue)
+![](https://img.shields.io/badge/⭐%20stars-28-yellow)
+![](https://img.shields.io/badge/📅%20days-14-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.
 
@@ -22,9 +22,9 @@ Welcome to the Advent of Code[^aoc] Kotlin project created by [tchojnacki][githu
 | Day 12: Passage Pathing         |   🌟   |   🌟   |
 | Day 13: Transparent Origami     |        |        |
 | Day 14: Extended Polymerization |   🌟   |   🌟   |
-| Day 15: ???                     |        |        |
-| Day 16: ???                     |        |        |
-| Day 17: ???                     |        |        |
+| Day 15: Chiton                  |   🌟   |   🌟   |
+| Day 16: Packet Decoder          |        |        |
+| Day 17: Trick Shot              |        |        |
 | Day 18: ???                     |        |        |
 | Day 19: ???                     |        |        |
 | Day 20: ???                     |        |        |
diff --git a/src/Day15.kt b/src/Day15.kt
new file mode 100644
index 0000000..763f723
--- /dev/null
+++ b/src/Day15.kt
@@ -0,0 +1,128 @@
+import java.util.*
+
+class CustomPriorityQueue<T>(private val array: Array<T>, private val comparator: Comparator<T>) {
+    init {
+        array.sortWith(comparator)
+    }
+
+    private var i = 0
+
+    private fun indexOfStartingFrom(elem: T, start: Int): Int {
+        for (i in (start until array.size)) {
+            if (i == elem) {
+                return i
+            }
+        }
+
+        return -1
+    }
+
+    fun isNotEmpty(): Boolean = i < array.size
+
+    fun take(): T = array[i++]
+
+    fun revalidate(elem: T) {
+        val currentIndex = indexOfStartingFrom(elem, i)
+
+        if (currentIndex == -1) {
+            return
+        }
+
+        val newIndex = Arrays
+            .binarySearch(array, i, currentIndex, elem, comparator)
+            .let { if (it >= 0) it else -(it + 1) }
+
+        System.arraycopy(array, newIndex, array, newIndex + 1, currentIndex - newIndex)
+
+        array[newIndex] = elem
+    }
+}
+
+class Matrix(private val data: Array<IntArray>, private val size: Int) {
+    companion object {
+        fun fromInput(input: List<String>): Matrix {
+            val data = input.map { line ->
+                line.map { it.digitToInt() }.toIntArray()
+            }.toTypedArray()
+
+            check(data.isNotEmpty()) { "No rows found!" }
+            check(data.first().isNotEmpty()) { "No columns found!" }
+
+            return Matrix(data, data.size)
+        }
+    }
+
+    private fun inMatrix(row: Int, col: Int): Boolean = row in 0 until size && col in 0 until size
+
+    fun set(row: Int, col: Int, value: Int) {
+        check(inMatrix(row, col)) { "Invalid position!" }
+        data[row][col] = value
+    }
+
+    fun get(row: Int, col: Int): Int {
+        check(inMatrix(row, col)) { "Invalid position!" }
+        return data[row][col]
+    }
+
+    fun expand(): Matrix {
+        val expandedData = Array(size * 5) { row ->
+            IntArray(size * 5) { col ->
+                ((data[row % size][col % size] + row / size + col / size) - 1) % 9 + 1
+            }
+        }
+
+        return Matrix(expandedData, size * 5)
+    }
+
+    private fun neighbours(pos: Pair<Int, Int>): Sequence<Pair<Int, Int>> {
+        val offsets = sequenceOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
+
+        return offsets
+            .map { pos.first + it.first to pos.second + it.second }
+            .filter { it.first in 0 until size && it.second in 0 until size }
+    }
+
+    fun dijkstra(): Int {
+        val positions = (0 until size)
+            .flatMap { row -> (0 until size).map { col -> row to col } }
+
+        val distances =
+            positions
+                .associateWith { Int.MAX_VALUE }
+                .toMutableMap()
+
+        distances[0 to 0] = 0
+
+
+        val queue = CustomPriorityQueue(positions.toTypedArray(), compareBy { distances[it]!! })
+
+        while (queue.isNotEmpty()) {
+            val u = queue.take()
+
+            for (v in neighbours(u)) {
+                val newDist = distances[u]!! + data[v.first][v.second]
+                if (distances[v]!! > newDist) {
+                    distances[v] = newDist
+                    queue.revalidate(v)
+                }
+            }
+        }
+
+        return distances[size - 1 to size - 1]!!
+    }
+}
+
+fun main() {
+    fun part1(input: List<String>): Int = Matrix.fromInput(input).dijkstra()
+
+    fun part2(input: List<String>): Int = Matrix.fromInput(input).expand().dijkstra()
+
+
+    val testInput = readInputAsLines("Day15_test")
+    check(part1(testInput) == 40)
+    check(part2(testInput) == 315)
+
+    val input = readInputAsLines("Day15")
+    println(part1(input))
+    println(part2(input))
+}