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
124
125
126
127
128
129
130
131
132
133
134
135
136
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))
}
|