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

Despite the title, today’s puzzle really isn’t about donuts (sadly). I love donuts. Anyway, we’ll write to breadth-first-search functions to solve each part of today’s puzzle.

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

Problem Input

We’ll start by writing a function to parse our input into a Set<Point2D>. Anything not in the set is either not in the maze or a wall. So we only need to keep track of valid spots:

private fun parseMaze(input: List<String>): Set<Point2D> =
    input.mapIndexed { y, row ->
        row.mapIndexedNotNull { x, c -> if (c == '.') Point2D(x, y) else null }
    }.flatten().toSet()

Since we’ll be using a range to specify alphabetical letters, we’ll define it as a constant:

companion object {
    val letters = 'A'..'Z'
}

We also need to find all of the portals and the start (AA) and end (ZZ) spots:

private fun linkPortals(input: List<String>): Triple<Map<Point2D, Point2D>, Point2D, Point2D> {
    val linked = mutableMapOf<Point2D, Point2D>()
    val unlinked = mutableMapOf<String, Point2D>()
    input.forEachIndexed { y, row ->
        row.forEachIndexed { x, c ->
            if (c in letters) {
                val at = Point2D(x, y)
                var name: String? = null
                var portal: Point2D? = null

                when {
                    input.getOrNull(at.south()) in letters && at.north() in maze -> {
                        name = "$c${input.getOrNull(at.south())}"
                        portal = at.north()
                    }
                    input.getOrNull(at.south()) in letters && at.south().south() in maze -> {
                        name = "$c${input.getOrNull(at.south())}"
                        portal = at.south().south()
                    }
                    input.getOrNull(at.east()) in letters && at.west() in maze -> {
                        name = "$c${input.getOrNull(at.east())}"
                        portal = at.west()
                    }
                    input.getOrNull(at.east()) in letters && at.east().east() in maze -> {
                        name = "$c${input.getOrNull(at.east())}"
                        portal = at.east().east()
                    }
                }

                if (name != null && portal != null) {
                    if (name in unlinked) {
                        linked[portal] = unlinked[name]!!
                        linked[unlinked[name]!!] = portal
                        unlinked.remove(name)
                    } else {
                        unlinked[name] = portal
                    }
                }
            }
        }
    }
    return Triple(linked, unlinked["AA"]!!, unlinked["ZZ"]!!)
}

There’s quite a bit to this, so let’s go over it. We’ll set up two maps for linked and unlinked portals. When we run into a portal for the first time, we’ll record its name and location. When we see its pair, we’ll record them both in the linked portals map, remembering that we need to link them both ways (A->B and B->A).

Then we will loop through the entire maze and find anything that is a letter. Our process is going to be to link portals as soon as we detect one. We are scanning east to west and then north to south. That means we have to scan either above, below, or to the side of the first character we find. If we find a character, we figure out which direction we’re looking at by comparing the neighboring spot (which also must be a letter), and the other neighbor which must be an open spot in the maze.

As we find portals, we record them either in linked or unlinked, depending on whether we’ve seen it already.

In the end, we return a Triple which has the linked portals map and the start and end points.

We’ll define all of that as properties of our class:

class Day20(input: List<String>) {

    private val maze: Set<Point2D> = parseMaze(input)
    private val portalData = linkPortals(input)
    private val portals: Map<Point2D, Point2D> = portalData.first
    private val begin: Point2D = portalData.second
    private val end: Point2D = portalData.third

}

⭐ Day 20, Part 1

The puzzle text can be found here.

Now that we’ve done most of the input parsing, we don’t have all that much to do to solve Part 1. To do this, we’ll write a breadth first search to find our way through the maze.

private fun bfs(): Int {
    val discovered = mutableSetOf<Point2D>().apply {
        add(begin)
    }
    val queue = ArrayDeque<MutableList<Point2D>>().apply {
        add(mutableListOf(begin))
    }

    while (queue.isNotEmpty()) {
        val here = queue.pop()
        if (here.first() == end) {
            return here.size - 1
        }
        here.first().neighborsWithPortals().forEach { neighbor ->
            if (neighbor !in discovered) {
                discovered.add(neighbor)
                queue.addLast(here.copyOf().also { it.add(0, neighbor) })
            }

        }
    }
    throw IllegalStateException("No path to end")
}

We will need to keep track of every point we’ve already evaluated (discovered). This prevents us from evaluating paths that we’ve already considered. We also need a queue, which contains lists of points (a path). We’ll initialize this queue with the starting spot.

While we still have paths to evaluate, we will evaluate them one at a time. If the path we’re evaluating is the end, we’ve done! Otherwise, we need to find all of the eligible neighbors for the spot at the tip of the path, and add new paths to the queue for each one of them.

The trick to solving part 1 depends on how we pick neighbors:

private fun Point2D.neighborsWithPortals(): List<Point2D> {
    val neighbors = this.neighbors().filter { it in maze }
    return (neighbors + portals[this]).filterNotNull()
}

In this case, we need to find neighbors of the current spot that are both in the maze and are portals. If we’re standing on a portal endpoint, we can treat the corresponding portal destination as a “neighbor”.

Calling this function solves part 1:

fun solvePart1(): Int =
    bfs()

Star earned!

⭐ Day 20, Part 2

The puzzle text can be found here.

To solve part 2, we’ll use a similar approach to part 1, but we’ll keep track of the level we’re on. The level in this case represents how many mazes we’ve traversed in and out of. The outermost maze is level 0, one in from that is level 1, and so on.

In order to know which direction we’re going (+1 level or -1 level) we need to know what kind of portal we’ll be going through. If it is on the outer edge, we’re going outward (-1), otherwise, inward. So we’ll calculate those values in advance:

private val outwardX = setOf(2, input.first().length - 3)
private val outwardY = setOf(2, input.size - 3)

Other than the fact that we need to account for the level, our BFS looks mostly the same. We need to take care that we can only exit the maze on level 0. So if we run into ZZ on any other level, it is not an endpoint.

private fun bfsLeveled(): Int {
    val discovered = mutableSetOf<Pair<Point2D, Int>>().apply {
        add(begin to 0)
    }
    val queue = ArrayDeque<MutableList<Pair<Point2D, Int>>>().apply {
        add(mutableListOf(begin to 0))
    }

    while (queue.isNotEmpty()) {
        val path = queue.pop()
        if (path.first() == end to 0) {
            return path.size - 1
        }
        path.first().neighborsWithPortalsAndLevels().filterNot { it in discovered }.forEach { neighbor ->
            discovered.add(neighbor)
            queue.addLast(path.copyOf().also { it.add(0, neighbor) })
        }
    }
    throw IllegalStateException("No path to end")
}

Much like Part 1, the trick to solving part 2 is the careful selection on neighboring spots. The complication is, of course, how many levels into the maze we are. We need to add adjacent portals and keep track of whether we are going inward to another maze, or outward to a maze we came from. Any other neighbor that isn’t a portal is on the same level we’re traversing currently. We calculate the difference in level (levelDiff) by looking to see if we are standing on the outer edge of the maze or not. If we are, we’re about to transport to an outer maze (-1 level), otherwise we are going inward (+1 level).

We also need to make sure that we don’t traverse to any negative levels.

private fun Pair<Point2D, Int>.neighborsWithPortalsAndLevels(): List<Pair<Point2D, Int>> {
    val neighbors = this.first.neighbors().filter { it in maze }.map { Pair(it, this.second) }.toMutableList()
    portals[this.first]?.let {
        val levelDiff = if (this.first.x in outwardX || this.first.y in outwardY) -1 else 1
        neighbors.add(it to this.second + levelDiff)
    }
    return neighbors.filter { it.second >= 0 }

And to solve Part 2, we call our new function:

fun solvePart2(): Int =
    bfsLeveled()

Star earned!

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading