Advent of Code 2023 - Day 5, in Kotlin - If You Give A Seed A Fertilizer • Todd Ginsberg

I’ll admit that when I saw part 2 my first thought was “well, how the heck am I going to do that?”, but it turns out that taking what we write for part 1 and reversing everything works.

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

Puzzle Input

I found parsing today’s puzzle a bit challenging because of the all the newlines, but I eventually figured it out. It’s perhaps a bit of a spoiler but part 2 calls for parsing the seed row a different way, so we’ll have a seedsPart1 value and a parsePart1Seeds function. The ranges can be used as is (mostly!) for part 2 so we’ll accomplish that with parseRanges.

class Day05(input: List<String>) {

    private val seedsPart1: List<Long> = parsePart1Seeds(input)
    private val ranges: List<Set<RangePair>> = parseRanges(input)

    private fun parsePart1Seeds(input: List<String>): List<Long> =
        input.first().substringAfter(":").trim().split(" ").map { it.toLong() }

    private fun parseRanges(input: List<String>): List<Set<RangePair>> =
        input.drop(2).joinToString("\n").split("\n\n").map {
            it.split("\n").drop(1).map { line -> RangePair.of(line) }.toSet()
        }
}

Parsing the seeds is somewhat straight forward as we can use the first line of input. Then we get everything after the : using our old friend substringAfter, taking care to trim the results before splitting on space. This means we have individual strings representing each seed, so we map them to Long.

In order to parse the ranges we will need to do some work. Because the first two lines of input are the seeds and an empty line, we can drop those right away. The way I’ve chosen to break the resulting List<String> up into chunks of ranges (a List<List<String>>, where each inner List<String> is a chunk of ranges), is to joinToString all of the elements of input using \n as the delimiter, and then using split to break it up again whenever we see two newlines. I wish there were a split { predicate }. Maybe I’ll need it in the future and we’ll have to write one.

Once we have a chunk of ranges, we split them again, and drop the first one (the header row, which we do not care about) and map each of the remaining lines to a RangePair (see below!). Once we have that, we’ll turn those into a Set (because order of the RangePair objects within a section is not important in this case).

Let’s take a look at RangePair, which, once again, I worked overtime to name.

// In Day05

private data class RangePair(
    private val source: LongRange,
    private val destination: LongRange
) {

    fun translate(num: Long): Long =
        destination.first + (num - source.first)

    operator fun contains(num: Long): Boolean =
        num in source

    companion object {
        fun of(row: String): RangePair {
            val parts = row.split(" ").map { it.toLong() }
            return RangePair(
                parts[1]..<(parts[1] + parts[2]),
                parts[0]..<(parts[0] + parts[2])
            )
        }
    }
}

The Plan - Why Use RangePair At All?

Picture each map (seed-to-soil, etc) as a pair of ranges. We’re asked to take some number (a seed in part 1) and test it against the source range. If the range includes the test number, we need to translate that value to a corresponding value in the destination range. Otherwise, the number passes through our map as-is. We can assume that each map will have several RangePair objects associated with it (this is why we store them in a Set<RangePair>).

The use of RangePair facilitates the translation of values from a source range to a destination range.

RangePair has two LongRange properties. One for the source side of the map, one for the destination side of the map.

The translate function allows us to convert a num from the source side to a number on the destination side. We assume that the caller has tested to make sure the num exists in the range already. We can convert from source to destination by adding a quantity to the lowest number in the destination range equal to the difference between num and the lowest number of the source range.

We will parse our row of input in the companion object via the of function. We split the row on space and map each result to Long, using them to create two LongRange objects. Because we don’t want the range to be inclusive of the end value, we’ll use Kotlin’s handy ..< operator instead of the upTo function (either works fine).

While we’re here, let’s define an operator contains on the RangePair to allow easier tests if a number is in the source side of the pair.

⭐ Day 5, Part 1

The puzzle text can be found here.

We can go directly to a solution to part 1 now, since we have RangePair doing most of the work.

// In Day05

fun solvePart1(): Long =
    seedsPart1.minOf { seed ->
        ranges.fold(seed) { acc, ranges ->
            ranges.firstOrNull { acc in it }?.translate(acc) ?: acc
        }
    }

The first thing we do is iterate through each of our seedsPart1 list, and ask Kotlin to find the minOf the output of our lambda. The lambda function takes the seed, passes it through a fold operation over all of the ranges. If you’ve never seen fold, it is a great tool for situations like this - where you need to take the output of some function and feed it back to itself.

For example, let’s pretend we want to calculate the sum of some numbers in a List<Int> (presumably without using sum()).

We could do this iteratively:

var sum = 0
ourNumbers.forEach { sum += it }

Or we could use a functional fold:

val sum = ourNumbers(0) { accumulatedValue, nextValue -> accumulatedValue + nextValue }

It looks like a lot more code because I used long, descriptive variable names. But the benefit is that fold will do all of this work as a single function chain, whereas our iterative solution relies on side-effects (note that sum is a var in the iterative case but a val in the functional fold case).

So now we know why we use fold, we can see that we carry the accumulated (acc) value along and operate on each Set<RangePair>. Because ranges is a Set<RangePair>, we need to find the fist RangePair that contains the acc value. We do this by calling firstOrNull and testing for inclusion via in, which calls our contains operator function. If this chain of calls returns null, we take the acc value as-is.

Running this will pass each seed through the chain of maps, and we’ll take the minimum value as our answer.

Star earned! Onward!

⭐ Day 5, Part 2

The puzzle text can be found here.

The strategy for part 2 is nearly identical to part 1 except we’re going to do everything in reverse. This isn’t the speediest implementation out there. On my laptop this finishes in anywhere between 1.1s to 1.4s when the JUnit test I have is run within IntelliJ. It is certainly faster than trying to brute force our way out of this by testing each seed in each seed range and running part 1 over and over again.

We still use the same fold mechanism to move between ranges, but we reverse all of the values, and traverse them in reverse. Meaning: start with an arbitrary location (let’s say, 0) and keep increasing the location values until one of them generates a number that is in one of the seed ranges. This will be the lowest numbered location.

To do this, let’s add a flip function to RangePair in order to make reversing them easier. Thankfully, this only involves switching the destination and source ends around.

// In RangePair

fun flip(): RangePair =
    RangePair(destination, source)

Now we can write our solution to part 2. First, we’ll reverse all of the ranges by mapping each of the RangePair objects to its flip version.

// In Day05 

fun solvePart2(): Long {

    val rangesReversed = ranges.map { range -> range.map { it.flip() } }.reversed()

    return generateSequence(0L, Long::inc).first { location ->
        val seed = rangesReversed.fold(location) { acc, ranges ->
            ranges.firstOrNull { acc in it }?.translate(acc) ?: acc
        }
        seedsPart2.any { seedRange -> seed in seedRange }
    }
}

Next, we use Kotlin’s generateSequence function to generate larger and larger Long values. It takes two values, first 0L as the location to start with, and Long::inc as the function to call to generate the next location. In our case the inc function on Long increases its value by 1. Alternatively, we could have called this in a lambda (generateSequence(0) { it + 1} ...).

Once we have a sequence, we keep executing our lambda (described further on) until the first time it returns true. The lambda/test is the same as part 1 - we fold over the rangesReversed and accumulate answers as we walk through the sets of ranges. At the end, that will leave us a seed (as opposed to a location in part 1). Now we can test to figure out if any of the ranges in the seedsPart2 set contain the seed we generated. If we do find something, that’s our answer. Otherwise generateSequence will increase the location by 1 and perform the calculation over again.

Star earned! See you tomorrow.

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Further Reading