Advent of Code 2018 - Day 9, in Kotlin • Todd Ginsberg

It feels like the real name of Day 9 should have been “Shifty Listy”, but it’s “Marble Mania” instead. Either works I suppose.

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

Problem Input

There are two Ints in a String that we need. Because we only have one row of input, I’ll just hand them in manually. Check the test cases in GihHub if you are interested in the details. We’ll pass the two values we need into our class for today:

class Day09(private val players: Int, private val highest: Int)

⭐ Day 9, Part 1

The puzzle text can be found here.

Well this looks fun. Let’s write a function to play this game for us. We’ll start out with the basics: An array to keep our scores (per Elf), and a ArrayDeque<Long> to store the marbles.

private fun play(numPlayers: Int, highest: Int): Long {
    val scores = LongArray(numPlayers)
    val marbles = ArrayDeque<Int>().also { it.add(0) }

    ... we
}

You might be wondering a few things at this point!

Why Long instead of Int? Because I know something about part 2 that you don’t know yet, and we’ll need it. If you want to code this with an Int, that’s fine, you’ll just have to refactor later (not by much).

Why a ArrayDeque? The strategy we are going to use for adding the next marble is to shift the entire list of marbles so we are only ever working with the first marble. I tried to do this another way where we maintain a pointer into the list, but I just found it confusing. This might sacrifice a bit of performance, but I feel we have clearer code in return. Using the ArrayDeque gives us a good performance boost over ArrayList, or LinkedList.

In order to do that, we’ll need to write a shift() function on Deque that accounts for negative and positive numbers:

private fun <T> Deque<T>.shift(n: Int): Unit =
    when {
        n < 0 -> repeat(n.absoluteValue) {
            addLast(removeFirst())
        }
        else -> repeat(n) {
            addFirst(removeLast())
        }
    }

Our shift() function works as follows: If we are shifting by a negative number we are going to remove the first element and place it on the end of the list. We do the opposite for a positive number of shifts. We use the repeat function to perform this as many times as we need.

Now that we have that, we can finish writing our play function:

private fun play(numPlayers: Int, highest: Int): Long {
    val scores = LongArray(numPlayers)
    val marbles = ArrayDeque<Int>().also { it.add(0) }

    (1..highest).forEach { marble ->
        when {
            marble % 23 == 0 -> {
                scores[marble % numPlayers] += marble + with(marbles) {
                    shift(-7)
                    removeFirst().toLong()
                }
                marbles.shift(1)
            }
            else -> {
                with(marbles) {
                    shift(1)
                    addFirst(marble)
                }
            }
        }
    }
    return scores.max()!!
}

There might be a couple of new things in here, so let’s go over it. First we set up a range from 1 to the number of marbles we’ll have. We have to start at 1 because there is already a marble in the list. (Side note: we could start at zero if we don’t add that first marble in the constructor, account for it with the modulus operator, and account for the empty array in shift(), but that seemed harder to read).

If our marble is divisible by 23, we calculate which player gets it (marble % numPlayers), and add the marble value to the shifted value we need. To do that, we’ll use Kotlin’s with function which is a nice way to call a few functions on a single object, as an expression. In this case, we shift by -7, remove the first element, and cast it to a Long (because Kotlin will not expand an Int to a Long for us automatically). After that, we store the value in our scores array. Because we’ve just shifted and removed a value, we’ll need account for the fact that the value we need at the head of the list is now at the end. So we’ll shift once more.

On the other hand, if we are not adding to a score this round, we just have to shift by 1 and add the marble to the head of the list.

Once all of that is done, we find the maximum value in the scores array. Because Kotlin doesn’t know that scores isn’t empty, we’ll have to use the Hold My Beer operator (!!) to convert our answer from Long? to Long. Now we can run our game code and find the answer:

fun solvePart1(): Long =
    play(players, highest

Star 1 earned! Onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

And now you know why we used Long above and not Int. Run the play function again to get the answer:

fun solvePart2(): Long =
    play(players, highest * 100)

Star 2 earned!

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading