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

On Day 20, we get to use our Point class again, and write a low-grade regex parser.

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

Problem Input

We get one giant String this time. We’ll hand it to the constructor of our class for today, and parse it in part 1.

⭐ Day 20, Part 1

The puzzle text can be found here.

Fair warning that this is not a general purpose solution for every map that exists. This works for the sample input, as well as my problem input. I suppose it might not work for all sample inputs. The approach I took is that for any given point, we should have a way to look up its distance from the starting point. I didn’t create a graph and then traverse it, we are going to walk through the regex and count the number of steps we’ve taken. This works for the inputs I’ve tried, but doesn’t work for all maps.

Housekeeping

First, let’s write our companion object.

// In Day20

companion object {
    private val startingPoint = Point(0, 0)
    private val movementRules = mapOf(
        'N' to Point::up,
        'S' to Point::down,
        'E' to Point::right,
        'W' to Point::left
    )
}

We will define startingPoint as 0,0, because that seems reasonable. We also need a way to look up our directions (North, East, West, South) and what function on our existing Point class they correspond to. So we will define a map to house that data.

Creating the Grid Distances Map

As I mentioned before, we’re going to create a Map<Point, Int>, where the key is some Point we’ve discovered and the value is an Int which represents how far it is from the starting point. I was tempted to parse our input with a recursive function but that ended up being messy so I abandoned that approach and went with a stack instead:

// In Day20

private fun parseGrid(input: String): Map<Point, Int> {
    val grid = mutableMapOf(startingPoint to 0)
    val stack = ArrayDeque<Point>()
    var current = startingPoint
    input.forEach {
        when (it) {
            '(' -> stack.push(current)
            ')' -> current = stack.pop()
            '|' -> current = stack.peek()
            in movementRules -> {
                // If we are moving to a spot we haven't seen before, we can
                // record this as a new distance.
                val nextDistance = grid.getValue(current) + 1
                current = movementRules.getValue(it).invoke(current)
                grid[current] = minOf(grid.getOrDefault(current, Int.MAX_VALUE), nextDistance)
            }
        }
    }
    return grid
}

Let’s walk through it. First, we set up a map called grid to store our data in, and initialize it with the startingPoint (which is conveniently 0 steps away from itself). Next, we’ll create a stack out of an ArrayDeque to remember where we were when we run into sub-expressions. Finally, we will have a var current to remember where in space we are.

Then we loop through all if the input, ignoring anything that we don’t expect, especially the ^ and $ characters. If we run into a (, that means we’ve started a new sub-expression, so we’ll have to save off our current location because when we stop working on the sub-expression we’ll need to resume moving from there. So we push it down onto the stack. Similarly, if we run into a ), that means we’ve ended a sub-expression and need to move back to the point we were at before the sub-expression started. So we pop that off the stack. The tricky one is |, and alternate ending to a sub-expression. In that case we still need to go back to where we were, but only temporarily or we’ll end up going back too far, so we just take a peek at what was on the top of the stack, leaving it there.

The last part of logic here concerns movement. If we run into a direction, we want to consult our movementRules on what to do about it. We get the function appropriate for the direction we need to move and execute it, moving in that direction. We record where we end up and its distance from start if we don’t already know it, by adding 1 to the point we moved from.

Now we have a Map<Point, Int> of every point we’ve passed and how far it is from the start.

Solving!

We can now move directly to a solution:

class Day20(rawInput: String) {

    private val grid: Map<Point, Int> = parseGrid(rawInput)

    fun solvePart1(): Int =
        grid.maxBy { it.value }!!.value
}

Star earned! Onward!

⭐ Day 20, Part 2

The puzzle text can be found here.

Good news! We already have everything we need to solve part 2!

fun solvePart2(): Int =
    grid.count { it.value >= 1000 }

Star earned!

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading