blob: 09c688adac6f2ec89f2bda5e74817ca49954df15 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
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() }
}
fun part1(input: List<String>): Int =
input
.asSequence()
.map(SnailfishNum::parse)
.reduce(SnailfishNum::plus)
.magnitude()
fun part2(input: List<String>): Int = combinations(input.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))
}
|
