Skip to Content

Advent of Code 2018 - Day 9, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 9: 'Marble Mania'

Posted on

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 Elves play this game by taking turns arranging the marbles in a circle according to very particular rules. The marbles are numbered starting with 0 and increasing by 1 until every marble has a number.

First, the marble numbered 0 is placed in the circle. At this point, while it contains only a single marble, it is still a circle: the marble is both clockwise from itself and counter-clockwise from itself. This marble is designated the current marble.

Then, each Elf takes a turn placing the lowest-numbered remaining marble into the circle between the marbles that are 1 and 2 marbles clockwise of the current marble. (When the circle is large enough, this means that there is one marble between the marble that was just placed and the current marble.) The marble that was just placed then becomes the current marble.

However, if the marble that is about to be placed has a number which is a multiple of 23, something entirely different happens. First, the current player keeps the marble they would have placed, adding it to their score. In addition, the marble 7 marbles counter-clockwise from the current marble is removed from the circle and also added to the current player’s score. The marble located immediately clockwise of the marble that was removed becomes the new current marble.

For example, suppose there are 9 players. After the marble with value 0 is placed in the middle, each player (shown in square brackets) takes a turn. The result of each of those turns would produce circles of marbles like this, where clockwise is to the right and the resulting current marble is in parentheses:

[-] (0)
[1]  0 (1)
[2]  0 (2) 1 
[3]  0  2  1 (3)
[4]  0 (4) 2  1  3 
[5]  0  4  2 (5) 1  3 
[6]  0  4  2  5  1 (6) 3 
[7]  0  4  2  5  1  6  3 (7)
[8]  0 (8) 4  2  5  1  6  3  7 
[9]  0  8  4 (9) 2  5  1  6  3  7 
[1]  0  8  4  9  2(10) 5  1  6  3  7 
[2]  0  8  4  9  2 10  5(11) 1  6  3  7 
[3]  0  8  4  9  2 10  5 11  1(12) 6  3  7 
[4]  0  8  4  9  2 10  5 11  1 12  6(13) 3  7 
[5]  0  8  4  9  2 10  5 11  1 12  6 13  3(14) 7 
[6]  0  8  4  9  2 10  5 11  1 12  6 13  3 14  7(15)
[7]  0(16) 8  4  9  2 10  5 11  1 12  6 13  3 14  7 15 
[8]  0 16  8(17) 4  9  2 10  5 11  1 12  6 13  3 14  7 15 
[9]  0 16  8 17  4(18) 9  2 10  5 11  1 12  6 13  3 14  7 15 
[1]  0 16  8 17  4 18  9(19) 2 10  5 11  1 12  6 13  3 14  7 15 
[2]  0 16  8 17  4 18  9 19  2(20)10  5 11  1 12  6 13  3 14  7 15 
[3]  0 16  8 17  4 18  9 19  2 20 10(21) 5 11  1 12  6 13  3 14  7 15 
[4]  0 16  8 17  4 18  9 19  2 20 10 21  5(22)11  1 12  6 13  3 14  7 15 
[5]  0 16  8 17  4 18(19) 2 20 10 21  5 22 11  1 12  6 13  3 14  7 15 
[6]  0 16  8 17  4 18 19  2(24)20 10 21  5 22 11  1 12  6 13  3 14  7 15 
[7]  0 16  8 17  4 18 19  2 24 20(25)10 21  5 22 11  1 12  6 13  3 14  7 15

The goal is to be the player with the highest score after the last marble is used up. Assuming the example above ends after the marble numbered 25, the winning score is 23+9=32 (because player 5 kept marble 23 and removed marble 9, while no other player got any points in this very short example game).

Here are a few more examples:

  • 10 players; last marble is worth 1618 points: high score is 8317
  • 13 players; last marble is worth 7999 points: high score is 146373
  • 17 players; last marble is worth 1104 points: high score is 2764
  • 21 players; last marble is worth 6111 points: high score is 54718
  • 30 players; last marble is worth 5807 points: high score is 37305

What is the winning Elf’s score?

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

Amused by the speed of your answer, the Elves are curious:

What would the new winning Elf’s score be if the number of the last marble were 100 times larger?

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!

Further Reading

  1. Index of All Solutions - All solutions for 2018, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 9
  4. Advent of Code - Come join in and do these challenges yourself!