Advent of Code 2024 - Day 20, in Kotlin - Race Condition • Todd Ginsberg

If all the contestants in this race can “cheat” with the same deterministic rules, doesn’t that bring them back where they started? Boring, deterministic races? Either way, it feels like these rules could also apply to a game of Candy Land , which also has a single track.

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

Puzzle Input

Today we’ll take our input in as a List<String> but not declare it as a property since we’ll parse it into a more usable form right away. We only need the single path through the maze, so we’ll store that as a List<Point2D> from start to finish.

class Day20(track: List<String>) {

    private val path: List<Point2D> = parseTrack(track)

    private fun parseTrack(input: List<String>): List<Point2D> {
        val end = input.findSingle('E')
        return mutableListOf(input.findSingle('S')).apply {
            while (last() != end) {
                add(
                    last()
                        .cardinalNeighbors()
                        .filter { input[it.y][it.x] != '#' }
                        .first { it != getOrNull(lastIndex - 1) }
                )
            }
        }
    }
}

Our parseTrack function finds the end and then creates a mutableList with the starting point in it already. While the last element of the list we’re building isn’t the end, we follow the path along. We get the cardinalNeighbors for the last point in the list, filter out any that are walls, and find the single one remaining that is the path forward. We do this by checking the last-1 element in the list we’re building as that is the only place that could be returned by cardinalNeighbors that we could have visited already.

Since we seem to need to find a single thing among a grid quite frequently, we’ll add findSingle to our Extensions file. Its job is to find the Point2D that a given target can be found at and assumes the target is always found.

// In Extensions.kt

fun List<String>.findSingle(target: Char): Point2D =
    flatMapIndexed { y, row ->
        row.mapIndexedNotNull { x, c ->
            if (c == target) Point2D(x, y) else null
        }
    }.first()

Strategy and Shared Code

Like yesterday, we can share a solution between parts 1 and 2 without any changes. Here we are 20 days into Advent of Code and we finally need a Manhattan Distance function for our Point2D. It feels like past years have needed this a lot earlier. Anyway, I copied distanceTo from my 2023 code, it calculates the Manhattan distance between two Point2D objects by taking the absolute difference in the x and y values. Feel free to make this infix and not use dots to make a.distanceTo(b) look like a distanceTo b if you want.

// In Point2D

fun distanceTo(other: Point2D): Int =
    (x - other.x).absoluteValue + (y - other.y).absoluteValue

Strategy

Since we have an in-order List of Point2D objects, we can determine how many picoseconds apart any two elements are via their relative indexes. Given that, we can compare all pairs of possible cheat start and cheat end points to see which ones are in the right positions given a savingsGoal (the minimum amount of time savings we want to consider worth cheating for), and a cheatTime (how long we’re able to cheat for).

// In Day20

private fun findCheats(savingsGoal: Int, cheatTime: Int): Int =
    path.indices.sumOf { start ->
        (start + savingsGoal..path.lastIndex).count { end ->
            val physicalDistance = path[start].distanceTo(path[end])
            physicalDistance <= cheatTime && physicalDistance <= end - start - savingsGoal
        }
    }

We start by looking at all the indices of the path, calling that the start point. We’ll take the sumOf any cheats we can make from this start point. Inside this loop, we need to find the end points that are worth evaluating. Since we know we’re looking to hit a specific savingsGoal, we can immediately remove end points from consideration that are closer (in picoseconds) to the start. Therefore, we set up a range of start + savingsGoal to the last index of the path. We call this the end of the possible cheating route.

We count any start/end points that meet some criteria for inclusion. To make this calculation we need the physicalDistance between the start and end points to see if we’re able to get there within the cheatTime. To be included, we need the physicalDistance to be less than the cheatTime (meaning: can we physically traverse from start to end within the cheatTime) and we also need to know if this saves us anything by subtracting the start and savingsGoal from the end. If that value is less than the physicalDistance we’ve saved enough time and we can count this start/end pair.

We’re now ready to solve both parts of the puzzle.

⭐ Day 20, Part 1

The puzzle text can be found here.

Now that we’ve done all the work to write findCheats, we can call it with our cheatTime of 2 and the goal passed in from the test case (because the test values and the real values use different goals). This solves part 1.

// In Day20

fun solvePart1(goal: Int): Int =
    findCheats(goal, 2)

Star earned! Onward!

⭐ Day 20, Part 2

The puzzle text can be found here.

Passing the goal and setting the cheatTime to 20 solves part 2.

// In Day20

fun solvePart2(goal: Int): Int =
    findCheats(goal, 20)

Star earned! See you tomorrow!

Puzzle Input

Strategy and Shared Code

⭐ Day 20, Part 1

⭐ Day 20, Part 2

Further Reading