Skip to Content

Advent of Code 2017 - Day 25, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 25: 'The Halting Problem'

Posted on

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

Following the twisty passageways deeper and deeper into the CPU, you finally reach the core of the computer. Here, in the expansive central chamber, you find a grand apparatus that fills the entire room, suspended nanometers above your head.

You had always imagined CPUs to be noisy, chaotic places, bustling with activity. Instead, the room is quiet, motionless, and dark.

Suddenly, you and the CPU’s garbage collector startle each other. “It’s not often we get many visitors here!”, he says. You inquire about the stopped machinery.

“It stopped milliseconds ago; not sure why. I’m a garbage collector, not a doctor.” You ask what the machine is for.

“Programs these days, don’t know their origins. That’s the Turing machine! It’s what makes the whole computer work.” You try to explain that Turing machines are merely models of computation, but he cuts you off. “No, see, that’s just what they want you to think. Ultimately, inside every CPU, there’s a Turing machine driving the whole thing! Too bad this one’s broken. We’re doomed!”

You ask how you can help. “Well, unfortunately, the only way to get the computer running again would be to create a whole new Turing machine from scratch, but there’s no way you can-” He notices the look on your face, gives you a curious glance, shrugs, and goes back to sweeping the floor.

You find the Turing machine blueprints (your puzzle input) on a tablet in a nearby pile of debris. Looking back up at the broken Turing machine above, you can start to identify its parts:

  • A tape which contains 0 repeated infinitely to the left and right.
  • A cursor, which can move left or right along the tape and read or write values at its current position.
  • A set of states, each containing rules about what to do based on the current value under the cursor. Each slot on the tape has two possible values: 0 (the starting value for all slots) and 1. Based on whether the cursor is pointing at a 0 or a 1, the current state says what value to write at the current position of the cursor, whether to move the cursor left or right one slot, and which state to use next.

For example, suppose you found the following blueprint:

Begin in state A.
Perform a diagnostic checksum after 6 steps.

In state A:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state B.
  If the current value is 1:
    - Write the value 0.
    - Move one slot to the left.
    - Continue with state B.

In state B:
  If the current value is 0:
    - Write the value 1.
    - Move one slot to the left.
    - Continue with state A.
  If the current value is 1:
    - Write the value 1.
    - Move one slot to the right.
    - Continue with state A.

Running it until the number of steps required to take the listed diagnostic checksum would result in the following tape configurations (with the cursor marked in square brackets):

... 0  0  0 [0] 0  0 ... (before any steps; about to run state A)
... 0  0  0  1 [0] 0 ... (after 1 step;     about to run state B)
... 0  0  0 [1] 1  0 ... (after 2 steps;    about to run state A)
... 0  0 [0] 0  1  0 ... (after 3 steps;    about to run state B)
... 0 [0] 1  0  1  0 ... (after 4 steps;    about to run state A)
... 0  1 [1] 0  1  0 ... (after 5 steps;    about to run state B)
... 0  1  1 [0] 1  0 ... (after 6 steps;    about to run state A)

The CPU can confirm that the Turing machine is working by taking a diagnostic checksum after a specific number of steps (given in the blueprint). Once the specified number of steps have been executed, the Turing machine should pause; once it does, count the number of times 1 appears on the tape. In the above example, the diagnostic checksum is 3.

Recreate the Turing machine and save the computer! What is the diagnostic checksum it produces once it’s working again?

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!

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 25.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Countdown - Number of days until Advent of Code 2018 starts!
  6. Music to Code By - Christmas at Ground Zero, by “Weird Al” Yankovic.