Skip to Content

Advent of Code 2017 - Day 15, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 15: 'Dueling Generators'

Posted on

On Day 15 we will show how awesome Kotlin’s sequence generators are and earn two easy stars! If you’d rather jump straight to the code, it’s right here.

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

Day 15, Part 1

Here, you encounter a pair of dueling generators. The generators, called generator A and generator B, are trying to agree on a sequence of numbers. However, one of them is malfunctioning, and so the sequences don’t always match.

As they do this, a judge waits for each of them to generate its next value, compares the lowest 16 bits of both values, and keeps track of the number of times those parts of the values match.

The generators both work on the same principle. To create its next value, a generator will take the previous value it produced, multiply it by a factor (generator A uses 16807; generator B uses 48271), and then keep the remainder of dividing that resulting product by 2147483647. That final remainder is the value it produces next.

To calculate each generator’s first value, it instead uses a specific starting value as its “previous value” (as listed in your puzzle input).

For example, suppose that for starting values, generator A uses 65, while generator B uses 8921. Then, the first five pairs of generated values are:

--Gen. A--  --Gen. B--
   1092455   430625591
1181022009  1233683848
 245556042  1431495498
1744312007   137874439
1352636452   285222916

In binary, these pairs are (with generator A’s value first in each pair):

00000000000100001010101101100111
00011001101010101101001100110111

01000110011001001111011100111001
01001001100010001000010110001000

00001110101000101110001101001010
01010101010100101110001101001010

01100111111110000001011011000111
00001000001101111100110000000111

01010000100111111001100000100100
00010001000000000010100000000100

Here, you can see that the lowest (here, rightmost) 16 bits of the third value match: 1110001101001010. Because of this one match, after processing these five pairs, the judge would have added only 1 to its total.

To get a significant sample, the judge would like to consider 40 million pairs. (In the example above, the judge would eventually find a total of 588 pairs that match in their lowest 16 bits.)

After 40 million pairs, what is the judge’s final count?

The second I saw this challenge I knew exactly how I would solve it. Kotlin has a function that allows you to build a sequence called generateSequence. Give it a starting point and a lambda to describe your iteration, and it’s done. Here’s the one I wrote to handle both Generator A and Generator B:

private fun generator(start: Long, factor: Long, divisor: Long = 2147483647): Sequence<Short> =
    generateSequence((start * factor) % divisor) { past ->
        (past * factor) % divisor
    }.map { it.toShort() }

It takes the start point, the multiplication factor, and the divisor and calculates the answer. The first time through it uses the start value, and every other time it uses the most recently generated number (past) as the start value. In this specific case I’m downcasting it to a Short, which is conveniently 16 bits. Sure, we could do some bitwise and-ing, but I felt that for a simple problem like this it was clearer to just downcast. Plus, we finally have a use case for Short on the JVM. :)

Aside: Something I like doing with Kotlin is to not hard code magic numbers except as default parameter values. That way people can override them but if they don't they still act like magic numbers.

All we need to do now is parse our input, and call our generators.

private val notNumbers = """[^\d]""".toRegex()
private val generatorA = generator(input[0].replace(notNumbers, "").toLong(), 16807)
private val generatorB = generator(input[1].replace(notNumbers, "").toLong(), 48271)

fun solvePart1(pairs: Int = 40_000_000): Int =
    generatorA
        .zip(generatorB)
        .take(pairs)
        .count { it.first == it.second }

The part that I like about this solution is the use of zip which takes two Sequences and jams the results together into a Pair. We use take to limit how many pairs we look at and then count the ones where both of the generators crank out the same values.

Easy and done for star number one.

Day 15, Part 2

In the interest of trying to align a little better, the generators get more picky about the numbers they actually give to the judge.

They still generate values in the same way, but now they only hand a value to the judge when it meets their criteria:

  • Generator A looks for values that are multiples of 4.
  • Generator B looks for values that are multiples of 8.

Each generator functions completely independently: they both go through values entirely on their own, only occasionally handing an acceptable value to the judge, and otherwise working through the same sequence of values as before until they find one.

The judge still waits for each generator to provide it with a value before comparing them (using the same comparison method as before). It keeps track of the order it receives values; the first values from each generator are compared, then the second values from each generator, then the third values, and so on.

Using the example starting values given above, the generators now produce the following first five values each:

--Gen. A--  --Gen. B--
1352636452  1233683848
1992081072   862516352
 530830436  1159784568
1980017072  1616057672
 740335192   412269392

These values have the following corresponding binary values:

01010000100111111001100000100100
01001001100010001000010110001000

01110110101111001011111010110000
00110011011010001111010010000000

00011111101000111101010001100100
01000101001000001110100001111000

01110110000001001010100110110000
01100000010100110001010101001000

00101100001000001001111001011000
00011000100100101011101101010000

Unfortunately, even though this change makes more bits similar on average, none of these values’ lowest 16 bits match. Now, it’s not until the 1056th pair that the judge finds the first match:

--Gen. A--  --Gen. B--
1023762912   896885216

00111101000001010110000111100000
00110101011101010110000111100000

This change makes the generators much slower, and the judge is getting impatient; it is now only willing to consider 5 million pairs. (Using the values from the example above, after five million pairs, the judge would eventually find a total of 309 pairs that match in their lowest 16 bits.)

After 5 million pairs, but using this new generator logic, what is the judge’s final count?

This solution is virtually similar to the one we just wrote except we filter the results down. We’ll use the same generators and approach otherwise:

fun solvePart2(pairs: Int = 5_000_000): Int =
    generatorA.filter { it % 4 == 0 }
        .zip(generatorB.filter { it % 8 == 0 })
        .take(pairs)
        .count { it.first == it.second }

See? More or less the same except for the filters. An easy second star for today.

I hope you’ve learned something and as always, feedback is welcome!

15 days and we’ve earned 30 stars with 20 left to go! 35 of the way

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 15.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Dueling Banjos, by Eric Weissberg.