Advent of Code 2023 - Day 20, in Kotlin - Pulse Propagation • Todd Ginsberg

We’re in the home stretch of Advent of Code 2023, just a few more puzzles left. I hope you’re having a good time with them, I sure am. Today’s was fun to implement but I, again, needed help from Reddit to figure out precisely what to do for part 2 as it involved some manual decompiling (sort of). I mostly got it, but it’s nice to have Reddit confirm my thinking before I go off and write a bunch of code I don’t have to.

If you’d rather just view the code, my GitHub Repository is here.

Puzzle Input

A lot of the work for today’s solutions is in the parsing section where we build up a set of classes representing the modules. We will store them by name in a modules map where the key is the name of the module and the value is the implementation.

class Day20(input: List<String>) {

    private val modules: Map<String, Module> = parseModules(input)

}

Before we define our modules, let’s define a class to represent a Pulse from one module to another.

// In Day20

data class Pulse(val high: Boolean, val source: String, val destination: String)

The Pulse class has a boolean representing if the pulse is high or not (we could have gone with an enum, but since there are only two states and we’re unlikely to add a third, this will do), a source the pulse came from and a destination the pulse was sent to.

With this, we’re able to define an abstract Module class, which has a name and a List<String> for destinations:

// In Day20

private abstract class Module(val name: String, val destinations: List<String>) {

    abstract fun receive(pulse: Pulse): List<Pulse>

    fun send(high: Boolean): List<Pulse> = 
        destinations.map { Pulse(high, name, it) }
}

The Module class could have been a sealed class but since I’m not performing operations where I need to exhaustively inspect the instances of Module, it can be a plain class. It has two functions. First, receive, which is abstract and will be implemented in the subclass. The purpose of receive is to take in a Pulse, do the logic, and respond with a List<Pulse> representing new signals to send. The second function is a helper called send which sends either a high or low signal to the destinations. This can be called by subclasses whenever they need to signal other modules.

The first module it the Broadcaster, which hast the most straight forward logic - relay its incoming signal to any destinations.

// In Day20

private class Broadcaster(destinations: List<String>) : Module("broadcaster", destinations) {
    override fun receive(pulse: Pulse): List<Pulse> = send(pulse.high)
}

Next up, the FlipFlop which has an on state and flips it on and off whenever a pulse is received. If it needs to send, it does so by calling the superclass. Otherwise, it returns an emptyList indicating it has no signals to send.

// In Day20

private class FlipFlop(name: String, destinations: List<String>) : Module(name, destinations) {
    private var on = false

    override fun receive(pulse: Pulse): List<Pulse> =
        if (pulse.high) emptyList()
        else {
            on = !on
            send(on)
        }
}

The final and most complicated module is Conjunction. It has a memory to remember the state of each of its sources, and an addSource function so we can tell it which modules will be sending signals. We’ll wire these up later, but it is inconvenient to have all of that information in the constructor. That’s why memory is a MutableMap and the sources are not received in the constructor. The implementation of receive uses the all function on the memory.values to make sure that they are not all true (high) to calculate the pulse type.

// In Day20

private class Conjunction(name: String, destinations: List<String>) : Module(name, destinations) {
    private val memory = mutableMapOf<String, Boolean>()

    fun addSource(source: String) {
        if (source !in memory) memory[source] = false
    }

    override fun receive(pulse: Pulse): List<Pulse> {
        memory[pulse.source] = pulse.high
        return send(!memory.values.all { it })
    }
}

Finally, we can implement parseModules which is on the more complex side compared to this year’s other puzzles.

// In Day20

private fun parseModules(input: List<String>): Map<String, Module> {
    val modules = input.associate { row ->
        val type = row.first()
        val name = row.substring(1).substringBefore(" ")
        val destinations = row.substringAfter(">").split(",").map { it.trim() }.filter { it.isNotEmpty() }

        when (type) {
            'b' -> "broadcaster" to Broadcaster(destinations)
            '&' -> name to Conjunction(name, destinations)
            '%' -> name to FlipFlop(name, destinations)
            else -> throw IllegalArgumentException("No such module: $type from $row")
        }
    }

    val conjunctions = modules.values.filterIsInstance<Conjunction>().associateBy { it.name }
    modules.values.forEach { module ->
        module.destinations.forEach { destination ->
            conjunctions[destination]?.addSource(module.name)
        }
    }
    return modules
}

The first part of the function looks at each row of input, breaks it up to type, name and destinations and figures out which implementaiton of Module is called for. We associate the name of the module to the implementation, which ends up resulting in a Map<String,Module> where the key is the name and the value is the associated module.

The rest of the function is used to wire up the conjunctions and tell them who their sources are. First we find all of the conjunctions by calling filterIsIntance on the modules, and put them in their own map. We use this map to find all of the other modules who mention one of the conjunctions in their destinations and call addSource on them.

Finally, all parsed!

⭐ Day 20, Part 1

The puzzle text can be found here.

Since we’re asked to press a button to send a signal through the modules, let’s call our function button.

// In Day20

private fun button(debugger: Debugger? = null) {
    val messages = ArrayDeque<Pulse>().apply {
        add(Pulse(false, "button", "broadcaster"))
    }
    while (messages.isNotEmpty()) {
        with(messages.removeFirst()) {
            debugger?.pulse(this)
            modules[destination]?.receive(this)?.forEach { messages.add(it) }
        }
    }
}

The button function takes an optional Debugger, which we will write in a moment. This will allow us to implement an interface and gather facts about how the modules interact with each other. We’ll end up writing two implementations, one for each puzzle part.

The first thing we do is set up a messages queue because signals all need to be processed in the order they are sent. We can’t just pass messages from module to module. This queue is where all messages are stored in order, so we initialize it with a Pulse representing the initial button press (which is a low signal).

While we have work to do (messages is not empty), we removeFirst element from the queue. We’ll wrap this section in a with call in order to make it a bit easier to read. The first thing we do is offer the message to the debugger, if we have one. Next, if the destination in the message is known, we call receive on it with the pulse, and then requeue the resulting messages. In the case we don’t know about the module we can ignore this pulse, sending it to a null implementation will not make a difference as they couldn’t respond.

Once we run out of work to do, the button function can return cleanly.

Let’s implement our Debugger, which takes a pulse and does some action to be determined.

// In Day20

private interface Debugger {
    fun pulse(pulse: Pulse)
}

Our debugger for part 1 keeps track of how many signals are sent with a high pulse and how many with a low pulse.

// In Day20

private class Part1Debugger : Debugger {
    var high = 0
    var low = 0
    override fun pulse(pulse: Pulse) {
        if (pulse.high) high++ else low++
    }
}

In order to solve part 1, we create our Part1Debugger, repeat the call to button (with our debugger) 1,00 times, and then inspect the state of the debugger, multiplying the high and low counts together.

// In Day20

fun solvePart1(): Int {
    val debugger = Part1Debugger()
    repeat(1000) {
        button(debugger)
    }
    return debugger.high * debugger.low
}

Star earned! Onward!

⭐ Day 20, Part 2

The puzzle text can be found here.

Strategy

This is one of those puzzles where you have to dig through the input to figure out what’s going on and devise a way to not do any work at all. And I’m not great at those. After more or less getting what was going on, Reddit confirmed and clarified what I needed to know. Namely, the rx module is fed by a single conjunction, which in turn is fed by four other modules. Since the conjunction will only signal rx when all of its inputs are high, we have to look for how many button presses it takes to each of the signals to reach the conjunction, and then get the least common multiple of them. Why? We need them to all be true at the same time, and the LCM of their cycle count is how we do that.

Implementation

First, we’ll write our debugger for part 2 which will allow us to watch the individual inputs to a conjunction.

// In Day20

private class Part2Debugger(val sources: Set<String>) : Debugger {
    val seen = mutableSetOf<String>()

    override fun pulse(pulse: Pulse) {
        if (pulse.high && pulse.source in sources)
            seen += pulse.source
    }
}

The Part2Debugger takes in a Set<String> representing sources we expect the conjunction to have. It has a seen set which allows us to keep track of whether we’ve received a high pulse from one of our sources.

To use our debugger, we need to find the inputs to the conjunction.

// In Day20

fun solvePart2(): Long {
    val sourceForRx = modules.values.first { "rx" in it.destinations }
    val lookFor = modules.values
        .filter { sourceForFx.name in it.destinations }.toMutableSet()
        .associate { it.name to 0L }
        .toMutableMap()
    val debugger = Part2Debugger(lookFor.keys)
    var count = 0

    while (lookFor.values.any { it == 0L }) {
        count++
        button(debugger)
        debugger.seen.forEach { name ->
            if (lookFor.getValue(name) == 0L) {
                lookFor[name] = count.toLong()
            }
        }
        debugger.seen.clear()
    }

    return lookFor.values.reduce(Long::lcm)
}

First we find the sourceForRx which is the conjunction that feeds the rx module at the end. Then we search for any module that sends a signal to the sourceforRx and store those in a MutableMap<String, Long> where the key is the name of the module and the value is how many button presses it took to have it signal the first time.

We set up our debugger, passing in the names of the sources we care about. We also set up a count to count button presses.

Then we start mashing the button! We keep mashing the button so long as any of the modules we care about have not sent a signal yet. Once we have head from all of them, we can stop. In each iteration of the button press, we increment our counter, press the button, and then see if the debugger has seen anything we care about. If it has, and we haven’t heard from it before, we record the count (as a Long). We clear the state of the debugger so we don’t end up re-evaluating the seen list over and over (you could leave this off and it would all work out just fine).

Finally, we reduce over the values (the number of button presses) and reuse our Long::lcm function from the other day to calculate the LCM of all the button press counts (which are all prime).

Star earned! See you tomorrow!

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading