AoC 2023 Day 5

Day5.scala

package net.tazato

import cats.*
import cats.data.NonEmptyList
import cats.effect.*
import cats.parse.Parser as P
import cats.parse.Numbers.digits
import cats.parse.Rfc5234.lf
import cats.parse.Rfc5234.wsp
import cats.syntax.all.*

import scala.collection.immutable.NumericRange

enum Almanac(val start: Long, val end: Long) {
  case Seed(s: Long, e: Long)        extends Almanac(s, e)
  case Soil(s: Long, e: Long)        extends Almanac(s, e)
  case Fertilizer(s: Long, e: Long)  extends Almanac(s, e)
  case Water(s: Long, e: Long)       extends Almanac(s, e)
  case Light(s: Long, e: Long)       extends Almanac(s, e)
  case Temperature(s: Long, e: Long) extends Almanac(s, e)
  case Humidity(s: Long, e: Long)    extends Almanac(s, e)
  case Location(s: Long, e: Long)    extends Almanac(s, e)
}

case class FullAlmanac(
    firstSeeds: NonEmptyList[Long],
    seedsToSoil: Map[Almanac.Seed, Almanac.Soil],
    soilToFertilizer: Map[Almanac.Soil, Almanac.Fertilizer],
    fertilizerToWater: Map[Almanac.Fertilizer, Almanac.Water],
    waterToLight: Map[Almanac.Water, Almanac.Light],
    lightToTemperature: Map[Almanac.Light, Almanac.Temperature],
    temperatureToHumidity: Map[Almanac.Temperature, Almanac.Humidity],
    humidityToLocation: Map[Almanac.Humidity, Almanac.Location]
)

trait AlmanacOps[A <: Almanac] {
  def make(start: Long, end: Long): A
}
object AlmanacOps {
  import Almanac.*
  def apply[A <: Almanac](start: Long, end: Long)(using ops: AlmanacOps[A]): A =
    ops.make(start, end)

  given AlmanacOps[Seed]        = (s, e) => Seed(s, e)
  given AlmanacOps[Soil]        = (s, e) => Soil(s, e)
  given AlmanacOps[Fertilizer]  = (s, e) => Fertilizer(s, e)
  given AlmanacOps[Water]       = (s, e) => Water(s, e)
  given AlmanacOps[Light]       = (s, e) => Light(s, e)
  given AlmanacOps[Temperature] = (s, e) => Temperature(s, e)
  given AlmanacOps[Humidity]    = (s, e) => Humidity(s, e)
  given AlmanacOps[Location]    = (s, e) => Location(s, e)
}

object Day5 extends IOApp.Simple {
  import Almanac.*

  def overlaps[A <: Almanac](
      input: NumericRange[Long],
      a: A
  ): Option[List[NumericRange[Long]]] =
    if (input.start > a.end || a.start > input.end) None
    else List((input.start max a.start) to (input.end min a.end)).some

  def traverse[A <: Almanac, B <: Almanac](
      m: Map[A, B],
      input: NumericRange[Long]
  ): List[NumericRange[Long]] = {
    val overlap: List[NumericRange[Long]] =
      m.keys.filter(k => overlaps(input, k).isDefined).toList.flatMap { k =>
        val overlap = overlaps(input, k).get
        val lowerRange = Option
          .when(input.start < k.start)(traverse(m, input.start to k.start - 1))
        val upperRange =
          Option.when(input.end > k.end)(traverse(m, k.end + 1 to input.end))
        val offsetFromStart = overlap.head.start - k.start
        val offsetFromEnd   = k.end - overlap.head.end
        val destination     = m(k)
        val rangeInDestination =
          (destination.start + offsetFromStart) to (destination.end - offsetFromEnd)
        (lowerRange ++ List(rangeInDestination.some) ++ upperRange).flatten
      }
    if overlap.isEmpty then input :: Nil
    else overlap
  }

  def totalTraverse(input: List[NumericRange[Long]], fullAlmanac: FullAlmanac) =
    List(
      fullAlmanac.seedsToSoil,
      fullAlmanac.soilToFertilizer,
      fullAlmanac.fertilizerToWater,
      fullAlmanac.waterToLight,
      fullAlmanac.lightToTemperature,
      fullAlmanac.temperatureToHumidity,
      fullAlmanac.humidityToLocation
    ).foldLeft(input) { (acc, m) =>
      acc.flatMap(traverse(m, _))
    }.minBy(_.start)
      .start

  val input = io.Source.fromResource("day5.txt").mkString

  val part1F: IO[Unit] = IO
    .delay {
      val parsed = parse.fullAlmanac.parseAll(input)
      parsed match {
        case Left(e) =>
          IO.raiseError(new Throwable(s"Failed to parse input:\n${e.show}"))
        case Right(almanac) =>
          totalTraverse(almanac.firstSeeds.toList.map(s => s to s), almanac)
      }
    }
    .flatMap(IO.println)

  val part2F: IO[Unit] = IO
    .delay {
      val parsed = parse.fullAlmanac.parseAll(input)
      parsed match {
        case Left(e) =>
          IO.raiseError(new Throwable(s"Failed to parse input:\n${e.show}"))
        case Right(almanac) =>
          val allTheSeeds = almanac.firstSeeds.toList
            .grouped(2)
            .map(p => p.head to (p.head + p.last - 1))
            .toList
          totalTraverse(allTheSeeds, almanac)
      }
    }
    .flatMap(IO.println)

  override def run: IO[Unit] = part1F

  object parse {
    case class MapLine(destination: Long, source: Long, length: Long)

    case class FirstSeeds(seeds: List[Long])

    val mapLine = (
      digits.map(_.toLong) <* wsp,
      digits.map(_.toLong) <* wsp,
      digits.map(_.toLong) <* lf.?
    ).mapN(MapLine.apply)

    def parseAlmanacMap[A <: Almanac, B <: Almanac](
        h: String
    )(using ma: AlmanacOps[A], mb: AlmanacOps[B]): P[Map[A, B]] =
      (P.string(h) *> mapLine.rep <* lf).map(
        _.toList
          .map[(A, B)] { ml =>
            ma.make(ml.source, ml.source + ml.length - 1) -> mb.make(
              ml.destination,
              ml.destination + ml.length - 1
            )
          }
          .toMap
      )

    val firstSeeds = P.string("seeds:") *> digits.rep.string
      .map(_.toLong)
      .surroundedBy(wsp.rep0)
      .rep <* lf.rep0

    val seedToSoil: P[Map[Seed, Soil]] =
      parseAlmanacMap[Seed, Soil]("seed-to-soil map:\n")

    val soilToFertilizer: P[Map[Soil, Fertilizer]] =
      parseAlmanacMap[Soil, Fertilizer]("soil-to-fertilizer map:\n")

    val fertilizerToWater: P[Map[Fertilizer, Water]] =
      parseAlmanacMap[Fertilizer, Water]("fertilizer-to-water map:\n")

    val waterToLight: P[Map[Water, Light]] =
      parseAlmanacMap[Water, Light]("water-to-light map:\n")

    val lightToTemperature: P[Map[Light, Temperature]] =
      parseAlmanacMap[Light, Temperature]("light-to-temperature map:\n")

    val temperatureToHumidity: P[Map[Temperature, Humidity]] =
      parseAlmanacMap[Temperature, Humidity]("temperature-to-humidity map:\n")

    val humidityToLocation: P[Map[Humidity, Location]] =
      parseAlmanacMap[Humidity, Location]("humidity-to-location map:\n")

    val fullAlmanac = (
      firstSeeds,
      seedToSoil,
      soilToFertilizer,
      fertilizerToWater,
      waterToLight,
      lightToTemperature,
      temperatureToHumidity,
      humidityToLocation
    ).mapN { case (seeds, s2, s3, s4, s5, s6, s7, s8) =>
      FullAlmanac(seeds, s2, s3, s4, s5, s6, s7, s8)
    }
  }
}

Day5Suite.scala

package net.tazato

import cats.syntax.all.*
import Day5.*
import weaver.*
import Day5.AlmanacParse.MapLine
import Day5.AlmanacParse.mapLine

object Day5Suite extends SimpleIOSuite {

  val example =
    """seeds: 79 14 55 13
      |
      |seed-to-soil map:
      |50 98 2
      |52 50 48
      |
      |soil-to-fertilizer map:
      |0 15 37
      |37 52 2
      |39 0 15
      |
      |fertilizer-to-water map:
      |49 53 8
      |0 11 42
      |42 0 7
      |57 7 4
      |
      |water-to-light map:
      |88 18 7
      |18 25 70
      |
      |light-to-temperature map:
      |45 77 23
      |81 45 19
      |68 64 13
      |
      |temperature-to-humidity map:
      |0 69 1
      |1 0 69
      |
      |humidity-to-location map:
      |60 56 37
      |56 93 4
      |
      |""".stripMargin

  pureTest("traverse works as expected") {
    import Almanac.*
    val m: Map[Seed, Soil] = Map(
      Seed(98, 98 + 2)  -> Soil(50, 50 + 2),
      Seed(50, 50 + 48) -> Soil(52, 52 + 48)
    )
    val result = traverse(m, 55L to 55L)
    expect(result.head.start == 57)
  }

  pureTest("map line parse works") {
    val line = "50 98 2\n"
    mapLine.parseAll(line) match
      case Left(e)      => failure(s"parse failed: \n${e.show}")
      case Right(value) => expect.same(value, MapLine(50, 98, 2))
  }

  pureTest("seed to soil parser works") {
    import Almanac.*
    val line =
      """seed-to-soil map:
        |50 98 2
        |52 50 48
        |
        |""".stripMargin

    Day5.AlmanacParse.seedToSoil.parseAll(line) match
      case Left(e) => failure(s"parse failed: \n${e.show}")
      case Right(value) =>
        expect.same(
          value,
          Map(
            Seed(98, 99) -> Soil(50, 51),
            Seed(50, 97) -> Soil(52, 99)
          )
        )
  }

  pureTest("first two maps work") {
    import Day5.AlmanacParse.*
    val input =
      """seed-to-soil map:
        |50 98 2
        |52 50 48
        |
        |soil-to-fertilizer map:
        |0 15 37
        |37 52 2
        |39 0 15
        |
        |""".stripMargin
    (seedToSoil ~ soilToFertilizer).parseAll(input) match
      case Left(e)      => failure(s"parse failed: \n${e.show}")
      case Right(value) => success

  }

  pureTest("full example parse works") {

    Day5.AlmanacParse.fullAlmanac.parseAll(example) match
      case Left(e)      => failure(s"parse failed: \n${e.show}")
      case Right(value) => success

  }

  pureTest("full actual parse works") {
    val input = Day5.input
    Day5.AlmanacParse.fullAlmanac.parseAll(input) match
      case Left(e)      => failure(s"parse failed: \n${e.show}")
      case Right(value) => success
  }

  pureTest("full traverse works") {
    Day5.AlmanacParse.fullAlmanac.parseAll(example) match
      case Left(e) => failure(s"parse failed: \n${e.show}")
      case Right(almanac) =>
        val result = Day5.totalTraverse((13L to 13L) :: Nil, almanac)
        expect(result == 35)
  }

  pureTest("full traverse all inputs works") {
    Day5.AlmanacParse.fullAlmanac.parseAll(example) match
      case Left(e) => failure(s"parse failed: \n${e.show}")
      case Right(almanac) =>
        val result = Day5.totalTraverse(almanac.firstSeeds.toList.map(s => s to s), almanac)
        expect.same(result, 35)
  }

  test("full actual answer part 1") {
    Day5.part1F.map { result =>
      expect.same(result, 457535844)
    }
  }

  test("full actual answer part 2") {
    Day5.part2F.map { result =>
      expect.same(result, 41222968)
    }
  }
}