את יום 5 של Advent Of Code השנה לקח לי הרבה זמן לעבד, למרות שבסופו של דבר הפיתרון לא היה יותר מדי מסובך. כמו תמיד בסידרה הזאת נתחיל עם תיאור התרגיל ואז פיתרון בשפת סקאלה, עם כמה מילים על סקאלה עצמה.

1. מה צריך למצוא

הקלט היום היה ארוך ומסורבל במיוחד, וזאת היתה רק ההתחלה. אנחנו עם קלט דוגמה שנראה ככה:

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

המשמעות שלו קצת משתנה בין החלקים, אבל אנחנו נתמקד כאן בחלק השני. אז שימו לב שאנחנו מתחילים עם שורה של ערכים עם התחילית seeds, ואחריה אוסף של בלוקים של "מפות". הערכים הם בעצם טווחים של ערכים, ואנחנו צריכים לזהות איך הטווחים האלה הולכים להשתנות באמצעות המפות בהמשך הטקסט. טווח מצוין על ידי המספר בו הוא מתחיל ואז גודל הטווח, אז שורת ה seeds בדוגמה מדברת על שני טווחים, הראשון מתחיל ב 79 וכולל 14 מספרים כלומר עד המספר 92 ועד בכלל, והשני מתחיל במספר 55 וגודלו 13 מספרים.

את המפות יש לקרוא בתור אוסף של כללי מיפוי, כל כלל מורכב מ-3 מספרים, המספר האמצעי אומר מאיזה מספר הטווח מתחיל, השלישי אומר מה אורך הטווח והמספר הראשון מציין את ההתחלה של טווח היעד, כך בטקסט הדוגמה המיפוי:

50 98 2

אומר שהמספר 98 ימופה למספר 50, והמספר 99 ימופה למספר 51 - או במילים אחרות, כל הטווח שמתחיל ב 98 ואורכו 2 מספרים ימופה לטווח באורך שני מספרים שמתחיל ב 50.

עכשיו המשימה - יש לקחת את הטווחים משורת ה seeds, למפות אותם דרך המפות עד שמגיעים למפה האחרונה ולהדפיס מה המספר הקטן ביותר שאפשר להגיע אליו. בנוסף מספר שאין לו מיפוי במפה מסוימת נשאר כמו שהוא ויוכל להתמפות במפה הבאה.

2. איך לגשת לזה

מה שמבלבל בתרגיל הזה הוא שטווח לא ממופה "כמו שהוא" בין מפה אחת לשניה, לדוגמה אם ניקח את כלל המיפוי:

52 50 48

ואת הטווח מ 60 עד 70 אז החיים קלים כי כל הטווח נמצא בתוך כלל המיפוי, ואז 60 ימופה ל 62, 61 ימופה ל 63 ו 69 ימופה ל 71, סך הכל הטווח מ 60 עד 70 אחרי יישום כלל המיפוי יהפוך לטווח 62 עד 72.

אבל אם הטווח שהתחלתי איתו הוא מ 40 עד 60 אז המצב יותר מסובך, כי המספרים מ 50 עד 60 ימופו לפי כלל המיפוי ויהפכו ל 52 עד 62, אבל המספרים מ 40 עד 50 יישארו כמו שהם כי כלל המיפוי לא מתאים להם, וכך מטווח מקור אחד קיבלתי מיפוי לשני טווחים במפה הבאה.

לכן לב הפיתרון יהיה פונקציה רקורסיבית שתיקח רשימה של טווחים ורשימה של כללי מיפוי, ותעביר את כל הטווחים דרך כללי המיפוי עד לקבלת רשימה חדשה של טווחים, אותה נשלח לכללי המיפוי בבלוק הבא.

3. פיתרון בסקאלה

אני מתחיל בתוספת ל Range ומוסיף פונקציה ששוברת אותו לפי Range אחר ומחזירה את החלקים מה Range שלא נמצאים ב Range השני. זה יעזור לנו להתמודד עם טווחים שנמצאים רק חלקית בתוך כלל מיפוי:

import scala.annotation.tailrec
import scala.collection.immutable.NumericRange
import scala.io.Source
import scala.util.chaining.*
import scala.util.matching.Regex

type Interval = NumericRange.Exclusive[Long]

extension (self: Interval) {
  def without(other: Interval): List[Interval] =
    if (self.isEmpty || other.isEmpty || self.end <= other.start || self.start >= other.end) {
      List(self)
    } else {
      val left = if (self.start < other.start) List(NumericRange.Exclusive[Long](self.start, other.start, step = 1)) else Nil
      val right = if (self.end > other.end) List(NumericRange.Exclusive[Long](other.end, self.end, step = 1)) else Nil
      left ++ right
    }
}

מכאן אפשר להמשיך למחלקה שמייצגת כלל מיפוי. בגלל שבכל מפה יש הרבה כללי מיפוי ולקח לי זמן להבין את התרגיל ואת התפקיד של כל חלק הלכתי על שם קצת טפשי למחלקה זו:

case class Day5Range(sourceStart: Long, destinationStart: Long, size: Long) {
  def toSourceRange: Interval =
    this.sourceStart.until(this.size + this.sourceStart)

  def getDestination(source: Interval): Interval =
    val offset = this.destinationStart - this.sourceStart
    NumericRange.Exclusive[Long](
      start = Math.max(source.start, this.sourceStart) + offset,
      end = Math.min(source.end, sourceStart + size) + offset,
      step = 1)

  def getLeftover(source: Interval): List[Interval] =
    source.without(NumericRange.Exclusive[Long](
      start = this.sourceStart,
      end = this.sourceStart + this.size,
      step = 1
    ))
}

המחלקה שומרת את שלושת המספרים וכוללת שתי פונקציות למיפוי טווחים, אחת מחזירה את טווח היעד אם טווח המקור מתאים לכלל המיפוי, והשניה תחזיר את החלק בטווח המקור שלא התאים לכלל המיפוי, במקרה שהיה צריך לשבור את הטווח לכמה חלקים.

המחלקה השניה מייצגת מפה שלמה, כלומר אוסף של כללי מיפוי. אני שמרתי גם את השם שלה למרות שהוא לא חשוב לפיתרון:

case class Day5Map(name: String, ranges: List[Day5Range]) {
  def getDestinations(sources: List[Interval]): List[Interval] =
    @tailrec
    def loop(sourceIntervals: List[Interval], destinationIntervals: List[Interval]): (List[Interval], List[Interval]) =
      sourceIntervals match
        case Nil => (sourceIntervals, destinationIntervals)
        case head :: tail =>
          this.ranges.find { r => ! r.getDestination(head).isEmpty } match
            case None => loop(tail, destinationIntervals :+ head)
            case Some(r) => loop(tail ++ r.getLeftover(head), destinationIntervals :+ r.getDestination(head))

    loop(sources, List())._2

  def withAddedRange(range: Day5Range): Day5Map = {
    Day5Map(this.name, this.ranges :+ range)
  }
}

הפונקציה המעניינת כאן היא getDestinations, שלוקחת רשימה של טווחים ומחזירה רשימה חדשה של טווחים שהם בעצם התוצאה של הפעלת כללי המיפוי של אותה מפה. בשביל זה לוקחים כל טווח מרשימת המקורות, רצים על כללי המיפוי ומחפשים כלל שמתאים לו. אם מצאנו נשבור את הטווח לכמה חלקים, נמפה את החלק שמתאים לכלל המיפוי ואת החלקים שלא התאימו משאירים ברשימת המקורות לאיטרציה הבאה.

את פיענוח הקלט עשיתי בשלבים בגלל סיבוך מהחלק הראשון. המחלקה ששומרת את הקלט נראית כך:

case class Day5Part2Input(seeds: List[Interval], maps: List[Day5Map])

case class Day5Input(seeds: List[Long], maps: List[Day5Map]) {
  def toPart2Input: Day5Part2Input =
    Day5Part2Input(
      seeds = seeds.grouped(2).toList.map {
        case List(a, b) => a.until(a + b)
      },
      maps = maps
    )
}

והקוד שבונה אותה הוא:

  def parseInput(source: Source): Day5Input =
    val newMapPattern: Regex = """([-\w]+) map:""".r
    val seedsPattern: Regex = """seeds: ([\d\s]+)""".r
    val mapLine: Regex = """(\d+) (\d+) (\d+)""".r

    source
      .getLines()
      .foldLeft(Day5Input(List(), List()))((input, line) => {
        line match
          case seedsPattern(seeds) => Day5Input(seeds.split(' ').map(_.toLong).toList, List())
          case newMapPattern(mapName) => Day5Input(
            input.seeds,
            input.maps :+ Day5Map(mapName, List())
          )
          case mapLine(destinationStart, sourceStart, size) =>
            val range = Day5Range(sourceStart.toLong, destinationStart.toLong, size.toLong)
            Day5Input(
              input.seeds,
              input.maps.updated(input.maps.size - 1, input.maps.last.withAddedRange(range))
            )
          case _ => input
      })

הלולאה המרכזית בקוד הזה היא לולאת reduce שעוברת שורה שורה ומעדכנת את אוביקט הקלט שאנחנו בונים לפי התוכן של השורה. זאת תבנית שאני משתמש בה הרבה בעבודה על קלט טקסטואלי וסך הכל הקוד די מספר בצורה ברורה מה עושים עם כל סוג שורה.

הפונקציה האחרונה בתוכנית רצה על הקלט, מבצעת את כל המיפויים ומחפשת את התוצאה הקטנה ביותר והיא נראית כך:

  @main
  def day5_part2(): Unit = {
    val input = parseInput(Source.fromResource("day5.txt")).toPart2Input

    val destinations = input.maps.foldLeft(input.seeds)((sources, map) => map.getDestinations(sources))
    println(destinations.minBy(i => i.start).start)
  }

כמה לקחים על סקאלה ומחשבות כלליות על הפיתרון:

1. הכי הרבה זמן שרפתי על המימוש של פונקציית המיפוי Day5Map::getDestinations, בעיקר בגלל שניסיתי למצוא לולאה מובנית בסקאלה שתעזור לי במימוש הזה. אחרי שהתעייפתי מהחיפוש בניתי לבד את הפונקציה הרקורסיבית ומשם הכל רץ מהר.

2. אני עדיין לא בטוח שאני משתמש נכון ב Case Classes של סקאלה. מצד אחד הם מחזיקים data בצורה מאוד נוחה אבל מצד שני מהר מאוד זה מרגיש כמו פיתוח מונחה עצמים. אולי המפתח שצריך לזכור כאן הוא שדברים הם Immutable וכל פעם שרוצים לשנות משהו "של האוביקט" בתוך פונקציה מחזירים אוביקט חדש במקום.

3. מנגנון Pattern Matching של סקאלה עובד טוב כולל בצורה מקוננת. קוד כזה נראה ממש הגיוני לכתיבה וקריאה:

      sourceIntervals match
        case Nil => (sourceIntervals, destinationIntervals)
        case head :: tail =>
          this.ranges.find { r => ! r.getDestination(head).isEmpty } match
            case None => loop(tail, destinationIntervals :+ head)
            case Some(r) => loop(tail ++ r.getLeftover(head), destinationIntervals :+ r.getDestination(head))

מכירים סקאלה ויש לכם רעיונות איך לשפר את הקוד? אל תתביישו לספר לי בתגובות.