Advent of Code 2023 - Day 05
Published: 2023-12-13 22:34:20

---
title: Advent of Code 2023 - Day 05
published: true
date: 2023-12-05 00:00:00 UTC
tags: 
canonical_url: https://ericburden.work/blog/2023/12/05/advent-of-code-2023-day-05/
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Kotlin](https://kotlinlang.org/). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2023) as well. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 5 - If You Give A Seed A Fertilizer

Find the problem description [HERE](https://adventofcode.com/2023/day/5).

## The Input - It’s Honest Work

“Advent of Parsing” indeed! This was the first day I got to break out my`resourceAsLineChunks()` file reading function, though, which is pretty cool. As you might have guessed, today’s input takes a hefty amount of parsing to get it into shape. The heavy lifting is the `Map` used to trace one resource number/range to another, and it is a bit gnarly.

```kotlin

// This is a bit of a complicated type. Essentially, we are representing one
// translation from one resource type to another. For example, to the mapping of
// the 'seed-to-soil' group from the example:
//
// seed-to-soil map:
// 50 98 2
// 52 50 48
//
// is represented as ("seed", ("soil", [(98..99, -48), (50..97, 2)])). This makes
// it a bit easier to use in the code below, as the list of them can be easily
// converted to a HashMap.
typealias ResourceRangeTranslationGroup = 
  Pair<String, Pair<String, List<Pair<LongRange, Long>>>>

/**
 * This class represents the contents of the elf's Almanac
 *
 * @property seeds A list of the seed numbers in ("seed", <seed number>) format.
 * @property mappings A map used to determine what type of resource is required.
 */
data class Almanac(
    val seeds: List<Pair<String, Long>>,
    val mappings: Map<String, Pair<String, List<Pair<LongRange, Long>>>>
) {
  companion object {
    /**
     * Parse the input from a list of input chunks.
     *
     * @param chunks A list of line chunks from the input.
     * @return The parsed Almanac.
     */
    fun fromInputChunks(chunks: List<List<String>>): Almanac {
      // This bit isn't too bad. We parse the first line into a list of
      // ("seed", <number>) pairs. This is so, when we attempt to go from one
      // resource to another later on, we've tagged this number with the type
      // of resource it represents.
      val seeds =
          chunks
          .first()
          .first()
          .removePrefix("seeds: ")
          .split("\\s+".toRegex()).map {
            val seedNumber =
                it.toLongOrNull() ?: 
                  throw IllegalArgumentException("$it cannot be parsed to Long!")
            "seed" to seedNumber
          }

      // Parsing the "x-to-y map" chunks was a bit involved, so I've moved
      // that logic to its own function.
      val mappings = chunks
        .drop(1)
        .filter { it.isNotEmpty() }
        .map { parseChunk(it) }
        .toMap()

      return Almanac(seeds, mappings)
    }

    /**
     * Parse one chunk of the input file
     *
     * This is where we're using the gnarly type alias defined at the top. The 
     * idea is to produce a list that can be converted to a Map that can be used 
     * to look up, for each resource, what numbers for the next resource it needs.
     *
     * @param lines The input lines for one chunk of the input file.
     * @return An object that can become an entry in the [Almanac.mappings] map.
     */
    fun parseChunk(lines: List<String>): ResourceRangeTranslationGroup {
      // Get which resource types we're dealing with.
      val (sourceType, targetType) = lines.first().removeSuffix(" map:").split("-to-")

      // For each subsequent line in the chunk, we extract two pieces of information:
      // 1. The range of the source resource
      // 2. The magnitude of the offset of the destination resource range from 
      // the source range. This works because the source range and destination 
      // ranges are constrained to be the same size by the input.
      val rangeMappings =
          lines
              .filter { it.isNotEmpty() }
              .drop(1)
              .map { line ->
                val (destinationRangeStart, sourceRangeStart, rangeLength) =
                    line.split("\\s+".toRegex()).map {
                      // Yes, I'm being paranoid.
                      it.toLongOrNull()
                          ?: throw IllegalArgumentException("$it cannot be parsed to Long!")
                    }
                val sourceRange = sourceRangeStart until (sourceRangeStart + rangeLength)
                val rangeShift = destinationRangeStart - sourceRangeStart
                sourceRange to rangeShift // Pair<LongRange, Long>
              }
              .sortedBy { it.first.start }
      return sourceType to (targetType to rangeMappings)
    }
  }
}

class Day05(input: List<List<String>>) {

  // And this was the easy part...
  private val parsed = Almanac.fromInputChunks(input)
  
}

```

Yes, I’m serious. That was the easy part. Well, in hindsight, now that I know all the edge cases and little mistakes, it’s not _that_ bad. Still, though, get ready for round 1.

## Part One - Agricultural Delivery

You know what? It’s kind of rare that we see an elf suffering the inevitable consequences of someone _else’s_ poor design decisions. I kind of feel sorry for this guy. How is _anyone_ supposed to map out the instructions included in this almanac? Also, who numbers seeds? Seems like a system designed to fail. Maybe the almanac sellers run a paid support plan… Well, we’re here now. Time to figure out where these seeds go.

```kotlin
data class Almanac(
    val seeds: List<Pair<String, Long>>,
    val mappings: Map<String, Pair<String, List<Pair<LongRange, Long>>>>
) {

  // companion object { ... }
  
  /**
   * Given a resource, traces it's requirements all the way to a location
   *
   * This is why I'm tagging the resource numbers like ("seed", 1). So I can 
   * pass that pair to this function and have it recursively search through the 
   * [Almanac] until the corresponding location is found.
   *
   * @param resource A pair of ("resource type", <number>) to find the location for.
   * @return A pair of ("location", <location number>)
   */
  fun resourceToLocation(resource: Pair<String, Long>): Pair<String, Long> {
    val (type, id) = resource
    if (type == "location") return resource

    // Get the mappings of source type ranges to destination type ranges
    val (destinationType, possibleDestinations) =
        mappings.get(type)
            ?: throw IllegalArgumentException("Could not find a destination for $type.")

    // If there is a matching mapping, then map the source number to the
    // destination number and return it.
    try {
      val destination =
          possibleDestinations
              .filter { (range, _) -> id in range }
              .map { (_, offset) -> id + offset }
              .single()
      return this.resourceToLocation(destinationType to destination)
    } catch (e: Exception) {
      // If there is no mapping, then we know that the destination number
      // is the same as the source number.
      return this.resourceToLocation(destinationType to id)
    }
  }
}

class Day05(input: List<List<String>>) {

  // Told you this was the easy part.
  // private val parsed = ...

  // In part one, we have a few seeds to follow all the way to their
  // ideal planting locations. Easy enough.
  fun solvePart1(): Long =
      parsed.seeds.map { parsed.resourceToLocation(it) }.minOf { (_, id) -> id }

```

Ok, fine, that wasn’t _too_ bad. But wait, there’s more!

## Part Two - Sow, Sow Many

I seriously doubt the elf has access to the literal _billions_ of _unique_ seeds indicated by this almanac. Not to mention all those unique locations! How big is this island, anyway. Not that big, that’s for sure. In part two, it seems we’ve once again misinterpreted plain text and the seed “numbers” are seed number “ranges”. We still need to find the closest location (which kind of makes sense, some of these are probably in outer space), though, but individually tracing each seed to its location isn’t going to cut it.

```kotlin
data class Almanac(
    val seeds: List<Pair<String, Long>>,
    val mappings: Map<String, Pair<String, List<Pair<LongRange, Long>>>>
) {

  // companion object { ... }
  
  // fun resourceToLocation(resource: Pair<String, Long>): Pair<String, Long> { ... }
  
  /**
   * Given a range of resource numbers, return all the possible location ranges
   *
   * In Part 2, the numbers are just too big for us to map each seed to its 
   * location individually. Instead, we need to map the resources by the entire 
   * range. The catch here is that the input range won't always slot neatly 
   * inside an output range and may instead encompass several ranges.
   * For that reason, we return a list of ("resource type", <range>) pairs.
   *
   * @param resourceRange A pair of ("resource type", <range>) to find location 
   * ranges for.
   * @return A list of all the location ranges the input range maps to.
   */
  fun resourceRangeToLocationRanges(
      resourceRange: Pair<String, LongRange>
  ): List<Pair<String, LongRange>> {
    val (type, sourceRange) = resourceRange
    if (type == "location") return listOf(resourceRange) // Base case

    val (destinationType, possibleDestinations) =
        mappings.get(type)
            ?: throw IllegalArgumentException("Could not find a destination for $type.")
    // Still paranoid

    // This will house all the destination ranges we find.
    var destinationRanges = mutableListOf<LongRange>()

    // If the `sourceRange` starts before the first `possibleDestinationRange`, 
    // then we need to add that non-overlapping part to the destinations as-is
    val (firstPossibleDestinationRange, _) = possibleDestinations.first()
    if (sourceRange.start < firstPossibleDestinationRange.start) {
      val prefixRangeEnd = minOf(
        sourceRange.endInclusive + 1, 
        firstPossibleDestinationRange.start
      )
      val prefixRange = sourceRange.start until prefixRangeEnd
      destinationRanges.add(prefixRange)
    }

    // Now, check over all the `possibleDestinations` and, for every destinationRange
    // that overlaps `range`, apply the offset to the overlapping portion of `range`
    // and add it to the destinations
    for ((destinationRange, destinationOffset) in
        possibleDestinations.sortedBy { it.first.start }) {
      if (sourceRange.start <= destinationRange.endInclusive &&
              destinationRange.start <= sourceRange.endInclusive
      ) {
        val overlappingRangeStart = maxOf(sourceRange.start, destinationRange.start)
        val overlappingRangeEnd = minOf(
          sourceRange.endInclusive, 
          destinationRange.endInclusive
        ) + 1
        val overlappingRange =
            (overlappingRangeStart + destinationOffset) until
                (overlappingRangeEnd + destinationOffset)
        destinationRanges.add(overlappingRange)
      }
    }

    // Finally, if `sourceRange` extends past the end of the last `destinationRange`,
    // then we need to add that non-overlapping part to the destinations as-is.
    var (lastPossibleDestinationRange, _) = possibleDestinations.last()
    if (sourceRange.endInclusive > lastPossibleDestinationRange.endInclusive) {
      val suffixRangeStart = maxOf(
        sourceRange.start, 
        lastPossibleDestinationRange.endInclusive + 1
      )
      val suffixRange = suffixRangeStart until sourceRange.endInclusive + 1
      destinationRanges.add(suffixRange)
    }

    // Now with our list of destination ranges, we need to recursively search
    // for the ranges of the final locations.
    return destinationRanges
        .map { this.resourceRangeToLocationRanges(destinationType to it) }
        .flatten()
  }
}

class Day05(input: List<List<String>>) {

  // Told you this was the easy part.
  // private val parsed = ...

  // How you like me now?
  // fun solvePart1(): Long = ...
  
  // In part two, we have a _tremendous_ number of seeds to track down.
  // Instead, we need to keep track of ranges of numbers to finish in a
  // reasonable amount of time.
  fun solvePart2(): Long {
    // Convert the seed numbers to ranges as specified in the puzzle text.
    val seedRanges =
        parsed.seeds.chunked(2) { (first, second) ->
          val (_, rangeStart) = first
          val (_, rangeLength) = second
          "seed" to (rangeStart until (rangeStart + rangeLength))
        }

    // For all the possible location ranges, find the smallest possible location.
    return seedRanges
        .map { seedRange -> parsed.resourceRangeToLocationRanges(seedRange) }
        .flatten()
        .minOf { (_, range) -> range.start }
  }
}

```

Yes, _of course_ I tried searching the seeds one at a time. What do you take me for? No, it didn’t work. I exceeded the JVM’s memory allocation. I could have_probably_ worked around that, but the algorithm change seemed like the right idea.

## Wrap Up

That was Day **5**!? I checked, and last year Day 5 was the crate-moving day. And yes, while that _did_ require a bit of tricky parsing (assuming you didn’t just hard-code the input), the algorithm bit was simplicity itself. And that took me around 260 lines of _Rust_ code (which is heckin’ verbose) compared to today’s 222 lines of Kotlin code. That probably doesn’t seem like a bad comparison, but you have to remember that Rust tends to have a _lot_ (relatively) of boilerplate. Strip all the comments, and it might even be _less_ Rust code. Typically, by this point, I’d expect either a bit of a tougher parse or a bit of a trickier algorithm, but today was a double whammy. Now, I’m not complaining, mind you, I enjoy a good challenge. Given how the last few days have gone, though, I’m starting to get a bit concerned for my sleep schedule! We’ll see what Day 6 has in store.