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

Kotlin solutions to parts 1 and 2 of Advent of Code 2023, Day 5: 'If You Give A Seed A Fertilizer'

Posted on

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.