-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day18.kt
102 lines (95 loc) · 4.13 KB
/
Day18.kt
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
package com.github.ephemient.aoc2021
/** [Day 18](https://adventofcode.com/2021/day/18): Snailfish */
@ExperimentalStdlibApi
class Day18(lines: List<String>) {
private val snails = lines.map { it.tokens() }
fun part1(): Int = snails.reduce { x, y -> x + y }.magnitude()
fun part2(): Int = sequence {
for ((i, x) in snails.withIndex()) {
for ((j, y) in snails.withIndex()) {
if (i != j) yield(x + y)
}
}
}.maxOf { it.magnitude() }
private sealed class Token {
object Open : Token()
object Close : Token()
class Value(val value: Int) : Token()
}
companion object {
private fun String.tokens(): List<Token> = buildList {
var i = 0
DeepRecursiveFunction<Unit, Unit> {
check(this@tokens[i++] == '[')
add(Token.Open)
if (this@tokens[i].isDigit()) add(Token.Value(this@tokens[i++].digitToInt())) else callRecursive(Unit)
check(this@tokens[i++] == ',')
if (this@tokens[i].isDigit()) add(Token.Value(this@tokens[i++].digitToInt())) else callRecursive(Unit)
check(this@tokens[i++] == ']')
add(Token.Close)
}(Unit)
check(i == this@tokens.length)
}
@Suppress(
"ComplexMethod", "NestedBlockDepth", "LoopWithTooManyJumpStatements",
"UnusedPrivateMember", // Detekt false-positive
)
private operator fun List<Token>.plus(other: List<Token>): List<Token> =
ArrayList<Token>(this.size + other.size + 2).apply {
add(Token.Open)
addAll(this@plus)
addAll(other)
add(Token.Close)
loop@while (true) {
var depth = 0
for (i in 0 until this.size - 4) {
if (depth > 3 && this[i] == Token.Open && this[i + 3] == Token.Close) {
val lhs = this[i + 1]
val rhs = this[i + 2]
if (lhs is Token.Value && rhs is Token.Value) {
this[i] = Token.Value(0)
this.subList(i + 1, i + 4).clear()
for (j in i - 1 downTo 0) {
val token = this[j] as? Token.Value ?: continue
this[j] = Token.Value(token.value + lhs.value)
break
}
for (j in i + 1 until this.size) {
val token = this[j] as? Token.Value ?: continue
this[j] = Token.Value(token.value + rhs.value)
break
}
continue@loop
}
}
when (this[i]) {
Token.Open -> depth++
Token.Close -> depth--
else -> {}
}
}
for ((i, token) in this.withIndex()) {
if (token is Token.Value && token.value > 9) {
this[i] = Token.Open
this.addAll(
i + 1,
listOf(Token.Value(token.value / 2), Token.Value((token.value + 1) / 2), Token.Close),
)
continue@loop
}
}
break@loop
}
}
private fun List<Token>.magnitude(): Int {
var i = 0
return DeepRecursiveFunction<Unit, Int> {
when (val token = this@magnitude[i++]) {
is Token.Open -> (3 * callRecursive(Unit) + 2 * callRecursive(Unit)).also { i++ }
is Token.Value -> token.value
else -> TODO()
}
}.invoke(Unit)
}
}
}