-
Notifications
You must be signed in to change notification settings - Fork 4
/
Day19.kt
113 lines (104 loc) · 4.59 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
package com.github.ephemient.aoc2022
import kotlinx.coroutines.Dispatchers
import kotlinx.coroutines.async
import kotlinx.coroutines.withContext
@Day
class Day19(lines: List<String>) {
private val blueprints = lines.map { line ->
val (id) = ID_PATTERN.matchAt(line, 0)!!.destructured
id.toInt() to PART_PATTERN.findAll(line).associate { partMatch ->
val (robot, costs) = partMatch.destructured
robot to COST_PATTERN.findAll(costs).associate { costMatch ->
val (cost, type) = costMatch.destructured
type to cost.toInt()
}
}
}
@Day.Part
suspend fun part1(): Int = withContext(Dispatchers.Default) {
blueprints.map { (id, blueprint) ->
async {
id * geodes(blueprint, 24).also { trace("($id, $it)") }
}
}.sumOf { it.await() }
}
@Day.Part
suspend fun part2(): Int = withContext(Dispatchers.Default) {
blueprints.take(3).map { (id, blueprint) ->
async {
geodes(blueprint, 32).also { trace("($id, $it)") }
}
}.fold(1) { acc, deferred -> acc * deferred.await() }
}
private data class State(
val robots: Map<String, Int>,
val resources: Map<String, Int>,
val time: Int,
) {
val estimate: Int = resources.get0("geode") + robots.get0("geode") * time
}
companion object {
private val ID_PATTERN = """Blueprint (\d+):""".toRegex()
private val PART_PATTERN = """Each (\w+) robot ([^.]+)[.]""".toRegex()
private val COST_PATTERN = """(?:costs | and )(\d+) (\w+)""".toRegex()
private fun <T> Map<T, Int>.get0(key: T): Int = getOrElse(key) { 0 }
@Suppress("CyclomaticComplexMethod")
private fun geodes(blueprint: Map<String, Map<String, Int>>, time: Int): Int {
val maxValues = buildMap {
for (costs in blueprint.values) {
for ((material, cost) in costs) this[material] = maxOf(this.get0(material), cost)
}
}
var best = 0
val queue = mutableListOf(State(mapOf("ore" to 1), emptyMap(), time))
while (queue.isNotEmpty()) {
val state = queue.removeLast()
if (potential(blueprint, state) < best) continue
if (state.estimate > best) best = state.estimate
for ((robot, costs) in blueprint) {
val maxValue = maxValues[robot]
if (maxValue != null && state.robots.get0(robot) >= maxValue) continue
val delta = blueprint.keys.maxOf { type ->
val demand = costs.get0(type) - state.resources.get0(type)
if (demand <= 0) {
0
} else {
val supply = state.robots.get0(type)
if (supply <= 0) Int.MAX_VALUE else (demand + supply - 1) / supply
}
}
if (delta < state.time) {
val robots = state.robots + (robot to state.robots.get0(robot) + 1)
val resources = buildMap {
putAll(state.resources)
for ((type, cost) in costs) this[type] = this.get0(type) - cost
for ((type, count) in state.robots) this[type] = this.get0(type) + count * (delta + 1)
}
queue.add(State(robots, resources, state.time - delta - 1))
}
}
}
return best
}
private fun potential(blueprint: Map<String, Map<String, Int>>, state: State): Int {
val potentialRobots = blueprint.keys.associateWithTo(mutableMapOf()) { 0 }
val potentialResources = state.resources.toMutableMap()
repeat(state.time) {
for ((robot, count) in potentialRobots) {
potentialResources[robot] = potentialResources.get0(robot) + state.robots.get0(robot) + count
}
for (entry in potentialRobots) {
val (robot, count) = entry
if (
blueprint[robot]!!.all { (type, cost) ->
potentialResources.get0(type) >= cost * (count + 1)
}
) {
entry.setValue(count + 1)
}
}
}
return potentialResources.get0("geode")
}
}
}