Move subproject to avoid IntelliJ module name issues

21 files changed, 1629 insertions, 0 deletions

diff --git a/aoc-2021-kotlin/src/Day01.kt b/aoc-2021-kotlin/src/Day01.kt
new file mode 100644
index 0000000..4ac1ef7
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day01.kt
@@ -0,0 +1,24 @@
+object Day01 {
+    fun part1(input: List<Int>) =
+        input
+            .zipWithNext()
+            .count { it.second > it.first }
+
+    fun part2(input: List<Int>) =
+        input
+            .asSequence()
+            .windowed(3)
+            .map { it.sum() }
+            .zipWithNext()
+            .count { it.second > it.first }
+}
+
+fun main() {
+    val testInput = readInputAsNumbers("Day01_test")
+    check(Day01.part1(testInput) == 7)
+    check(Day01.part2(testInput) == 5)
+
+    val input = readInputAsNumbers("Day01")
+    println(Day01.part1(input))
+    println(Day01.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day02.kt b/aoc-2021-kotlin/src/Day02.kt
new file mode 100644
index 0000000..2eb085a
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day02.kt
@@ -0,0 +1,56 @@
+object Day02 {
+    private fun dispatchCommands(commands: List<String>, action: (command: String, argument: Int) -> Unit) {
+        for (line in commands) {
+            val parts = line.split(" ")
+            val command = parts[0]
+            val argument = parts[1].toInt()
+
+            action(command, argument)
+        }
+    }
+
+    fun part1(input: List<String>): Int {
+        var horizontal = 0
+        var depth = 0
+
+        dispatchCommands(input) { command, argument ->
+            when (command) {
+                "forward" -> horizontal += argument
+                "down" -> depth += argument
+                "up" -> depth -= argument
+            }
+        }
+
+        return horizontal * depth
+    }
+
+    fun part2(input: List<String>): Int {
+        var horizontal = 0
+        var depth = 0
+        var aim = 0
+
+        dispatchCommands(input) { command, argument ->
+            when (command) {
+                "forward" -> {
+                    horizontal += argument
+                    depth += aim * argument
+                }
+
+                "down" -> aim += argument
+                "up" -> aim -= argument
+            }
+        }
+
+        return horizontal * depth
+    }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day02_test")
+    check(Day02.part1(testInput) == 150)
+    check(Day02.part2(testInput) == 900)
+
+    val input = readInputAsLines("Day02")
+    println(Day02.part1(input))
+    println(Day02.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day03.kt b/aoc-2021-kotlin/src/Day03.kt
new file mode 100644
index 0000000..1418a2e
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day03.kt
@@ -0,0 +1,51 @@
+object Day03 {
+    private fun addLists(l1: List<Int>, l2: List<Int>) = l1.zip(l2).map { it.first + it.second }
+
+    private fun valueOfBits(bitList: List<Int>) = bitList.reduce { acc, bit -> acc * 2 + bit }
+
+    private fun invertBits(bitList: List<Int>) = bitList.map { bit -> 1 - bit }
+
+    private fun mostCommonBits(input: List<List<Int>>): List<Int> =
+        input
+            .reduce(::addLists)
+            .map { bit -> if (bit.toDouble() / input.size >= 0.5) 1 else 0 }
+
+    private fun selectByBitCriteria(
+        input: List<List<Int>>,
+        comparisonCriteria: (currentList: List<List<Int>>) -> List<Int>
+    ): List<Int>? {
+        var list = input
+        var index = 0
+
+        while (list.size > 1 && index < list[0].size) {
+            list = list.filter { e -> e[index] == comparisonCriteria(list)[index] }
+            index += 1
+        }
+
+        return list.getOrNull(0)
+    }
+
+    fun part1(input: List<List<Int>>): Int =
+        mostCommonBits(input)
+            .let { gammaBits ->
+                val epsilonBits = invertBits(gammaBits)
+                return valueOfBits(gammaBits) * valueOfBits(epsilonBits)
+            }
+
+    fun part2(input: List<List<Int>>): Int {
+        val oxygenRating = selectByBitCriteria(input) { mostCommonBits(it) }!!
+        val scrubberRating = selectByBitCriteria(input) { invertBits(mostCommonBits(it)) }!!
+
+        return valueOfBits(oxygenRating) * valueOfBits(scrubberRating)
+    }
+}
+
+fun main() {
+    val testInput = readInputAsBitLists("Day03_test")
+    check(Day03.part1(testInput) == 198)
+    check(Day03.part2(testInput) == 230)
+
+    val input = readInputAsBitLists("Day03")
+    println(Day03.part1(input))
+    println(Day03.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day04.kt b/aoc-2021-kotlin/src/Day04.kt
new file mode 100644
index 0000000..96cdf3b
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day04.kt
@@ -0,0 +1,97 @@
+object Day04 {
+    private class Bingo(private val revealQueue: ArrayDeque<Int>, private val boards: List<Board>) {
+        companion object {
+            fun fromString(input: String): Bingo {
+                val sections = input.trim().split("(\\r?\\n){2}".toRegex())
+
+                val revealQueueString = sections.first()
+                val revealQueue = ArrayDeque(revealQueueString.split(",").map(String::toInt))
+
+                val boards = sections.drop(1).map { Board.fromMatrixString(it) }
+
+                return Bingo(revealQueue, boards)
+            }
+        }
+
+        fun getResults() = sequence {
+            while (revealQueue.isNotEmpty() && boards.any { !it.didWin }) {
+                val number = revealQueue.removeFirst()
+
+                for (board in boards.filter { !it.didWin }) {
+                    board.reveal(number)
+
+                    if (board.didWin) {
+                        yield(board.sumOfUnmarked * number)
+                    }
+                }
+            }
+        }
+
+        private class Board(private var rows: List<List<Square>>) {
+            companion object {
+                fun fromMatrixString(matrixString: String): Board = Board(
+                    matrixString.trim().split("\\r?\\n".toRegex()).map { rowString ->
+                        rowString.trim().split("\\s+".toRegex()).map { squareString ->
+                            Square.Unmarked(squareString.toInt())
+                        }
+                    }
+                )
+
+                private const val SIZE = 5
+
+                private val ROWS = (0 until SIZE).map { row ->
+                    (0 until SIZE).map { square ->
+                        Pair(row, square)
+                    }
+                }
+
+                private val COLUMNS = (0 until SIZE).map { column ->
+                    (0 until SIZE).map { square ->
+                        Pair(square, column)
+                    }
+                }
+
+                private val WINNING_CONFIGURATIONS = ROWS + COLUMNS
+            }
+
+            fun reveal(number: Int) {
+                rows = rows.map { row ->
+                    row.map { square ->
+                        if (square is Square.Unmarked && square.number == number) Square.Marked else square
+                    }
+                }
+            }
+
+            val didWin: Boolean
+                get() = WINNING_CONFIGURATIONS.any { configuration ->
+                    configuration.all { (row, column) -> rows[row][column] is Square.Marked }
+                }
+
+            val sumOfUnmarked: Int
+                get() = rows.fold(0) { rowAcc, row ->
+                    rowAcc + row.fold(0) { squareAcc, square ->
+                        squareAcc + if (square is Square.Unmarked) square.number else 0
+                    }
+                }
+
+            sealed class Square {
+                object Marked : Square()
+                class Unmarked(val number: Int) : Square()
+            }
+        }
+    }
+
+    fun bothParts(input: String) = Bingo.fromString(input).getResults().let { it.first() to it.last() }
+}
+
+fun main() {
+    val testInput = readInputAsString("Day04_test")
+    val testOutput = Day04.bothParts(testInput)
+    check(testOutput.first == 4512)
+    check(testOutput.second == 1924)
+
+    val input = readInputAsString("Day04")
+    val output = Day04.bothParts(input)
+    println(output.first)
+    println(output.second)
+}
diff --git a/aoc-2021-kotlin/src/Day05.kt b/aoc-2021-kotlin/src/Day05.kt
new file mode 100644
index 0000000..2c5e219
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day05.kt
@@ -0,0 +1,62 @@
+import kotlin.math.absoluteValue
+import kotlin.math.max
+import kotlin.math.sign
+
+object Day05 {
+    private data class Line(val start: Pos2D, val end: Pos2D) {
+        companion object {
+            fun fromString(input: String): Line {
+                val (start, end) = input.split(" -> ").map { coordinateString ->
+                    val (x, y) = coordinateString.split(",").map(String::toInt)
+                    Pos2D(x, y)
+                }
+
+                return Line(start, end)
+            }
+        }
+
+        val isHorizontalOrVertical: Boolean
+            get() = start.x == end.x || start.y == end.y
+
+        val isDiagonal: Boolean
+            get() = (end.x - start.x).absoluteValue == (end.y - start.y).absoluteValue
+
+        val pointSequence: Sequence<Pos2D>
+            get() = sequence {
+                val xOffset = end.x - start.x
+                val yOffset = end.y - start.y
+
+                for (s in 0..max(xOffset.absoluteValue, yOffset.absoluteValue)) {
+                    val x = start.x + s * xOffset.sign
+                    val y = start.y + s * yOffset.sign
+
+                    yield(Pos2D(x, y))
+                }
+            }
+    }
+
+    private fun helper(input: List<String>, linePredicate: (line: Line) -> Boolean) = input
+        .asSequence()
+        .map(Line::fromString)
+        .filter(linePredicate)
+        .flatMap(Line::pointSequence)
+        .groupingBy { it }
+        .eachCount()
+        .values
+        .count { it >= 2 }
+
+    fun part1(input: List<String>): Int = helper(input, Line::isHorizontalOrVertical)
+
+    fun part2(input: List<String>): Int = helper(input) { it.isHorizontalOrVertical || it.isDiagonal }
+
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day05_test")
+    check(Day05.part1(testInput) == 5)
+    check(Day05.part2(testInput) == 12)
+
+    val input = readInputAsLines("Day05")
+    println(Day05.part1(input))
+    println(Day05.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day06.kt b/aoc-2021-kotlin/src/Day06.kt
new file mode 100644
index 0000000..4627cca
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day06.kt
@@ -0,0 +1,38 @@
+object Day06 {
+    private fun calculateFishPopulation(input: String, days: Int): Long {
+        val fishCounts =
+            input
+                .trim()
+                .split(",")
+                .map(String::toInt)
+                .groupingBy { it }
+                .eachCount()
+                .mapValues { (_, v) -> v.toLong() }
+                .toMutableMap()
+
+        repeat(days) {
+            val readyToBirth = fishCounts.getOrDefault(0, 0)
+            repeat(8) {
+                fishCounts[it] = fishCounts.getOrDefault(it + 1, 0)
+            }
+            fishCounts.merge(6, readyToBirth, Long::plus)
+            fishCounts[8] = readyToBirth
+        }
+
+        return fishCounts.values.sum()
+    }
+
+    fun part1(input: String): Int = calculateFishPopulation(input, 80).toInt()
+
+    fun part2(input: String): Long = calculateFishPopulation(input, 256)
+}
+
+fun main() {
+    val testInput = readInputAsString("Day06_test")
+    check(Day06.part1(testInput) == 5934)
+    check(Day06.part2(testInput) == 26984457539)
+
+    val input = readInputAsString("Day06")
+    println(Day06.part1(input))
+    println(Day06.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day07.kt b/aoc-2021-kotlin/src/Day07.kt
new file mode 100644
index 0000000..9c1b79f
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day07.kt
@@ -0,0 +1,27 @@
+import kotlin.math.absoluteValue
+
+object Day07 {
+    fun part1(input: String): Int {
+        val numbers = input.trim().split(",").map(String::toInt)
+        val range = numbers.minOrNull()!!..numbers.maxOrNull()!!
+
+        return range.minOf { n -> numbers.sumOf { (it - n).absoluteValue } }
+    }
+
+    fun part2(input: String): Int {
+        val numbers = input.trim().split(",").map(String::toInt)
+        val range = numbers.minOrNull()!!..numbers.maxOrNull()!!
+
+        return range.minOf { n -> numbers.map { (it - n).absoluteValue }.sumOf { (it * (it + 1)) / 2 } }
+    }
+}
+
+fun main() {
+    val testInput = readInputAsString("Day07_test")
+    check(Day07.part1(testInput) == 37)
+    check(Day07.part2(testInput) == 168)
+
+    val input = readInputAsString("Day07")
+    println(Day07.part1(input))
+    println(Day07.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day08.kt b/aoc-2021-kotlin/src/Day08.kt
new file mode 100644
index 0000000..b513352
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day08.kt
@@ -0,0 +1,51 @@
+object Day08 {
+    fun part1(input: List<String>): Int =
+        input.sumOf {
+            it
+                .split("|")[1]
+                .trim()
+                .split(" ")
+                .map(String::length)
+                .count { len -> len in listOf(2, 3, 4, 7) }
+        }
+
+    fun part2(input: List<String>): Long = input.sumOf { line ->
+        val (patternString, outputString) = line.split("|").map(String::trim)
+        val patterns = patternString.split(" ").map(String::toSet)
+
+        val one = patterns.first { it.size == 2 }
+        val four = patterns.first { it.size == 4 }
+        val seven = patterns.first { it.size == 3 }
+        val eight = patterns.first { it.size == 7 }
+
+        val top = seven - one
+        val middle = patterns.filter { it.size == 5 }.reduce(Set<Char>::intersect) intersect four
+        val five = patterns.filter { it.size == 6 }.reduce(Set<Char>::intersect) + middle
+        val bottom = five - (four + top)
+        val nine = four + top + bottom
+        val lowerLeft = eight - nine
+        val six = five + lowerLeft
+        val lowerRight = one intersect six
+        val three = one + top + middle + bottom
+        val zero = eight - middle
+        val upperLeft = nine - three
+        val two = eight - (upperLeft + lowerRight)
+
+        val encodings = listOf(zero, one, two, three, four, five, six, seven, eight, nine)
+
+        outputString
+            .split(" ")
+            .joinToString("") { encodings.indexOf(it.toSet()).toString() }
+            .toLong()
+    }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day08_test")
+    check(Day08.part1(testInput) == 26)
+    check(Day08.part2(testInput) == 61229L)
+
+    val input = readInputAsLines("Day08")
+    println(Day08.part1(input))
+    println(Day08.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day09.kt b/aoc-2021-kotlin/src/Day09.kt
new file mode 100644
index 0000000..9d0c41d
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day09.kt
@@ -0,0 +1,40 @@
+object Day09 {
+    private fun Map<Pos2D, Int>.getLowPoints() =
+        filter { (pos, num) -> Pos2D.directions4.all { num < getOrDefault(pos + it, 9) } }
+
+    fun part1(input: List<String>) =
+        parseToMap(input).getLowPoints().values.sumOf { it + 1 }
+
+    fun part2(input: List<String>): Int {
+        val map = parseToMap(input)
+
+        fun traverseBasin(pos: Pos2D, acc: MutableSet<Pos2D>) {
+            acc.add(pos)
+            Pos2D.directions4
+                .map { pos + it }
+                .filter { !acc.contains(it) && map.getOrDefault(it, 9) < 9 }
+                .forEach { traverseBasin(it, acc) }
+        }
+
+        return map
+            .getLowPoints()
+            .map {
+                val visited = mutableSetOf<Pos2D>()
+                traverseBasin(it.key, visited)
+                visited.size
+            }
+            .sortedDescending()
+            .take(3)
+            .sum()
+    }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day09_test")
+    check(Day09.part1(testInput) == 15)
+    check(Day09.part2(testInput) == 1134)
+
+    val input = readInputAsLines("Day09")
+    println(Day09.part1(input))
+    println(Day09.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day10.kt b/aoc-2021-kotlin/src/Day10.kt
new file mode 100644
index 0000000..d6d026c
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day10.kt
@@ -0,0 +1,91 @@
+object Day10 {
+    private enum class ChunkDelimiter(val open: Char, val close: Char) {
+        Parentheses('(', ')'),
+        Brackets('[', ']'),
+        Braces('{', '}'),
+        Angled('<', '>');
+
+        companion object {
+            fun isOpening(character: Char): Boolean = values().any { it.open == character }
+            fun isClosing(character: Char): Boolean = values().any { it.close == character }
+            fun from(character: Char): ChunkDelimiter =
+                values().find { it.open == character || it.close == character }!!
+        }
+    }
+
+    private sealed class SyntaxError {
+        object None : SyntaxError()
+        class IncompleteLine(private val stack: ArrayDeque<ChunkDelimiter>) : SyntaxError() {
+            val score: Long
+                get() {
+                    fun delimiterValue(delimiter: ChunkDelimiter): Int = when (delimiter) {
+                        ChunkDelimiter.Parentheses -> 1
+                        ChunkDelimiter.Brackets -> 2
+                        ChunkDelimiter.Braces -> 3
+                        ChunkDelimiter.Angled -> 4
+                    }
+
+                    return stack.fold(0) { acc, elem -> acc * 5 + delimiterValue(elem) }
+                }
+        }
+
+        class CorruptedLine(private val invalidDelimiter: ChunkDelimiter) : SyntaxError() {
+            val score: Int
+                get() = when (invalidDelimiter) {
+                    ChunkDelimiter.Parentheses -> 3
+                    ChunkDelimiter.Brackets -> 57
+                    ChunkDelimiter.Braces -> 1197
+                    ChunkDelimiter.Angled -> 25137
+                }
+        }
+    }
+
+    private fun parse(line: String): SyntaxError {
+        val stack = ArrayDeque<ChunkDelimiter>()
+
+        for (char in line) {
+            when {
+                ChunkDelimiter.isOpening(char) -> stack.addFirst(ChunkDelimiter.from(char))
+                ChunkDelimiter.isClosing(char) -> {
+                    val closingDelimiter = ChunkDelimiter.from(char)
+                    if (stack.first() == closingDelimiter) {
+                        stack.removeFirst()
+                    } else {
+                        return SyntaxError.CorruptedLine(closingDelimiter)
+                    }
+                }
+            }
+        }
+
+        if (stack.isNotEmpty()) {
+            return SyntaxError.IncompleteLine(stack)
+        }
+
+        return SyntaxError.None
+    }
+
+    fun part1(input: List<String>): Int = input
+        .map { parse(it) }
+        .filterIsInstance<SyntaxError.CorruptedLine>()
+        .sumOf { it.score }
+
+    fun part2(input: List<String>): Long =
+        input
+            .asSequence()
+            .map { parse(it) }
+            .filterIsInstance<SyntaxError.IncompleteLine>()
+            .map { it.score }
+            .sorted()
+            .toList()
+            .let { it[it.size / 2] }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day10_test")
+    check(Day10.part1(testInput) == 26397)
+    check(Day10.part2(testInput) == 288957L)
+
+    val input = readInputAsLines("Day10")
+    println(Day10.part1(input))
+    println(Day10.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day11.kt b/aoc-2021-kotlin/src/Day11.kt
new file mode 100644
index 0000000..db56d61
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day11.kt
@@ -0,0 +1,48 @@
+object Day11 {
+    private fun flashSequence(input: Map<Pos2D, Int>) = sequence {
+        val map = input.toMutableMap()
+
+        while (true) {
+            val flashed = mutableSetOf<Pos2D>()
+            fun canFlash(entry: Map.Entry<Pos2D, Int>): Boolean = entry.value > 9 && !flashed.contains(entry.key)
+
+            // 1)
+            map.forEach { (pos, energy) -> map[pos] = energy + 1 }
+
+            // 2)
+            while (map.any(::canFlash)) {
+                map
+                    .filter(::canFlash)
+                    .forEach { (pos, _) ->
+                        flashed.add(pos)
+                        Pos2D.directions8.map { pos + it }.forEach {
+                            if (map.containsKey(it)) {
+                                map[it] = map[it]!! + 1
+                            }
+                        }
+                    }
+            }
+
+            // 3)
+            flashed.forEach { map[it] = 0 }
+
+            yield(flashed.size)
+        }
+    }
+
+    fun bothParts(input: List<String>) = flashSequence(parseToMap(input)).let { seq ->
+        seq.take(100).sum() to seq.indexOfFirst { it == 100 } + 1
+    }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day11_test")
+    val testOutput = Day11.bothParts(testInput)
+    check(testOutput.first == 1656)
+    check(testOutput.second == 195)
+
+    val input = readInputAsLines("Day11")
+    val output = Day11.bothParts(input)
+    println(output.first)
+    println(output.second)
+}
diff --git a/aoc-2021-kotlin/src/Day12.kt b/aoc-2021-kotlin/src/Day12.kt
new file mode 100644
index 0000000..d3368da
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day12.kt
@@ -0,0 +1,72 @@
+object Day12 {
+    private class CaveGraph {
+        companion object {
+            fun fromLines(input: List<String>): CaveGraph =
+                CaveGraph().apply { input.forEach { addConnection(it) } }
+        }
+
+        private val adjacencyList = mutableMapOf<Node, Set<Node>>()
+
+        private 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
+                        }
+                    }
+                }
+            }
+        }
+
+        private 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 bothParts(input: List<String>) = CaveGraph.fromLines(input).let { it.countPaths() to it.countPaths(true) }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day12_test")
+    val testOutput = Day12.bothParts(testInput)
+    check(testOutput.first == 226)
+    check(testOutput.second == 3509)
+
+    val input = readInputAsLines("Day12")
+    val output = Day12.bothParts(input)
+    println(output.first)
+    println(output.second)
+}
diff --git a/aoc-2021-kotlin/src/Day13.kt b/aoc-2021-kotlin/src/Day13.kt
new file mode 100644
index 0000000..0f9b096
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day13.kt
@@ -0,0 +1,99 @@
+object Day13 {
+    private sealed class FoldCommand {
+        abstract fun dispatch(dots: Set<Pos2D>): Set<Pos2D>
+
+        class AlongX(private val x: Int) : FoldCommand() {
+            override fun dispatch(dots: Set<Pos2D>): Set<Pos2D> = dots
+                .filter { it.x != x }
+                .map {
+                    if (it.x < x) {
+                        it
+                    } else {
+                        Pos2D(2 * x - it.x, it.y)
+                    }
+                }
+                .toSet()
+        }
+
+        class AlongY(private val y: Int) : FoldCommand() {
+            override fun dispatch(dots: Set<Pos2D>): Set<Pos2D> = dots
+                .filter { it.y != y }
+                .map {
+                    if (it.y < y) {
+                        it
+                    } else {
+                        Pos2D(it.x, 2 * y - it.y)
+                    }
+                }
+                .toSet()
+        }
+    }
+
+    private fun parseOrigami(input: List<String>): Pair<Set<Pos2D>, Sequence<FoldCommand>> {
+        val dots = mutableSetOf<Pos2D>()
+        val commands = mutableListOf<FoldCommand>()
+
+        for (line in input) {
+            if (line.matches("\\d+,\\d+".toRegex())) {
+                val (x, y) = line.split(",").map(String::toInt)
+                dots.add(Pos2D(x, y))
+            }
+
+            if (line.matches("fold along [xy]=\\d+".toRegex())) {
+                val equation = line.substring(11)
+                val (axis, valueString) = equation.split("=")
+                val value = valueString.toInt()
+
+                commands.add(
+                    when (axis) {
+                        "x" -> FoldCommand.AlongX(value)
+                        "y" -> FoldCommand.AlongY(value)
+                        else -> throw IllegalStateException("Illegal axis given!")
+                    }
+                )
+            }
+        }
+
+        return dots to commands.asSequence()
+    }
+
+    fun part1(input: List<String>): Int {
+        val (dots, commands) = parseOrigami(input)
+
+        return commands.first().dispatch(dots).size
+    }
+
+    fun part2(input: List<String>): String {
+        val origami = parseOrigami(input)
+        var dots = origami.first
+        val commands = origami.second
+
+        commands.forEach {
+            dots = it.dispatch(dots)
+        }
+
+        val bounds = dots.reduce { max, pos ->
+            when ((pos.x > max.x) to (pos.y > max.y)) {
+                true to true -> pos
+                true to false -> Pos2D(pos.x, max.y)
+                false to true -> Pos2D(max.x, pos.y)
+                else -> max
+            }
+        }
+
+        val lines = Array(bounds.y + 1) { Array(bounds.x + 1) { ' ' } }
+
+        dots.forEach { lines[it.y][it.x] = '#' }
+
+        return lines.joinToString("\n") { it.joinToString("") }
+    }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day13_test")
+    check(Day13.part1(testInput) == 17)
+
+    val input = readInputAsLines("Day13")
+    println(Day13.part1(input))
+    println(Day13.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day14.kt b/aoc-2021-kotlin/src/Day14.kt
new file mode 100644
index 0000000..920ea9e
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day14.kt
@@ -0,0 +1,46 @@
+object Day14 {
+    private fun getPolymerLetterCounts(input: List<String>, iterations: Int): Long {
+        val template = input.first()
+        val rules = input.drop(2).associate {
+            val (pattern, replacement) = it.split(" -> ")
+            (pattern[0] to pattern[1]) to replacement.first()
+        }
+
+        var pairCounts = template
+            .zipWithNext()
+            .groupingBy { it }
+            .eachCount()
+            .mapValues { (_, v) -> v.toLong() }
+
+        repeat(iterations) {
+            val newCounts = mutableMapOf<Pair<Char, Char>, Long>()
+
+            pairCounts.forEach { (pair, count) ->
+                newCounts.merge(rules[pair]!! to pair.second, count, Long::plus)
+                newCounts.merge(pair.first to rules[pair]!!, count, Long::plus)
+            }
+
+            pairCounts = newCounts
+        }
+
+        val letterCounts = mutableMapOf<Char, Long>()
+        pairCounts.forEach { (pair, count) -> letterCounts.merge(pair.second, count, Long::plus) }
+        letterCounts.merge(template.first(), 1, Long::plus)
+
+        return letterCounts.values.let { it.maxOrNull()!! - it.minOrNull()!! }
+    }
+
+    fun part1(input: List<String>): Long = getPolymerLetterCounts(input, 10)
+
+    fun part2(input: List<String>): Long = getPolymerLetterCounts(input, 40)
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day14_test")
+    check(Day14.part1(testInput) == 1588L)
+    check(Day14.part2(testInput) == 2188189693529L)
+
+    val input = readInputAsLines("Day14")
+    println(Day14.part1(input))
+    println(Day14.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day15.kt b/aoc-2021-kotlin/src/Day15.kt
new file mode 100644
index 0000000..6d0de5c
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day15.kt
@@ -0,0 +1,117 @@
+import java.util.*
+
+object Day15 {
+    private 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 (array[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
+        }
+    }
+
+    private 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)
+            }
+        }
+
+        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 part1(input: List<String>): Int = Matrix.fromInput(input).dijkstra()
+
+    fun part2(input: List<String>): Int = Matrix.fromInput(input).expand().dijkstra()
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day15_test")
+    check(Day15.part1(testInput) == 40)
+    check(Day15.part2(testInput) == 315)
+
+    val input = readInputAsLines("Day15")
+    println(Day15.part1(input))
+    println(Day15.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day16.kt b/aoc-2021-kotlin/src/Day16.kt
new file mode 100644
index 0000000..d11219d
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day16.kt
@@ -0,0 +1,161 @@
+object Day16 {
+    private sealed class Packet(
+        private val bits: Int,
+        protected val version: Int,
+    ) {
+        private class Literal(
+            bits: Int,
+            version: Int,
+            private val literalValue: Long,
+        ) : Packet(bits, version) {
+            override fun versionSum(): Int = version
+
+            override val value: Long
+                get() = literalValue
+        }
+
+        private class Operator(
+            bits: Int,
+            version: Int,
+            private val typeId: Int,
+            private val subpackets: List<Packet>,
+        ) : Packet(bits, version) {
+            override fun versionSum(): Int = version + subpackets.sumOf { it.versionSum() }
+
+            override val value: Long
+                get() = when (typeId) {
+                    0 -> subpackets.sumOf { it.value }
+                    1 -> subpackets.fold(1) { acc, packet -> acc * packet.value }
+                    2 -> subpackets.minOf { it.value }
+                    3 -> subpackets.maxOf { it.value }
+                    5, 6, 7 -> {
+                        val (first, second) = subpackets.map { it.value }
+
+                        if (when (typeId) {
+                                5 -> first > second
+                                6 -> first < second
+                                7 -> first == second
+                                else -> false
+                            }
+                        ) {
+                            1
+                        } else {
+                            0
+                        }
+                    }
+
+                    else -> throw IllegalStateException("Illegal packet type id.")
+                }
+        }
+
+        abstract fun versionSum(): Int
+
+        abstract val value: Long
+
+        companion object {
+            fun parse(bitQueue: ArrayDeque<Char>): Packet {
+                var packetBits = 0
+
+                fun takeBits(n: Int): Int {
+                    packetBits += n
+                    return (0 until n)
+                        .joinToString("") { bitQueue.removeFirst().toString() }
+                        .toInt(2)
+                }
+
+                val version = takeBits(3)
+
+                when (val typeId = takeBits(3)) {
+                    4 -> { // Literal packet
+                        var literalValue = 0L
+                        while (true) {
+                            val groupHeader = takeBits(1)
+                            val groupValue = takeBits(4)
+
+                            literalValue = (literalValue shl 4) + groupValue
+
+                            if (groupHeader == 0) {
+                                break
+                            }
+                        }
+
+                        return Literal(packetBits, version, literalValue)
+                    }
+
+                    else -> { // Operator packet
+                        val subpackets = mutableListOf<Packet>()
+
+                        when (takeBits(1)) {
+                            0 -> {
+                                val subpacketLength = takeBits(15)
+
+                                var currentSubpacketLength = 0
+                                while (currentSubpacketLength < subpacketLength) {
+                                    val subpacket = parse(bitQueue)
+                                    currentSubpacketLength += subpacket.bits
+                                    subpackets.add(subpacket)
+                                }
+                            }
+
+                            1 -> {
+                                val subpacketCount = takeBits(11)
+
+                                repeat(subpacketCount) {
+                                    subpackets.add(parse(bitQueue))
+                                }
+                            }
+
+                            else -> throw IllegalStateException("Illegal length type id.")
+                        }
+
+                        packetBits += subpackets.sumOf { it.bits }
+
+                        return Operator(packetBits, version, typeId, subpackets)
+                    }
+                }
+            }
+        }
+    }
+
+    private fun parse(input: String): Packet {
+        val bitQueue = ArrayDeque(
+            input
+                .flatMap {
+                    it
+                        .toString()
+                        .toInt(16)
+                        .toString(2)
+                        .padStart(4, '0')
+                        .toList()
+                }
+        )
+
+        return Packet.parse(bitQueue)
+    }
+
+    fun part1(input: String): Int = parse(input).versionSum()
+
+    fun part2(input: String): Long = parse(input).value
+}
+
+
+fun main() {
+    check(Day16.part1("8A004A801A8002F478") == 16)
+    check(Day16.part1("620080001611562C8802118E34") == 12)
+    check(Day16.part1("C0015000016115A2E0802F182340") == 23)
+    check(Day16.part1("A0016C880162017C3686B18A3D4780") == 31)
+
+    check(Day16.part2("C200B40A82") == 3L)
+    check(Day16.part2("04005AC33890") == 54L)
+    check(Day16.part2("880086C3E88112") == 7L)
+    check(Day16.part2("CE00C43D881120") == 9L)
+    check(Day16.part2("D8005AC2A8F0") == 1L)
+    check(Day16.part2("F600BC2D8F") == 0L)
+    check(Day16.part2("9C005AC2F8F0") == 0L)
+    check(Day16.part2("9C0141080250320F1802104A08") == 1L)
+
+
+    val input = readInputAsString("Day16")
+    println(Day16.part1(input))
+    println(Day16.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day17.kt b/aoc-2021-kotlin/src/Day17.kt
new file mode 100644
index 0000000..5e0170b
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day17.kt
@@ -0,0 +1,62 @@
+import kotlin.math.max
+import kotlin.math.sign
+
+object Day17 {
+    data class Target(val left: Int, val right: Int, val bottom: Int, val top: Int)
+
+    private class Probe(private var vel: Pos2D, private val target: Target) {
+        companion object {
+            fun search(target: Target): Pair<Int, Int> {
+                var highest = 0
+                var count = 0
+
+                for (vx in 0..1000) {
+                    for (vy in -1000..1000) {
+                        val probe = Probe(Pos2D(vx, vy), target)
+                        var currentHighest = 0
+
+                        while (probe.canHitTarget) {
+                            probe.step()
+                            currentHighest = max(currentHighest, probe.pos.y)
+
+                            if (probe.isInTarget) {
+                                count++
+                                highest = max(highest, currentHighest)
+                                break
+                            }
+                        }
+                    }
+                }
+
+                return highest to count
+            }
+        }
+
+        private var pos = Pos2D(0, 0)
+
+        private fun step() {
+            pos += vel
+            vel = vel.copy(x = vel.x - vel.x.sign, y = vel.y - 1)
+        }
+
+        private val canHitTarget
+            get() = pos.y > target.bottom
+
+        private val isInTarget
+            get() = pos.x in target.left..target.right && pos.y in target.bottom..target.top
+    }
+
+    fun bothParts(input: Target) = Probe.search(input)
+}
+
+fun main() {
+    val testInput = Day17.Target(20, 30, -10, -5)
+    val testOutput = Day17.bothParts(testInput)
+    check(testOutput.first == 45)
+    check(testOutput.second == 112)
+
+    val input = Day17.Target(192, 251, -89, -59)
+    val output = Day17.bothParts(input)
+    println(output.first)
+    println(output.second)
+}
diff --git a/aoc-2021-kotlin/src/Day18.kt b/aoc-2021-kotlin/src/Day18.kt
new file mode 100644
index 0000000..84575b7
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day18.kt
@@ -0,0 +1,137 @@
+import kotlin.math.ceil
+import kotlin.math.floor
+
+object Day18 {
+    private class SnailfishNum private constructor(private val data: MutableList<Entry>) {
+        private data class Entry(var num: Int, val depth: Int)
+
+        companion object {
+            fun parse(input: String): SnailfishNum {
+                var depth = 0
+                val list = mutableListOf<Entry>()
+
+                for (char in input) {
+                    when (char) {
+                        '[' -> depth += 1
+                        ']' -> depth -= 1
+                        ',' -> {}
+                        else -> list.add(Entry(char.toString().toInt(), depth))
+                    }
+                }
+
+                return SnailfishNum(list)
+            }
+        }
+
+        private val shouldExplode
+            get() = data
+                .zipWithNext()
+                .any { it.first.depth == it.second.depth && it.first.depth >= 5 }
+
+        private val shouldSplit
+            get() = data.any { it.num >= 10 }
+
+        private fun explode() {
+            val (leftIndex, rightIndex) = data
+                .zipWithNext()
+                .indexOfFirst { it.first.depth == it.second.depth && it.first.depth >= 5 }
+                .let { it to it + 1 }
+
+            if (leftIndex - 1 in data.indices) {
+                data[leftIndex - 1].num += data[leftIndex].num
+            }
+
+            if (rightIndex + 1 in data.indices) {
+                data[rightIndex + 1].num += data[rightIndex].num
+            }
+
+            data[leftIndex] = Entry(0, data[leftIndex].depth - 1)
+            data.removeAt(rightIndex)
+        }
+
+        private fun split() {
+            val index = data.indexOfFirst { it.num >= 10 }
+            val depth = data[index].depth
+
+            val half = data[index].num / 2.0
+            val roundedDown = floor(half).toInt()
+            val roundedUp = ceil(half).toInt()
+
+            data[index] = Entry(roundedUp, depth + 1)
+            data.add(index, Entry(roundedDown, depth + 1))
+        }
+
+        private fun reduce() {
+            while (true) {
+                if (shouldExplode) {
+                    explode()
+                } else if (shouldSplit) {
+                    split()
+                } else {
+                    break
+                }
+            }
+        }
+
+        fun magnitude(): Int {
+            val dataCopy = data.toMutableList()
+
+            while (dataCopy.size > 1) {
+                val maxDepth = dataCopy.maxOf { it.depth }
+
+                val (leftIndex, rightIndex) = dataCopy
+                    .zipWithNext()
+                    .indexOfFirst { it.first.depth == it.second.depth && it.first.depth == maxDepth }
+                    .let { it to it + 1 }
+
+                dataCopy[leftIndex] = Entry(
+                    dataCopy[leftIndex].num * 3 + dataCopy[rightIndex].num * 2,
+                    maxDepth - 1
+                )
+                dataCopy.removeAt(rightIndex)
+            }
+
+            return dataCopy.first().num
+        }
+
+        operator fun plus(other: SnailfishNum): SnailfishNum =
+            SnailfishNum(
+                (this.data + other.data).map { Entry(it.num, it.depth + 1) }.toMutableList()
+            ).also { it.reduce() }
+    }
+
+    private fun <T> combinations(items: Sequence<T>): Sequence<Pair<T, T>> =
+        sequence {
+            items.forEach { a ->
+                items.forEach { b ->
+                    yield(a to b)
+                }
+            }
+        }
+
+    fun part1(input: List<String>): Int =
+        input
+            .asSequence()
+            .map(SnailfishNum::parse)
+            .reduce(SnailfishNum::plus)
+            .magnitude()
+
+    fun part2(input: List<String>): Int =
+        combinations(
+            input
+                .asSequence()
+                .map(SnailfishNum::parse)
+        )
+            .filter { it.first !== it.second }
+            .maxOf { (it.first + it.second).magnitude() }
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day18_test")
+    check(Day18.part1(testInput) == 4140)
+    check(Day18.part2(testInput) == 3993)
+
+    val input = readInputAsLines("Day18")
+    println(Day18.part1(input))
+    println(Day18.part2(input))
+}
diff --git a/aoc-2021-kotlin/src/Day24.kt b/aoc-2021-kotlin/src/Day24.kt
new file mode 100644
index 0000000..9ca300c
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day24.kt
@@ -0,0 +1,231 @@
+object Day24 {
+    @JvmInline
+    private value class Register private constructor(val address: Int) {
+        companion object {
+            val W = Register(0)
+            val X = Register(1)
+            val Y = Register(2)
+            val Z = Register(3)
+
+            fun fromString(string: String) = when (string) {
+                "x" -> X
+                "y" -> Y
+                "z" -> Z
+                "w" -> W
+                else -> throw IllegalArgumentException(string)
+            }
+        }
+    }
+
+    private sealed class Instruction {
+        companion object {
+            fun fromString(string: String) = string.split(" ").let { parts ->
+                val operatorString = parts[0]
+                val target = Register.fromString(parts[1])
+
+                if (operatorString == "inp") {
+                    Input(target)
+                } else {
+                    val opcode = when (operatorString) {
+                        "add" -> Binary.Opcode.ADD
+                        "mul" -> Binary.Opcode.MUL
+                        "div" -> Binary.Opcode.DIV
+                        "mod" -> Binary.Opcode.MOD
+                        "eql" -> Binary.Opcode.EQL
+                        else -> throw IllegalArgumentException(operatorString)
+                    }
+
+                    val source = when (val parsed = parts[2].toLongOrNull()) {
+                        is Long -> Source.Literal(parsed)
+                        else -> Source.Memory(Register.fromString(parts[2]))
+                    }
+
+                    Binary(opcode, target, source)
+                }
+            }
+        }
+
+        data class Input(val register: Register) : Instruction()
+        data class Binary(val opcode: Opcode, val a: Register, val b: Source) : Instruction() {
+            enum class Opcode {
+                ADD, MUL, DIV, MOD, EQL
+            }
+        }
+
+        sealed class Source {
+            data class Memory(val register: Register) : Source()
+            data class Literal(val value: Long) : Source()
+        }
+    }
+
+    private data class ALU(private val memory: LongArray) {
+        @Suppress("unused")
+        val w get() = memory[Register.W.address]
+
+        @Suppress("unused")
+        val x get() = memory[Register.X.address]
+
+        @Suppress("unused")
+        val y get() = memory[Register.Y.address]
+
+        @Suppress("unused")
+        val z get() = memory[Register.Z.address]
+
+        fun toMutable() = MutableALU(memory.clone())
+
+        override fun equals(other: Any?): Boolean {
+            if (this === other) return true
+            if (javaClass != other?.javaClass) return false
+            return memory.contentEquals((other as ALU).memory)
+        }
+
+        override fun hashCode() = memory.contentHashCode()
+    }
+
+    private class MutableALU(private val memory: LongArray) {
+        constructor() : this(LongArray(4) { 0L })
+
+        fun toImmutable() = ALU(memory.clone())
+
+        fun executeBatch(batch: List<Instruction.Binary>) {
+            batch.forEach {
+                memory[it.a.address] = when (it.opcode) {
+                    Instruction.Binary.Opcode.ADD -> fetch(it.a) + fetch(it.b)
+                    Instruction.Binary.Opcode.MUL -> fetch(it.a) * fetch(it.b)
+                    Instruction.Binary.Opcode.DIV -> fetch(it.a) / fetch(it.b)
+                    Instruction.Binary.Opcode.MOD -> fetch(it.a) % fetch(it.b)
+                    Instruction.Binary.Opcode.EQL -> if (fetch(it.a) == fetch(it.b)) 1L else 0L
+                }
+            }
+        }
+
+        fun feedInput(input: Instruction.Input, value: Long) {
+            memory[input.register.address] = value
+        }
+
+        private fun fetch(register: Register) = memory[register.address]
+
+        private fun fetch(source: Instruction.Source) = when (source) {
+            is Instruction.Source.Literal -> source.value
+            is Instruction.Source.Memory -> memory[source.register.address]
+        }
+    }
+
+    private class Program private constructor(private val parts: List<Part>) {
+        companion object {
+            fun compileFrom(inputs: List<String>): Program {
+                val instructionQueue = inputs.map(Instruction::fromString)
+
+                val parts = mutableListOf<Part>()
+
+                val currentStep = mutableListOf<Instruction.Binary>()
+                var currentInput: Instruction.Input? = null
+
+                instructionQueue.forEach {
+                    when (it) {
+                        is Instruction.Input -> {
+                            parts.add(Part(currentInput, currentStep.toList()))
+
+                            currentStep.clear()
+                            currentInput = it
+                        }
+
+                        is Instruction.Binary -> currentStep.add(it)
+                    }
+                }
+
+                parts.add(Part(currentInput, currentStep.toList()))
+
+                return Program(parts)
+            }
+        }
+
+        private data class Part(val input: Instruction.Input?, val instructionBatch: List<Instruction.Binary>)
+
+        private data class Checkpoint(val partNumber: Int, val alu: ALU)
+
+        fun findInputDigits(
+            digitRange: IntProgression = 0..9,
+            successCondition: (ALU) -> Boolean
+        ): Sequence<Long> {
+            val cache = mutableSetOf<Checkpoint>()
+            val matchingCheckpoints = mutableSetOf<Checkpoint>()
+
+            fun solveRecursively(checkpoint: Checkpoint, accumulator: Long): Sequence<Long> = sequence {
+                if (cache.contains(checkpoint)) return@sequence
+
+                if (checkpoint.partNumber == parts.size) {
+                    if (successCondition(checkpoint.alu)) {
+                        yield(accumulator)
+                        val statesOfCurrent = inputStateSequence(accumulator).toSet()
+                        matchingCheckpoints.addAll(statesOfCurrent)
+                        cache.removeAll(statesOfCurrent)
+                    }
+
+                    return@sequence
+                }
+
+                digitRange.forEach {
+                    yieldAll(
+                        solveRecursively(
+                            Checkpoint(
+                                checkpoint.partNumber + 1,
+                                executePart(checkpoint.partNumber, checkpoint.alu, it.toLong()),
+                            ),
+                            accumulator * 10 + it,
+                        )
+                    )
+                }
+
+                if (!matchingCheckpoints.contains(checkpoint)) cache.add(checkpoint)
+
+                Runtime.getRuntime().let {
+                    if (it.totalMemory().toDouble() / it.maxMemory() > 0.75) {
+                        cache.clear()
+                        it.gc()
+                    }
+                }
+            }
+
+            return solveRecursively(Checkpoint(1, executePart(0)), 0L)
+        }
+
+        private fun inputStateSequence(input: Long) = sequence {
+            var checkpoint = Checkpoint(1, executePart(0))
+            yield(checkpoint)
+
+            input.toString().toCharArray().map { it.toString().toInt() }.forEach {
+                checkpoint = Checkpoint(
+                    checkpoint.partNumber + 1,
+                    executePart(checkpoint.partNumber, checkpoint.alu, it.toLong())
+                )
+                yield(checkpoint)
+            }
+        }
+
+        private fun executePart(partNumber: Int, alu: ALU? = null, input: Long? = null): ALU {
+            val part = parts[partNumber]
+            val executor = alu?.toMutable() ?: MutableALU()
+
+            if (part.input != null && input != null)
+                executor.feedInput(part.input, input)
+
+            executor.executeBatch(part.instructionBatch)
+
+            return executor.toImmutable()
+        }
+    }
+
+    fun bothParts(input: List<String>) = Program
+        .compileFrom(input)
+        .findInputDigits(digitRange = 9 downTo 1) { it.z == 0L }
+        .let { it.first() to it.last() }
+}
+
+fun main() {
+    val input = readInputAsLines("Day24")
+    val output = Day24.bothParts(input)
+
+    println(output.first)
+    println(output.second)
+}
diff --git a/aoc-2021-kotlin/src/Day25.kt b/aoc-2021-kotlin/src/Day25.kt
new file mode 100644
index 0000000..36a2f75
--- /dev/null
+++ b/aoc-2021-kotlin/src/Day25.kt
@@ -0,0 +1,87 @@
+object Day25 {
+    private class SeaCucumbers(private val width: Int, private val height: Int, private val matrix: Array<SeaTile>) {
+        companion object {
+            fun fromLines(lines: List<String>) =
+                Pos2D(
+                    lines.getOrNull(0)?.length ?: throw IllegalArgumentException("Sea must have a non-zero height!"),
+                    lines.size
+                ).let { size ->
+                    SeaCucumbers(size.x, size.y, Array(size.x * size.y) {
+                        when (val char = lines[it / size.x][it % size.x]) {
+                            '>' -> SeaTile.Cucumber.EastFacing
+                            'v' -> SeaTile.Cucumber.SouthFacing
+                            '.' -> SeaTile.EmptyTile
+                            else -> throw IllegalArgumentException("Found '$char', expected '>', 'v' or '.'!")
+                        }
+                    })
+                }
+        }
+
+        private sealed class SeaTile {
+            object EmptyTile : SeaTile()
+            sealed class Cucumber : SeaTile() {
+                object EastFacing : Cucumber()
+                object SouthFacing : Cucumber()
+            }
+        }
+
+        private fun moveIndex(index: Int, offset: Pos2D) =
+            ((index / width + offset.y) % height) * width + (index + offset.x) % width
+
+        private inline fun <reified T : SeaTile.Cucumber> stepDirection(pos: Pos2D) {
+            matrix
+                .asSequence()
+                .withIndex()
+                .map { (index, seaTile) ->
+                    val nextIndex = moveIndex(index, pos)
+                    if (seaTile is T && matrix[nextIndex] is SeaTile.EmptyTile) {
+                        index to nextIndex
+                    } else {
+                        null
+                    }
+                }
+                .filterNotNull()
+                .toList()
+                .forEach { (index, nextIndex) ->
+                    matrix[nextIndex] = matrix[index].also { matrix[index] = SeaTile.EmptyTile }
+                }
+        }
+
+        private fun stepOnce() {
+            stepDirection<SeaTile.Cucumber.EastFacing>(Pos2D(1, 0))
+            stepDirection<SeaTile.Cucumber.SouthFacing>(Pos2D(0, 1))
+        }
+
+        fun simulate(): Int {
+            var count = 0
+
+            do {
+                val previousHashCode = matrix.contentHashCode()
+                stepOnce()
+                count++
+            } while (matrix.contentHashCode() != previousHashCode)
+
+            return count
+        }
+
+        override fun toString(): String = matrix
+            .withIndex()
+            .joinToString("") { (index, seaTile) ->
+                when (seaTile) {
+                    SeaTile.Cucumber.EastFacing -> ">"
+                    SeaTile.Cucumber.SouthFacing -> "v"
+                    SeaTile.EmptyTile -> "."
+                } + (if (index % width == width - 1) "\n" else "")
+            }
+    }
+
+    fun singlePart(input: List<String>) = SeaCucumbers.fromLines(input).simulate()
+}
+
+fun main() {
+    val testInput = readInputAsLines("Day25_test")
+    check(Day25.singlePart(testInput) == 58)
+
+    val input = readInputAsLines("Day25")
+    println(Day25.singlePart(input))
+}
diff --git a/aoc-2021-kotlin/src/Utils.kt b/aoc-2021-kotlin/src/Utils.kt
new file mode 100644
index 0000000..f0a420b
--- /dev/null
+++ b/aoc-2021-kotlin/src/Utils.kt
@@ -0,0 +1,32 @@
+import java.io.File
+
+fun readInputAsLines(name: String): List<String> = File("src", "$name.txt").readLines()
+
+fun readInputAsString(name: String): String = File("src", "$name.txt").readText()
+
+fun readInputAsNumbers(name: String): List<Int> = readInputAsLines(name).map(String::toInt)
+
+fun readInputAsBitLists(name: String): List<List<Int>> =
+    readInputAsLines(name)
+        .map { binaryString -> binaryString.toList().map { bit -> bit.toString().toInt() } }
+
+data class Pos2D(val x: Int, val y: Int) {
+    companion object {
+        val directions4 = listOf(Pos2D(0, 1), Pos2D(1, 0), Pos2D(0, -1), Pos2D(-1, 0))
+        val directions8 = directions4 + listOf(
+            Pos2D(1, 1),
+            Pos2D(1, -1),
+            Pos2D(-1, -1),
+            Pos2D(-1, 1),
+        )
+    }
+
+    operator fun plus(other: Pos2D) = Pos2D(x + other.x, y + other.y)
+}
+
+fun parseToMap(input: List<String>): Map<Pos2D, Int> =
+    input.flatMapIndexed { y, line ->
+        line.mapIndexed { x, char ->
+            Pos2D(x, y) to char.toString().toInt()
+        }
+    }.toMap()