# 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

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) {
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).