Advent of Code 2017 - Day 25, in Kotlin • Todd Ginsberg

On Day 25 we will go way back in time (for some of us) to CS101 and build a Turing Machine! 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 25, Part 1

The puzzle text can be found here.

OK, let’s write ourselves a Turing Machine! I’m going to save parsing the input until later, let’s talk about what we need in order to build our Turing Machine first. A Turing Machine has an infinite tape of 1’s and 0’s, is in a specific state, perform an action in that state depending on what the tape says, move the tape, and switch to a new state. That might sound like a lot but implementing a Turing Machine is actually quite simple and there are many, many ways to do it (so have fun!).

Let’s start with how we represent the state, and the actions to take in that state if the tape is 1 or 0:

class Action(val write: Boolean, val move: Int, val nextState: Char)
class MachineState(val zero: Action, val one: Action)

Our Action class has three values: if we are writing or not, how much to change our cursor (movement) and what state to go to next. And our MachineState represents each of these Actions depending on whether the tape is 1 or 0. Why am I implementing writing as a Boolean when the instructions mention writing 1 or 0? Because in our model, which you will see in a moment, a 0 will erase data and 1 will record the cursor’s position.

Let’s start thinking about our actual TuringMachine class next. It will need to know all of the MachineStates, how many steps to take, what state we start with, what the current state is, and what’s on the tape. It is also going to know where the cursor is pointing.

class TuringMachine(private val states: Map<Char, MachineState>, private val steps: Int, startState: Char) {
    private val tape = mutableSetOf<Int>()
    private var state = states.getValue(startState)
    private var cursor = 0

    fun run(): Int {
        repeat(steps) {
            execute()
        }
        return tape.size
    }

    private fun execute() {
        if (cursor in tape) handleAction(state.one)
        else handleAction(state.zero)
    }

    private fun handleAction(action: Action) {
        if (action.write) tape.add(cursor) else tape.remove(cursor)
        cursor += action.move
        state = states.getValue(action.nextState)
    }
}

As you can see, we represent the tape as a Set<Int>. Since we don’t have to make any decisions about the order of the marks we make on the tape, we can simply and quickly just keep a set of which cursor values ended up with a write instruction. You could represent this as lists or BitSets as well.

Credit to Edson Menegatti, who used a set in his solution posted to #AdventOfCode in Kotlin Slack. Originally I had implemented an InfiniteTape class which managed a positive and negative list of integers, but the set solution is so much more elegant I’m taking inspiration and using that. Never be afraid to refactor your code when a better idea is presented.

The actual execution of the TuringMachine is quite simple. Check the current state, and either add the value of the cursor (mark the tape with 1) or remove the value of the cursor (mark the tape with 0), move in the direction we’re told (update the cursor), and figure out what our next state is. Repeat that steps number of times, and then see how many marks we’ve made on the tape by counting the number of elements in the tape set.

Simple, right? Well, until you consider all the parsing required to read our input and crank out a TuringMachine. When I first solved this I just hard coded the MachineState map, but after looking at the input decided that despite how verbose it is, it’s really not that hard to parse:

private fun parseInput(input: List<String>): TuringMachine {
    val initialState = input.first()[15]
    val steps = input[1].split(" ")[5].toInt()

    val stateMap = input
        .filter { it.isNotBlank() }
        .drop(2)
        .map { it.split(" ").last().dropLast(1) }
        .chunked(9)
        .map {
            it[0].first() to MachineState(
                Action(it[2] == "1", if (it[3] == "right") 1 else -1, it[4].first()),
                Action(it[6] == "1", if (it[7] == "right") 1 else -1, it[8].first())
            )
        }.toMap()
    return TuringMachine(stateMap, steps, initialState)
}

Let’s break that down line by line. The first line contains the state our machine starts in. It’s always the 16th character, so we’ll just manually pick that out and set it aside. Next, we pick out the number of steps our machine makes. That’s always the 6th symbol if we separate by spaces, so we’ll pick that out and convert it to an integer.

Building up the state map (State to MachineState) looks more complicated but thanks to Kotlin’s strong standard library, is actually quite efficient and easy to understand once you look at the input. From here on, we really only care about the very last symbol in each row. Go look at it if you don’t believe me. We also only care about lines that aren’t blank. So the first thing we do is get rid of blank lines and drop the first two lines which we’ve already manually parsed.

Next, we take each remaining line, split it by space, and take the very last symbol that we care about. At this point we have a String with some punctuation on the end, so we will drop the last Char from our String. At this point we’re operating on a stream of symbols that make up MachineStates. Since the symbols form a MachineState in groups of 9, we will chunk all of the String inputs together into List<String>, of size 9! Then we only have to act on each of those to make a MachineState mapping!

To do that, we create Actions by evaluating the elements in the chunked list. This final map function actually returns a List<Pair<Char, MachineState>>, and the .toMap() turns the Pairs into a Map<Char, MachineState> for us! Neat!

All we’re left with for parsing is to actually build and return our TuringMachine. I’m fairly confident that this will work on any input the Advent of Code gives you.

And of course, executing our TuringMachine and getting an answer couldn’t get much simpler:

class Day25(input: List<String>) {

    private val machine: TuringMachine = parseInput(input)

    fun solvePart1(): Int =
        machine.run()

    // ...
}

That’s star one out of the way, let’s see what part 2 has in store for us…

⭐ Day 25, Part 2

There is no code to write for part 2 because we’re given our 50th star for getting this far. Good work!

Thanks to Eric Wastl for creating Advent of Code. I learned a lot and enjoyed the time I spent solving the problems, refactoring code, explaining all of my solutions, and coming up with a tangentially related song to go with it (for coding music). I can’t wait to play again next year!

If you enjoyed Advent of Code, I humbly suggest you consider donating to Eric to show your support . He comes up with 25 (x2!) puzzles over the course of the year, writes all the stories, writes all the code to generate all the inputs, and does it all flawlessly (never a broken puzzle).

I hope you had fun.

Only 340 days until Advent of Code 2018!

⭐ Day 25, Part 1

⭐ Day 25, Part 2

Further Reading