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

I know this one is late, and I had a lot of trouble getting it to actually work for each of the test cases. If there’s an overall theme for this one, it’s that order matters. You’ll see corner cases pop up or disappear over and over again if ordering isn’t precise. Most essential is understanding what reader order is, and paying attention to movement and target finding.

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

Problem Input

We are given a picture of the caves as a single input file. We will handle it in Part 1 below.

⭐ Day 15, Part 1

The puzzle text can be found here.

Parsing The Cave

Our cave is similar to past examples so we will parse it into an Array<CharArray>. We will be mutating the cave, and part 2 calls for us to reset the cave to its original state, so we will do the work in a function we can call, rather than as an initialized val. We also define some typealiases to make life a bit easier here as well. One for our cave, and one for a List<Point> we’ll need later.


typealias Caves = Array<CharArray>
typealias Path = List<Point>

class Day15(private val rawInput: List<String>) {

    private var caves: Caves = parseCaves()
    private var fighters: List<Fighter> = Fighter.findFighters(caves)

    private fun parseCaves(): Caves =
        rawInput.map { it.toCharArray() }.toTypedArray()

}

We will define the function to get our “fighters” below.

Data Classes, etc…

Let’s get some housekeeping out of the way first. We need to have a class to represent Elves and Goblins, which we’ll call Fighter. We also need a way to tell them apart, so we’ll define an enum called Team.

private enum class Team(val logo: Char) {
    Elf('E'),
    Goblin('G');

    companion object {
        fun byLogo(logo: Char): Team? =
            values().firstOrNull { logo == it.logo }
    }
}

And our Fighter data object, with its parsing logic is here. We need the entire cave in order to find the Goblins and Elves:

private data class Fighter(
    val team: Team,
    var location: Point,
    var hp: Int = 200,
    var ap: Int = 3,
    var dead: Boolean = false
) : Comparable<Fighter> {

    override fun compareTo(other: Fighter): Int =
        location.compareTo(other.location)

    companion object {
        fun findFighters(caves: Caves): List<Fighter> =
            caves.mapIndexed { y, row ->
                row.mapIndexed { x, spot ->
                    Team.byLogo(spot)?.let {
                        Fighter(it, Point(x, y))
                    }
                }
            }
                .flatten()
                .filterNotNull()
    }

}

We implement Comparable<Fighter> here so that they are ordered in reader order for when we sort them in a list. This is one of the areas where order of operations and which fighter moves first is critical.

Point

Let’s get changes to Point out of the way. We defined this as a simple data object the other day, and we’ll depend heavily on it today.

data class Point(val x: Int, val y: Int) : Comparable<Point> {

    fun distanceTo(otherX: Int, otherY: Int): Int =
        abs(x - otherX) + abs(y - otherY)

    fun distanceTo(other: Point): Int =
        distanceTo(other.x, other.y)

    fun cardinalNeighbors(allowNegative: Boolean = true): List<Point> =
        // Note: Generate in reading order!
        listOf(
            Point(x, y - 1),
            Point(x - 1, y),
            Point(x + 1, y),
            Point(x, y + 1)
        ).filter { allowNegative || it.x >= 0 && it.y >= 0 }

    override fun compareTo(other: Point): Int =
        when {
            y < other.y -> -1
            y > other.y -> 1
            x < other.x -> -1
            x > other.x -> 1
            else -> 0
        }

    companion object {
        fun of(input: String): Point =
            input.split(",")
                .map { it.trim().toInt() }
                .run { Point(this[0], this[1]) }
    }
}

The parsing and distance logic do no change, but we do have a new function to measure the distance to another Point. The comparator, once again, will sort these into reader order. The main new functionality here is to generate neighboring points. And again, these need to be done in reader order (this is the last bug that got me for long time).

A Single Round of Fighting

Most of the work for today’s problem revolves around getting the order of target selection, movement, and combat correct. We’ll call this a “round” of fighting. Essentially, we have to figure out if we’re next to an enemy already (breaking ties with reader order in the case where we have more than one), move towards a spot next to an enemy if we aren’t already there, target enemies again after we’ve moved, and attack. Order is critical, and each fighter does all of this before we move on to the next fighter.

Let’s write the code for a round of fighting and then we’ll go over it and write the supporting code:

// In Day15

private fun round(): Boolean {
    // Fighters need to be in order at the start of the round.
    // This is a sequence because we can lazily remove dead fighers before their turn,
    // otherwise we have to manually check.
    fighters.sorted().asSequence().filterNot { it.dead }.forEach { fighter ->
        // Check for premature end of the round - nobody left to fight
        if (!keepFighting()) {
            return false
        }

        // If we are already in range, stop moving.
        var target: Fighter? = fighter.inRange(fighters).firstOrNull()
        if (target == null) {
            // Movement
            val path = fighter.findPathToBestEnemyAdjacentSpot(fighters, caves)
            if (path.isNotEmpty()) {
                fighter.moveTo(path.first(), caves)
            }
            // Find target
            target = fighter.inRange(fighters).firstOrNull()
        }

        // Fight if we have a target
        target?.let {
            fighter.attack(it, caves)
        }
    }
    return true // Round ended at its natural end
}

It’s important to track that a round ends naturally. Meaning - every fighter has had their chance to participate in the round. This means that if one entire side is eliminated before the round ends, the round did not end naturally. It ended early. A corner case to watch out for is that an enemy is eliminated as the last action in a round, and that round ends combat entirely. In that case, our round did finish naturally. This was another one that caused me a some issues.

As you can see, we’ll have to add some functions on Fighter to find enemies, move, and fight. We also have a function to figure out when the round ends. It does this by counting the distinct number of teams left, and when that gets to 1, we’re done fighting.

private fun keepFighting(): Boolean =
    fighters.filterNot { it.dead }.distinctBy { it.team }.count() > 1

Let’s write our movement code in fighter first because it’s the most straight forward:

// In Fighter
fun moveTo(place: Point, caves: Caves) {
    // We need to alter the caves because we use it for pathfinding
    caves[location.y][location.x] = '.'
    location = place
    caves[location.y][location.x] = team.logo
}

It is important to alter the cave so future pathfinding efforts aren’t running into fighters that aren’t there any more.

We can also write our attack function because that is similar. We reduce our targets HP by our AP, and mark them dead if they died so we don’t keep letting them participate in a round. We need to clean up the corpses immediately so future pathfinding doesn’t get stopped by dead bodies:

// In Fighter

fun attack(target: Fighter, caves: Caves) {
    target.hp -= this.ap
    if (target.hp <= 0) {
        // Mark enemy as dead and clean up the corpse
        target.dead = true
        caves[target.location.y][target.location.x] = '.'
    }
}

The last straight forward function we can write is the one where we find enemy-adjacent spots in the cave. An enemy-adjacent spot, in addition to being a horrible description for real estate is:

Next to one of our enemies
Who is not dead
The spot is not currently occupied by anything else

// In Fighter

private fun enemyAdjacentOpenSpots(fighters: List<Fighter>, caves: Caves): Set<Point> =
   fighters
       .filterNot { it.dead }
       .filterNot { it.team == team }
       .flatMap { it.location.cardinalNeighbors().filter { neighbor -> caves[neighbor.y][neighbor.x] == '.' } }
       .toSet()

Now we have everything we need to do the tricky part…

Path Finding

An essential part of the requirements is that before a fighter moves, they have to pick the closest point in reader order to move to that is enemy-adjacent, and move there according to the best path, again, in reader order. There are cases where there are two paths to take, so we have to be careful. This, again, bit me for a long time.

Let’s write a function that given a starting spot (where our fighter is standing) and a set of target spots (our enemy-adjacent set), find the best single path to any of those spots. It’s ok if we don’t find a path, we’ll just return an empty list.

// In Fighter

private fun pathToAnyEnemy(
    enemies: Set<Point>,
    caves: Caves
): Path {
    val seen: MutableSet<Point> = mutableSetOf(location)
    val paths: Deque<Path> = ArrayDeque()

    // Seed the queue with each of our neighbors, in reading order (that's important)
    location.cardinalNeighbors()
        .filter { caves[it.y][it.x] == '.' }
        .forEach { paths.add(listOf(it)) }

    // While we still have paths to examine, and haven't found the answer yet...
    while (paths.isNotEmpty()) {
        val path: Path = paths.removeFirst()
        val pathEnd: Point = path.last()

        // If this is one of our destinations, return it
        if (pathEnd in enemies) {
            return path
        }

        // If this is a new path, create a set of new paths from it for each of its
        // cardinal direction (again, in reader order), and add them all back
        // to the queue.
        if (pathEnd !in seen) {
            seen.add(pathEnd)
            pathEnd.cardinalNeighbors()
                .filter { caves[it.y][it.x] == '.' }
                .filterNot { it in seen }
                .forEach { paths.add(path + it) }
        }
    }
    return emptyList()
}

I know that’s a lot - let’s go over it. To begin we have a queue we are always working from. This queue will give us paths in reader order (because that’s how we’ll put them in there) in increasing length from the start, fanning out across the cave. We seed this queue with a single path - the spot we are standing on.

So long as we haven’t found a path to one of our desired spots, and the queue still has paths we can look at, we can keep working. Every time we pull a possible path off the queue, we check where that path ends. If it’s one of the spots we want, great! We’re done. Otherwise we figure out if we’ve examined this spot yet. If so, we’re done for this path, there is no way to expand it. Otherwise, we get all of the neighboring points for the last spot in the path we are looking at. It’s important to get these neighboring spots in reader order. This is how paths will always expand out in reader order. It’s also important to make sure the neighboring spots aren’t occupied (meaning we can traverse them).

Now that we have a new set of neighbors to the end of our current path, we create new paths from our existing path - one for each new neighbor. If we have three valid neighbors, we have three new paths to add to the queue. It is important to record the points in the cave we’ve already seen or this will loop forever.

Running this function should produce one of two things - the single best path to the closest enemy, or no path at all.

We can invoke this by adding a function to Fighter:

// In Fighter

fun findPathToBestEnemyAdjacentSpot(
    fighters: List<Fighter>,
    caves: Caves
): Path =
    pathToAnyEnemy(
        enemyAdjacentOpenSpots(fighters, caves),
        caves
    )

Fight!

We are so close to being able to solve the problem. Remember the answer requires that we keep track of how many rounds we naturally complete. Let’s write a function to keep fighting round after round until fighting is done:

// In Day15

private fun goFightGoblins(): Pair<Int, List<Fighter>> {
    var rounds = 0
    while (round()) {
        rounds++
    }
    return Pair(rounds, fighters)
}

(Yes, I named this in a way that shows my pro-Elf bias).

Actually Solving the Problem

We’re finally here. The moment where we’ve written so much code that somehow, it must solve our problem. We’ve been through h*ck writing this code together, and I’m proud to call you all brothers and sisters.

// In Day15

fun solvePart1(): Int {
    val result = goFightGoblins()
    return result.second.filterNot { it.dead }.sumBy { it.hp } * result.first
}

Star (and a drink of your choice, you’re buying) earned! Onward!

⭐ Day 15, Part 2

The puzzle text can be found here.

The good news is we more or less have everything we need. The critical part about solving part 2 is to reset the cave and fighter state between attempts at increasing Elf AP. We can keep increasing the AP level of just the elves and fighting until we find the lowest number that causes no Elves to die. To do that, we’ll modify our goFightGoblins() function to take in a level for how much AP the Elves should have, defaulting it to 3:

// In  Day15

private fun goFightGoblins(elfAttackPoints: Int = 3): Pair<Int, List<Fighter>> {
    fighters.filter { it.team == Team.Elf }.forEach { it.ap = elfAttackPoints }
    var rounds = 0
    while (round()) {
        rounds++
    }
    return Pair(rounds, fighters)
}

Since we already have a way to run a single round we’re nearly done. Looping until we hit the magic number is all that’s left:

    fun solvePart2(): Int =
        generateSequence(4, Int::inc).map { ap ->
            // Reset
            caves = parseCaves()
            fighters = Fighter.findFighters(caves)

            val result = goFightGoblins(ap)
            if (result.second.filter { it.team == Team.Elf }.none { it.dead }) {
                result.second.filterNot { it.dead }.sumBy { it.hp } * result.first
            } else {
                null
            }
        }
            .filterNotNull()
            .first()

In this code we use an infinite sequence to keep increasing Elf AP, resetting the cave, resetting the fighters, fighting a round, and checking to see if there are any dead elves. Once we emit a non-null result from the generator, we’ve found our result!

Star earned!

⭐ Day 15, Part 1

⭐ Day 15, Part 2

Further Reading