-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day18.kt
82 lines (70 loc) · 2.67 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
package aoc2021.day18
class Node(
var left: Node? = null,
var right: Node? = null,
var value: Int? = null,
var parent: Node? = null,
) {
val magnitude: Int get() = value ?: (3 * left!!.magnitude + 2 * right!!.magnitude)
operator fun plus(other: Node): Node {
return Node(this, other).apply {
left?.parent = this
right?.parent = this
reduce()
}
}
private fun reduce() {
findNodeToExplode()?.apply {
val (x, y) = left?.value!! to right?.value!!
left = null
right = null
findNodeOnLeft()?.let { it.value = it.value!! + x }
findNodeOnRight()?.let { it.value = it.value!! + y }
value = 0
}
findNodeToSplit()?.apply {
val (a, b) = value!!.let { it / 2 to (it + 1) / 2 }
left = Node(value = a, parent = this)
right = Node(value = b, parent = this)
value = null
}
}
private fun findNodeToExplode(d: Int = 0): Node? =
if (value == null && d >= 4) this else left?.findNodeToExplode(d + 1) ?: right?.findNodeToExplode(d + 1)
private fun findNodeToSplit(): Node? =
if ((value ?: 0) >= 10) this else left?.findNodeToSplit() ?: right?.findNodeToSplit()
private fun findNodeOnLeft(): Node? {
if (value != null) return this
if (this == parent?.left) return parent!!.findNodeOnLeft()
if (this == parent?.right) return parent!!.left?.findRightMostNode()
return null
}
private fun findNodeOnRight(): Node? {
if (value != null) return this
if (this == parent?.left) return parent!!.right?.findLeftMostNode()
if (this == parent?.right) return parent!!.findNodeOnRight()
return null
}
private fun findLeftMostNode(): Node? = if (value != null) this else left?.findLeftMostNode()
private fun findRightMostNode(): Node? = if (value != null) this else right?.findRightMostNode()
}
fun getNode(input: String): Node {
var i = 0
fun parse(parent: Node): Node = Node(parent = parent).apply {
if (input[i++] == '[') {
left = parse(this).also { i++ }
right = parse(this).also { i++ }
} else value = input[i - 1].digitToInt()
}
return parse(Node())
}
fun part1(input: List<String>): Int {
return input.map(::getNode).reduce(Node::plus).magnitude
}
fun part2(input: List<String>): Int {
return input.indices.flatMap { i -> input.indices.map { j -> i to j } }
.filter { (i, j) -> i != j }
.maxOf { (i, j) -> (getNode(input[i]) + getNode(input[j])).magnitude }
}