-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day20.kt
153 lines (136 loc) · 5.53 KB
/
Day20.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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
package com.github.ephemient.aoc2023
class Day20(input: String) {
private val machines: Map<String, Pair<Set<String>, Type?>>
private val dependencies: Map<String, Set<String>>
init {
val machines = mutableMapOf<String, Pair<Set<String>, Type?>>()
val dependencies = mutableMapOf<String, MutableSet<String>>()
for (line in input.lines()) {
val (lhs, rhs) = line.split(" -> ", limit = 2).takeIf { it.size == 2 } ?: continue
val (type, key) = when {
lhs.startsWith('%') -> Type.FlipFlop to lhs.drop(1)
lhs.startsWith('&') -> Type.Conjunction to lhs.drop(1)
else -> null to lhs
}
val dsts = rhs.split(", ").toSet()
machines[key] = dsts to type
for (dst in dsts) dependencies.getOrPut(dst) { mutableSetOf() }.add(key)
}
this.machines = machines
this.dependencies = dependencies
}
fun part1(): Int {
val state = machines.mapValues { (key, value) ->
value.second.createState(dependencies[key] ?: emptySet())
}
var x = 0
var y = 0
repeat(1000) {
val queue = ArrayDeque<Triple<String, String, Boolean>>()
queue.add(Triple("button", "broadcaster", false))
@Suppress("LoopWithTooManyJumpStatements")
while (true) {
val (src, key, value) = queue.removeFirstOrNull() ?: break
if (value) x++ else y++
val newValue = state[key]?.onPulse(src, value) ?: continue
machines.getValue(key).first.mapTo(queue) { Triple(key, it, newValue) }
}
}
return x * y
}
@Suppress("CyclomaticComplexMethod", "NestedBlockDepth", "ReturnCount")
fun part2(): Long? {
val conjunction = dependencies["rx"]?.singleOrNull()
?.takeIf { machines[it]?.second == Type.Conjunction }
?: return null
val subsets = (dependencies[conjunction] ?: emptySet()).associateWith { dst ->
buildSet {
val stack = mutableListOf(dst)
@Suppress("LoopWithTooManyJumpStatements")
while (true) {
val key = stack.removeLastOrNull() ?: break
if (!add(key)) continue
dependencies[key]?.let { stack.addAll(it) }
}
}
}
subsets.values.toList().let { values ->
for (i in values.indices) {
for (j in i + 1..values.lastIndex) {
if (values[i].intersect(values[j]).singleOrNull() != "broadcaster") {
return null
}
}
}
}
return subsets.entries.fold(1) { acc: Long, (dst, subset) ->
val state = machines.filterKeys { it in subset }.mapValues { (key, value) ->
value.second.createState(dependencies[key] ?: emptySet())
}
val seen = mutableMapOf<Map<String, Boolean?>, Int>()
var hadOutput = false
while (true) {
var hasOutput = false
val queue = ArrayDeque<Triple<String, String, Boolean>>()
queue.add(Triple("button", "broadcaster", false))
@Suppress("LoopWithTooManyJumpStatements")
while (true) {
val (src, key, value) = queue.removeFirstOrNull() ?: break
val newValue = state[key]?.onPulse(src, value) ?: continue
if (newValue && key == dst) hasOutput = true
machines.getValue(key).first
.filter { it in subset }
.mapTo(queue) { Triple(key, it, newValue) }
}
val snapshot = state.mapValues { it.value.value }
if (snapshot in seen) {
if (!hadOutput) return null
val i = seen.getValue(snapshot)
if (i != 0) return null
break
}
seen[snapshot] = seen.size
if (hadOutput) return null
hadOutput = hasOutput
}
lcm(acc, seen.size.toLong())
}
}
private sealed interface State {
object Default : State {
override val value: Boolean?
get() = null
override fun onPulse(key: String, value: Boolean): Boolean = value
}
class FlipFlop : State {
override var value = false
private set
override fun onPulse(key: String, value: Boolean): Boolean? = if (value) {
null
} else {
!this.value
}?.also { this.value = it }
}
class Conjunction(keys: Set<String>) : State {
private val state = keys.associateWithTo(mutableMapOf()) { false }
override val value: Boolean
get() = !state.values.all { it }
override fun onPulse(key: String, value: Boolean): Boolean {
state[key] = value
return this.value
}
}
val value: Boolean?
fun onPulse(key: String, value: Boolean): Boolean?
}
private enum class Type {
FlipFlop, Conjunction,
}
companion object {
private fun Type?.createState(keys: Set<String>): State = when (this) {
null -> State.Default
Type.FlipFlop -> State.FlipFlop()
Type.Conjunction -> State.Conjunction(keys)
}
}
}