Advent of Code 2019 - Day 16, in Kotlin • Todd Ginsberg

Today’s puzzle involves some simple math for Part 1 and some Pattern Recognition for Part 2.

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

Problem Input

We are given a lengthy String of digits, which we want to turn into an IntArray so we can manipulate it later on. Because each Char in the String needs to be converted to digit and not an integer (because of how the character encodings work), we’ll use Character.getNumericValue() from Java.

class Day16(private val input: String) {

    private val signal: IntArray = input.map { Character.getNumericValue(it) }.toIntArray()

}

We will also keep our input around as a private val because we need it for Part 2.

⭐ Day 16, Part 1

The puzzle text can be found here.

Part 1 today can be done with brute force. Meaning, follow the instructions and perform the transforms indicated. We’ll start by declaring some constants:

companion object {
    val base: IntArray = intArrayOf(0, 1, 0, -1)
}

This is the 0, 1, 0, -1 that we use to do some multiplying later.

Next, we’ll write an extension function to take the last digit of our calculations:

private fun Int.lastDigit(): Int =
    (this % 10).absoluteValue

We’ll also need a nice way to turn our base into the cycle mask we need to use. We’ll do this by setting up another range, this time from zero to the number of cycles we’ll need. This will create one more spot than we need, but since we drop the first element at the end, that’s good. We use flatMap here because our inner loop is creating multiple List<Int>, and we want them flattened into one List<Int> that we can turn into an IntArray. The inner loop uses the fact that List has a constructor that takes a size (perCycle) and a lambda to calculate the value for a given index. Finally, we drop the first item and turn the rest into an IntArray.

private fun IntArray.cycle(perCycle: Int, length: Int): IntArray =
    (0..length / perCycle).flatMap { idx ->
        List(perCycle) { this[idx % this.size] }
    }.drop(1).toIntArray()

At the core of our algorithm is the notion of a phase. A set of transitions. Since we’re basing our data structure off of an IntArray, we’ll write an extension on IntArray that does one phase transform:

private fun phase(input: IntArray): IntArray =
    (1..input.size).map { element ->
        val cycle: IntArray = base.cycle(element, input.size)
        input.mapIndexed { index, inputElement -> (inputElement * cycle[index]) }.sum().lastDigit()
    }.toIntArray()

Let’s break that down. We need to perform one full calculation for each digit of our input, so we’ll set up a range for that and map the results. Next, we’ll use our cycle extension function to calculate what the full set of masks are. Finally, we perform the multiplication of the input with the mask (cycle), sum the digits, and take the last digit of that. We perform this calculation once for each digit of our input and return the results.

To solve Part 1, we’ll repeat this 100 times, using a fold:

fun solvePart1(phases: Int = 100): String =
    (1..phases).fold(signal) { carry, _ -> phase(carry) }.joinToString(separator = "").take(8)

Star earned!

⭐ Day 16, Part 2

The puzzle text can be found here.

For this part, we need to get clever. We can’t run this many phases on such a large number or it will take a very long time. If we look at the offset we’re given, it is over half way through the newly stretched out signal’s length. This means that when applying the base calculation, from place 0 to place offset will be some number times 0, so we can ignore them. And for the rest of the signal, it will be each number times 1, so we can take them as-is. If we look at the signal, the value of any position n is the sum of the signal’s digits between n and the end (mod 10, absolute value). So if we keep both of these facts in mind, and calculate backwards, we can complete one phase of a very long signal somewhat quickly!

fun solvePart2(phases: Int = 100): String {
    val offset = input.take(7).toInt()
    val stretchedInput = (offset until 10_000 * input.length).map { signal[it % input.length] }.toIntArray()
    repeat(phases) {
        stretchedInput.indices.reversed().fold(0) { carry, idx ->
            (stretchedInput[idx] + carry).lastDigit().also { stretchedInput[idx] = it }
        }
    }
    return stretchedInput.take(8).joinToString(separator = "")
}

First, we grab the seven digit offset from our original input. Because we’re converting a String to an Int instead of an individual Char, we can just call toInt(). Because of the theory above, we can safely ignore anything before the offset. Next, we multiply our original input signal by 10,000 times and turn it into an IntArray. The value of each slot in our new stretchedInput is the place value mod the original input length.

Next, we run our new phase 100 times. In Part 2 here, we’ll modify our stretchedInput in place because it is so huge. I don’t want to make a lot of copies, we’ll just depend on the side effect. We will reverse the indexes for our stretchedInput and fold over that, setting each slot to the sum of the previous slots (remember, we’re working backwards), and taking the last digit.

Finally, we take the first eight digits from our final stretchedInput and join them together into a String, which is our answer!

Star earned!

⭐ Day 16, Part 1

⭐ Day 16, Part 2

Further Reading