Advent of Code 2019 - Day 15, in Kotlin • Todd Ginsberg

Today, we’ll write ourselves a reusable function to find paths through a maze. Maybe that will come in handy in the future!

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

Problem Input

Another IntCode program calls for parsing these the same way we’ve parsed them before.

private val program: MutableMap<Long, Long> = input
    .split(",")
    .withIndex()
    .associateTo(mutableMapOf()) { it.index.toLong() to it.value.toLong() }

⭐ Day 15, Part 1

The puzzle text can be found here.

The strategy we’re going to use to solve Part 1 is to use the robot to discover the entire maze and then work with that representation so we don’t have to keep moving the robot around.

First, some constants:

companion object {
    private const val pathBlocked: Long = 0
    private const val robotMoved: Long = 1
    private const val foundOxygen: Long = 2

    private const val wall: Char = '#'
    private const val open: Char = '.'
    private const val oxygen: Char = 'O'
}

We will represent our maze as a Map<Point2D, Char>, where the key is a point in the maze and the value is a character (so we can print this and have a chance at a good picture). To do that, we’ll need a computer, and a function to use the computer to explore the entire maze. Once we have the maze, we’ll create a variable to represent the position of the oxygen in the maze because we’ll use it a few times.

private val computer = IntCodeComputerMk2(program)
private val maze: Map<Point2D, Char> = maze()
private val oxygenLocation: Point2D = maze.entries.first { it.value == oxygen }.key

To create our maze map, we’ll need a suspending function to start our computer, hand off the work of moving the robot around, and then waiting for the answer.

private fun maze() = runBlocking {
    val job = async {
        computer.runProgram()
    }
    calculateMaze().also {
        job.cancel()
    }
}

And the function to calculate the maze:

private suspend fun calculateMaze(
    at: Point2D = Point2D.ORIGIN,
    mazeSoFar: MutableMap<Point2D, Char> = mutableMapOf(Point2D.ORIGIN to open)
): MutableMap<Point2D, Char> {
    at.neighbors().filter { it !in mazeSoFar }.forEach { neighbor ->
        computer.input.send(at.directionTo(neighbor))
        when (val result = computer.output.receive()) {
            foundOxygen, robotMoved -> {
                mazeSoFar[neighbor] = if (result == robotMoved) open else oxygen
                calculateMaze(neighbor, mazeSoFar)
                computer.input.send(neighbor.directionTo(at))
                computer.output.receive() // Ignore, we know this works.
            }
            pathBlocked -> mazeSoFar[neighbor] = wall
        }
    }
    return mazeSoFar
}

The calculateMaze function is recursive. It finds the neighbors of the point we are given, and filters out anything that we’ve already traversed. For each of the neighbors, we move the robot towards that point and interpret the results. If we’ve hit a wall, we do nothing (try the next neighbor). If we find an open place or oxygen, note that and then recursively call calculateMaze with our neighbor as the starting point. When that call is done, we back the robot up in the opposite direction. This will eventually traverse the entire maze and give us our map.

I’ve also defined this extension class on Point2D as part of today’s solution class instead of Point2D because it feels like a one-off. This compares two adjacent points and translates them into directions for the computer.

private fun Point2D.directionTo(other: Point2D): Long =
    when (other) {
        north() -> 1
        south() -> 2
        west() -> 3
        east() -> 4
        else -> throw IllegalStateException("Unknown relation between $this and $other")
    }

Next, we’ll write a function to traverse a maze and find all of the paths from a certain point to another point. Because sometimes we might not know our goal, we can make that optional, in which case our function will find all paths until there are no spots left to check. Because what constitutes a valid neighbor will change, we must provide a function so we can filter out neighbors.

// In Searches.kt

fun findPaths(from: Point2D,
              to: Point2D?,
              validNeighbor: (Point2D) -> Boolean): Sequence<List<Point2D>> = sequence {
    val visited = mutableSetOf<Point2D>()
    val queue = ArrayDeque<MutableList<Point2D>>().apply { add(mutableListOf(from)) }
    while (queue.isNotEmpty()) {
        val thisPath = queue.pop()
        if (thisPath.last() == to) {
            yield(thisPath)
        }
        if (thisPath.last() !in visited) {
            visited.add(thisPath.last())
            val neighbors = thisPath.last().neighbors().filter { validNeighbor(it) }.filter { it !in visited }
            if (neighbors.isEmpty() && to == null) {
                yield(thisPath)
            } else {
                neighbors.forEach { neighbor ->
                    queue.add(thisPath.copyOf().apply { add(neighbor) })
                }
            }
        }
    }
}

I’ve implemented this as a sequence. Because we add new work to the end of the queue rather than the beginning, we’re guaranteed to find solutions in shortest to longest order. So if we wanted only the shortest solution, we could just stop reading from the sequence.

And to solve part 1:

fun solvePart1(): Int =
    findPaths(Point2D.ORIGIN, oxygenLocation) { maze.getOrDefault(it, wall) != wall }.first().size - 1

We call our findPaths function, asking it to find a path from the origin to the oxygen. We tell it what constitutes a valid neighbor (anything that isn’t a wall), and take the first result. Because our paths contain the origin, we need to subtract that to get the number of steps taken.

Star earned!

⭐ Day 15, Part 2

The puzzle text can be found here.

Now that we’ve done the hard work in Part 1, we can directly solve part 2. Because we can use our findPaths function to get all paths from the oxygen to wherever it runs out of spots to check, we know that the last path will be the longest. This is how long it takes for oxygen to reach that point. Again, we need to subtract 1 to account for the fact that the starting point is in our path.

fun solvePart2(): Int =
    findPaths(oxygenLocation, null) { maze.getOrDefault(it, wall) != wall }.last().size - 1

Star earned!

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading