Skip to Content

Advent of Code 2018 - Day 20, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2018, Day 20: 'A Regular Map'

Posted on

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

Note: I’m not going to quote the entire problem, it is quite lengthy. Go read it yourself.

What is the largest number of doors you would be required to pass through to reach a room? That is, find the room for which the shortest path from your starting location to that room would require passing through the most doors; what is the fewest doors you can pass through to reach it?

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

Okay, so the facility is big.

How many rooms have a shortest path from your current location that pass through at least 1000 doors?

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

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

Star 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 20
  4. Advent of Code - Come join in and do these challenges yourself!