https://kotlinlang.org logo
Join Slack
Powered by
Day 20 help - no solutions
# advent-of-code
p
Day 20 help - no solutions
Can someone hint me towards problematic inputs? My solution passes the two test inputs but for the real input my result is too low.
r
I had a too low solution for part 1 too, in my case it was because, simply put, I maintained a 
Set
of resulting pulses while processing the input pulses, but as it turned out it needed to be a 
List
It worked on the examples but not on the input, like in your case 😅
j
Be sure to read the instructions carefully,
Copy code
Pulses are always processed in the order they are sent. So, if a pulse is sent to modules a, b, and c, and then module a processes its pulse and sends more pulses, the pulses sent to modules b and c would have to be handled first.
Was what got m in my first try, worked on examples, but I had processed all resulting pulses from a down until nothing happened anymore
p
r
I think I see your issue. Basically in your code, when a conjunction receives a pulse, it immediately updates its state and checks if all the inputs are high to decide whether to send a pulse, while actually, there might be a pulse further in the queue that updates one of these inputs (which would have led to a different output pulse)
basically, your queue would need to be batched, if you know what I mean
v
Copy code
is Module.Conjunction -> {
            module.memory[instruction.from] = instruction.low
            val hasOnlyHighPulses = module.memory.all { it.value }
@Paul Woitaschek didn't you mix 'low' and 'it.value' here? looks like it means an opposite things
module.memory == true for high values, isn't it?
p
The memory is a Map<String, Boolean>. By doing .all { it.value } I’m checking if all values are positive (=high pulses)
v
Yes, but you assign it first to 'true' if is low (module.memory[instruction.from] = instruction.low)
Copy code
module.on = !module.on
              module.destinations.mapTo(queue) { destination ->
                Instruction(low = module.on, to = destination, from = module.name)
              }
also here. If it is 'on' then we should send a high impulse
I would say it should be module.memory[instruction.from] = !instruction.low
and also
Copy code
module.destinations.mapTo(queue) { destination ->
                Instruction(low = !module.on, to = destination, from = module.name)
              }
p
Yes!
c
Anyone able to have a look at mine? It works for the first sample but doesn't for the second. Instead of the expected 4250/2750 low/high pulses I get 4251/2749. I suspect it's something to do with 
However, before b can turn off, the pulse sent to con is handled first, so it briefly remembers all high pulses for its inputs and sends a low pulse to output. After that, flip-flop b turns off, which causes con to update its state and send a high pulse to output.
but I'm not sure I really understand what its saying here. It says above pulses are processed in order and I don't see anything about them waiting for future inputs. https://github.com/CfGit12/aoc-2023/blob/main/src/main/kotlin/20.kt
m
@Charles Flynn I would check again the Conjunctions and its memory, specially this part of the definition
c
I was doing that but it wasn't working for the sample so I changed it 😕
Copy code
//val memory = destinations.associateBy({ it }, { Pulse.LOW }).toMutableMap()
val memory = mutableMapOf<String, Pulse>()
Well I get that's destinations rather than all possible inputs. Hmm.
e
My input has a link to the device rx that doesn't exist &df -> rx no record about rx... how I suppose to send a signal to rx then Does anybody have similar input as well ?
c
Yeah. Check the example that mentions 
output
🙏 1
j
@Charles Flynn that seems like you used the destinations as memory, you have to memorize last input from other modules
c
Yeah. So I need to work out all the things that could send to it and init them to LOW?
👍 1
j
correct
c
Weird. Ta 🙂
Cheers. Easy enough fix in the end 🙂 Part 2 has a suspiciously low amount of text...
r
what it lacks in text, it more than makes up for it in brute-force runtime 😛
j
@Charles Flynn have fun with part 2. Note I do not recommend trying to brute force it
☝️ 1
➕ 1
c
I'm off to the pub instead 🙂
🍻 3
e
Closer to the Xmas, harder the second parts
a
Can someone give me a hint for Part 2? It feels like another math problem where we pick some special numbers, multiply them together or something like that with constant complexity and voila? or is there some algo trick?
i'm looking at memory state of modules to see some patterns but it doen't look promising
ideas I have so far: 1. module definitions are expressions that could be simplified and calculated faster? kinda like Day 19 2. work backwards from RX low power state - to reverse module definition somehow 3. i noticed that "hf" conjunction increases the number of input states that are need to be on from 1 to 2 in around square number of button presses. I tried to just x^4 but the answer is too low 4. the problem definition sounds like like a halting problem - dig deeper into state machines? 5. some modular arithmetic, group theory or some other algebraic voodoo nothin glooks like a clear winner 😞
j
@andriyo have a look at a graph of the module connections, then you'll see the solution
a
@Jonathan Kolberg thank you! I'll try that
o
I have similar issues with my solution for part 1. Works for both test cases but not the actual input. Can anyone help check?
Copy code
import java.util.LinkedList

fun main() {
    val lines = input.split("\n")
    val modules = lines.map {
        val name = it.split(" -> ")[0]
        when {
            name == "broadcaster" -> Module.BroadcasterModule(name)
            name.startsWith("%") -> Module.FlipFlopModule(name.drop(1))
            name.startsWith("&") -> Module.ConjunctionModule(name.drop(1))
            else -> error("Unknown module")
        }
    }.associateBy { it.name }

    lines.forEach {
        val (parent, children) = it.split(" -> ")
        val parentModule = modules[parent.removePrefix("%").removePrefix("&")]!!

        children.split(", ").forEach {
            if (modules[it] is Module.ConjunctionModule) {
                (modules[it] as Module.ConjunctionModule).addSourceModule(parentModule.name)
            }
            modules[it]?.let { it1 -> parentModule.children.add(it1) }
        }
    }
    data class QueueEntry(val sourceModule: String, val isHighPulse: Boolean, val destinationModule: Module)

    val queue = LinkedList<QueueEntry>()
    var lowPulseCount = 0L
    var highPulseCount = 0L
    (1..1000).forEach {
        queue.offer(QueueEntry("button", false, modules["broadcaster"]!!))
        lowPulseCount++
        while (queue.isNotEmpty()) {
            val (sourceModule, isHighPulse, destinationModule) = queue.poll()
            val nextPulseSignals = destinationModule.processPulse(sourceModule, isHighPulse)
            nextPulseSignals.second.forEach {
                if (nextPulseSignals.first) {
                    highPulseCount++
                } else {
                    lowPulseCount++
                }
                queue.offer(QueueEntry(destinationModule.name, nextPulseSignals.first, it))
            }
        }
    }

    println("Pulse count: ${(lowPulseCount) * highPulseCount}")
}

sealed interface Module {
    val name: String
    val children: MutableSet<Module>

    fun processPulse(sourceModule: String, isHighPulse: Boolean): Pair<Boolean, Set<Module>>

    data class BroadcasterModule(
        override val name: String,
    ) : Module {
        override val children: MutableSet<Module> = mutableSetOf()
        override fun processPulse(sourceModule: String, isHighPulse: Boolean): Pair<Boolean, Set<Module>> {
            return isHighPulse to children
        }
    }

    data class FlipFlopModule(
        override val name: String
    ) : Module {
        private var isOn: Boolean = false
        override val children: MutableSet<Module> = mutableSetOf()
        override fun processPulse(sourceModule: String, isHighPulse: Boolean): Pair<Boolean, Set<Module>> {
            if (!isHighPulse) {
                isOn = !isOn
                return isOn to children
            }
            return isOn to emptySet()
        }
    }

    data class ConjunctionModule(
        override val name: String
    ) : Module {
        override val children: MutableSet<Module> = mutableSetOf()
        private val sourceModules = mutableMapOf<String, Boolean>()

        fun addSourceModule(sourceModule: String) {
            sourceModules[sourceModule] = false
        }
        override fun processPulse(sourceModule: String, isHighPulse: Boolean): Pair<Boolean, Set<Module>> {
            sourceModules[sourceModule] = isHighPulse
            return if (sourceModules.values.all { it }) {
                false to children
            } else {
                true to children
            }
        }
    }
}
r
@Ozioma Ogbe in the 
processPulse
function of the 
FlipFlopModule
I see it returns 
isOn to emptySet()
, shouldn't that be 
isOn to children
instead? Of that's the case, I'm surprised this would have worked for the example though 😅
o
I did that to ignore high pulses according to the instructions, I only add items to the queue if the result of processPulse is not empty
r
ah yeah I misread that, indeed
o
I was ignoring the output module when parsing, works now, thanks.
👍 1
17 Views
Open in Slack
PreviousNext
Powered by