-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day16.kt
89 lines (75 loc) · 3.54 KB
/
Day16.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
package com.github.ephemient.aoc2021
/** [Day 16](https://adventofcode.com/2021/day/16): Packet Decoder */
@ExperimentalStdlibApi
class Day16(lines: List<String>) {
private val packet = parsePacket(lines.single().iterator().hexBitsIterator())
fun part1(): Int = DeepRecursiveFunction<Packet, Int> { packet ->
when (packet) {
is Packet.Literal -> packet.version
is Packet.Operator -> packet.version + packet.children.sumOf { callRecursive(it) }
}
}(packet)
fun part2(): Long = DeepRecursiveFunction<Packet, Long> { packet ->
when (packet) {
is Packet.Literal -> packet.value
is Packet.Operator -> when (packet.type) {
0 -> packet.children.sumOf { callRecursive(it) }
1 -> packet.children.fold(1L) { acc, child -> acc * callRecursive(child) }
2 -> packet.children.minOf { callRecursive(it) }
3 -> packet.children.maxOf { callRecursive(it) }
5 -> if (callRecursive(packet.children[0]) > callRecursive(packet.children[1])) 1 else 0
6 -> if (callRecursive(packet.children[0]) < callRecursive(packet.children[1])) 1 else 0
7 -> if (callRecursive(packet.children[0]) == callRecursive(packet.children[1])) 1 else 0
else -> TODO()
}
}
}(packet)
private sealed class Packet {
abstract val version: Int
data class Literal(override val version: Int, val value: Long) : Packet()
data class Operator(override val version: Int, val type: Int, val children: List<Packet>) : Packet()
}
companion object {
private val parsePacket = DeepRecursiveFunction<BooleanIterator, Packet> { iterator ->
val version = iterator.nextInt(3)
val type = iterator.nextInt(3)
if (type == 4) {
var value = 0L
do {
val continuation = iterator.nextBoolean()
value = 16 * value + iterator.nextInt(4)
} while (continuation)
Packet.Literal(version, value)
} else {
val children = if (iterator.nextBoolean()) {
List(iterator.nextInt(11)) { callRecursive(iterator) }
} else {
val childIterator = iterator.take(iterator.nextInt(15))
buildList {
while (childIterator.hasNext()) add(callRecursive(childIterator))
}
}
Packet.Operator(version, type, children)
}
}
private fun CharIterator.hexBitsIterator(): BooleanIterator = object : BooleanIterator() {
private var buf = 0
private var i = -1
override fun hasNext(): Boolean = i >= 0 || this@hexBitsIterator.hasNext()
override fun nextBoolean(): Boolean {
if (i < 0) {
buf = nextChar().digitToInt(16)
i = 3
}
return buf shr i-- and 1 != 0
}
}
private fun BooleanIterator.take(n: Int): BooleanIterator = object : BooleanIterator() {
private var remaining = n
override fun hasNext(): Boolean = remaining > 0 && this@take.hasNext()
override fun nextBoolean(): Boolean = this@take.nextBoolean().also { remaining-- }
}
private fun BooleanIterator.nextInt(bits: Int): Int =
(1..bits).fold(0) { acc, _ -> 2 * acc + if (nextBoolean()) 1 else 0 }
}
}