diff options
Diffstat (limited to 'aoc-2021-kotlin/src/Day18.kt')
-rw-r--r-- | aoc-2021-kotlin/src/Day18.kt | 137 |
1 files changed, 137 insertions, 0 deletions
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)) +} |