-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day19.kt
119 lines (102 loc) · 4.31 KB
/
Day19.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package io.dmitrijs.aoc2023
import io.dmitrijs.aoc2023.Day19.Expr.Accept
import io.dmitrijs.aoc2023.Day19.Expr.Compare
import io.dmitrijs.aoc2023.Day19.Expr.Jump
import io.dmitrijs.aoc2023.Day19.Expr.Reject
import kotlin.math.max
import kotlin.math.min
private typealias VariableRanges = List<Pair<Int, Int>>
class Day19(input: String) {
private val environments = input.substringAfter("\n\n").trimEnd().lines().map { line ->
buildMap {
line.trim('{', '}').split(',').forEach { expr ->
put(expr.substringBefore('='), expr.substringAfter('=').toLong())
}
}
}
private val workflowMap = input.substringBefore("\n\n").lines().associate { line ->
line.substringBefore('{') to line.substringAfter('{').trimEnd('}').split(',')
}
fun puzzle1() = environments.sumOf { env ->
fun Compare.predicate() = when (op) {
'>' -> env.getValue(name) > value
'<' -> env.getValue(name) < value
else -> error("Invalid operation $op supplied.")
}
var accept = false
val expressions = workflowMap
.getValue("in")
.map { it.toExpr() }
.toMutableList()
do {
when (val expr = expressions.removeFirst()) {
is Accept -> accept = true
is Reject -> break
is Compare -> if (expr.predicate()) {
expressions.clear()
expressions.add(expr.expr)
}
is Jump -> {
expressions.clear()
expressions.addAll(workflowMap.getValue(expr.next).map { it.toExpr() })
}
}
} while (!accept)
if (accept) env.values.sum() else 0L
}
fun puzzle2() = traverseRanges("in", List(4) { 1 to 4_000 })
private fun splitRanges(expr: String, ranges: VariableRanges): Pair<VariableRanges, VariableRanges> {
val (name, split) = expr
.substringBefore(':')
.split('<', '>')
.let { (n, v) -> n to v.toInt() }
val index = "xmas".indexOf(name)
val range = ranges[index]
return when {
'>' in expr -> {
val l = ranges.toMutableList().apply { this[index] = max(range.first, split + 1) to range.second }
val r = ranges.toMutableList().apply { this[index] = range.first to min(range.second, split) }
l to r
}
'<' in expr -> {
val l = ranges.toMutableList().apply { this[index] = range.first to min(range.second, split - 1) }
val r = ranges.toMutableList().apply { this[index] = max(range.first, split) to range.second }
l to r
}
else -> error("Invalid expression '$expr'.")
}
}
private fun traverseRanges(workflow: String, ranges: VariableRanges): Long = when (workflow) {
"R" -> 0L
"A" -> ranges.variations()
else -> {
var result = 0L
val expressions = workflowMap.getValue(workflow)
var currentRanges = ranges
for (index in 0..<expressions.lastIndex) {
val (left, right) = splitRanges(expressions[index], currentRanges)
if (left.variations() > 0) {
result += traverseRanges(expressions[index].substringAfter(':'), left)
}
currentRanges = right
}
result + traverseRanges(expressions.last(), currentRanges)
}
}
private fun VariableRanges.variations() = fold(1L) { acc, range ->
acc * (if (range.second < range.first) 0 else (range.second - range.first + 1))
}
private fun String.toExpr(): Expr = when {
"A" == this -> Accept
"R" == this -> Reject
">" in this -> split('>', ':').let { (name, value, next) -> Compare(name, '>', value.toLong(), next.toExpr()) }
"<" in this -> split('<', ':').let { (name, value, next) -> Compare(name, '<', value.toLong(), next.toExpr()) }
else -> Jump(this)
}
private sealed class Expr {
data object Accept : Expr()
data object Reject : Expr()
data class Jump(val next: String) : Expr()
data class Compare(val name: String, val op: Char, val value: Long, val expr: Expr) : Expr()
}
}