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

1. האתגר

הסיפור בגדול הוא פיענוח של קלט שמגיע בצורת מטריצה. הקלט לדוגמה הוא:

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

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

2. פיענוח הקלט בסקאלה

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

  sealed trait Sigil
  case class NumberSigil(line: Int, start: Int, end: Int, value: Int) extends Sigil
  case class NullSigil(value: Int = 0) extends Sigil
  case class SignSigil(line: Int, column: Int, value: String) extends Sigil {
    def neighbors(): Seq[(Int, Int)] =
      for 
        ii <- Range(line-1, line+2)
        jj <- Range(column-1, column+2)
      yield (ii, jj)
  }

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

הפונקציה הבאה מקבלת מטריצה מהסוג שתיארתי ואוביקט של סימן או מספר ומוסיפה אותו למטריצה:

  def addSigilsToDB(sigils: List[Sigil])(db: Map[(Int, Int), Sigil]): Map[(Int, Int), Sigil] =
    sigils.foldLeft(db)((acc, value) =>
      value match
        case n: NumberSigil =>
          Range(n.start, n.end).foldLeft(acc)((acc, col) =>
            acc.updated((n.line, col), n))
        case s: SignSigil => acc.updated((s.line, s.column), s)
    )

כתבתי את הפונקציה בתור חישוב מושהה (Curry) כלומר היא מקבלת קודם את הסימן ואז מחזירה פונקציה שמקבלת את המטריצה ומחזירה מטריצה חדשה עם תוספת הסימן. הסיבה היא הפונקציה האחרונה parse שמקבלת את הקלט ובונה ממנו את המטריצה. זה הקוד שלה:

  def parse(input: Source): Map[(Int, Int), Sigil] =
    input.getLines().zipWithIndex.foldLeft(Map(): Map[(Int, Int), Sigil])((acc, value) =>
      val (line, lineIndex) = value
      val numberSigils =
        """(\d+)""".r.findAllMatchIn(line).map(m =>
            NumberSigil(line = lineIndex, start = m.start, end = m.end, value = m.toString.toInt))
          .toList
      val signSigils =
        """([^\d.])""".r.findAllMatchIn(line).map(m =>
            SignSigil(line = lineIndex, column = m.start, value = m.toString()))
          .toList
      acc
        .pipe(addSigilsToDB(numberSigils))
        .pipe(addSigilsToDB(signSigils))
      )

המבנה של פונקציה שמחזירה פונקציה הוא שאפשר להפעיל את pipe כדי לקבל תחביר קצת יותר קריא לשירשור פונקציות.

3. שימוש במידע המפוענח לפיתרון החלק הראשון

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

    db
      .values
      .collect { case s: SignSigil => s }
      .flatMap(s => s.neighbors())
      .map(pos => db.getOrElse(pos, NullSigil()))
      .toSet
      .toList
      .collect { case s: NumberSigil => s.value }
      .sum
      .pipe(println)

בתרגום לעברית - קח את כל הערכים של המטריצה (המספרים והסימנים), סנן מהם רק את הסימנים, קח את כל רשימת השכנים של כל הסימנים לתוך רשימה אחת ארוכה ואז תהפוך כל קואורדינטות של שכן לסימן שנמצא שם מתוך db. אם אין ערך במטריצה לקואורדינטה הזו נשתמש בערך הריק. אחרי זה תשמור את כל הסימנים שמצאת לתוך Set, מה שימחק את הכפילויות, ואז תהפוך חזרה לרשימה כדי שנוכל לקחת את הערכים המספריים שלהם, לסכום את כולם ולהדפיס.

4. שימוש במידע המפוענח לפיתרון החלק השני

את החלק השני אפשר למצוא מאותה מטריצה באופן הבא:

    db
      .values
      .collect { case n: SignSigil if n.value == "*" => n }
      .map(s => s.neighbors())
      .map(s => s.map(p => db.getOrElse(p, NullSigil)))
      .map(s => s.toSet)
      .map(s => s.collect { case n: NumberSigil => n })
      .filter(s => s.size == 2)
      .map(g => g.foldLeft(1)(_ * _.value))
      .sum
      .pipe(println)

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