# Advent of Code 2019 - Day 16, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 16: 'Flawed Frequency Transmission'

Posted on

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!