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

1. האתגר

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

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

2. אם התווית לא בקופסה יש להוסיף אותה בתור העדשה האחרונה של הקופסה.

3. אם לא עבר ערך יש להוציא את העדשה עם התווית מהקופסה.

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

קלט לדוגמה נראה כך:

rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7

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

After "rn=1":
Box 0: [rn 1]

After "cm-":
Box 0: [rn 1]

After "qp=3":
Box 0: [rn 1]
Box 1: [qp 3]

After "cm=2":
Box 0: [rn 1] [cm 2]
Box 1: [qp 3]

After "qp-":
Box 0: [rn 1] [cm 2]

After "pc=4":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4]

After "ot=9":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9]

After "ab=5":
Box 0: [rn 1] [cm 2]
Box 3: [pc 4] [ot 9] [ab 5]

After "pc-":
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5]

After "pc=6":
Box 0: [rn 1] [cm 2]
Box 3: [ot 9] [ab 5] [pc 6]

After "ot=7":
Box 0: [rn 1] [cm 2]
Box 3: [ot 7] [ab 5] [pc 6]

2. פיתרון כללי

מבנה הנתונים המרכזי שעזר לי לפתור את התרגיל הזה נקרא בסקאלה ListMap (הוא קיים גם בפייתון ושם נקרא OrderedDict. זה מבנה נתונים שהוא שילוב בין מילון לרשימה - מכניסים אליו דברים לפי מפתחות אבל הוא שומר על סדר ההכנסה שלהם. בסקאלה שימוש לדוגמה בו נראה כך:

scala> ListMap("foo" -> 10, "bar" -> 20, "buz" -> 30)
val res2: scala.collection.immutable.ListMap[String, Int] = ListMap(foo -> 10, bar -> 20, buz -> 30)

scala> ListMap("foo" -> 10, "bar" -> 20, "buz" -> 30).updated("bar", 40)
val res3: scala.collection.immutable.ListMap[String, Int] = ListMap(foo -> 10, bar -> 40, buz -> 30)

scala> ListMap("foo" -> 10, "bar" -> 20, "buz" -> 30).updated("foo", 30)
val res4: scala.collection.immutable.ListMap[String, Int] = ListMap(foo -> 30, bar -> 20, buz -> 30)

scala> ListMap("foo" -> 10, "bar" -> 20, "buz" -> 30).updated("hiz", 50)
val res5: scala.collection.immutable.ListMap[String, Int] = ListMap(foo -> 10, bar -> 20, buz -> 30, hiz -> 50)

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

וזה מצוין כי עכשיו אפשר לתרגם את משימת העדשות לפעולות על מילון-רשימה:

1. בכל קופסה נשים ListMap.

2. כל פקודה על עדשה (הכנסה, שינוי או הוצאה) תתורגם לפעולה על אותו ListMap.

3. בסוף יהיו לנו את כל המפתחות לפי סדר ההכנסה.

קוד? זה החלק הרלוונטי מתוך התוכנית:

      .foldLeft(Map[Int, ListMap[String, Int]]()) { (boxes, instruction) =>
        instruction.split("[-=]") match
          case Array(label, value) =>
            val boxNumber = runningHash(label)
            boxes.updatedWith(boxNumber) {
              case Some(lenses) => Some(lenses.updated(label, value.toInt))
              case None => Some(ListMap(label -> value.toInt))
            }

          case Array(label) =>
            val boxNumber = runningHash(label)
            boxes.updatedWith(boxNumber) {
              case Some(lenses) => Some(lenses.removed(label))
              case _ => None
            }
      }

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

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

import scala.io.Source
import scala.util.chaining._
import scala.collection.immutable.ListMap

object aoc2023day15 {
  val demoInput: String = "rn=1,cm-,qp=3,cm=2,qp-,pc=4,ot=9,ab=5,pc-,pc=6,ot=7"

  def runningHash(input: String): Int =
    val currentValue = 0
    input.map(_.toInt).foldLeft(currentValue) {(currentValue, asciiCode) =>
      ((currentValue + asciiCode) * 17) % 256
    }

  def focusingPower(boxNumber: Int, index: Int, value: Int): Long =
    (boxNumber + 1) * (index + 1) * value

  @main
  def day15part1(): Unit =
    Source
      .fromResource("day15.txt")
      .getLines()
      .next()
      .split(',')
      .map(runningHash)
      .sum
      .pipe(println)

  @main
  def day15part2(): Unit =
    Source
      .fromResource("day15.txt")
      .getLines()
      .next()
      .split(',')
      .foldLeft(Map[Int, ListMap[String, Int]]()) { (boxes, instruction) =>
        instruction.split("[-=]") match
          case Array(label, value) =>
            val boxNumber = runningHash(label)
            boxes.updatedWith(boxNumber) {
              case Some(lenses) => Some(lenses.updated(label, value.toInt))
              case None => Some(ListMap(label -> value.toInt))
            }

          case Array(label) =>
            val boxNumber = runningHash(label)
            boxes.updatedWith(boxNumber) {
              case Some(lenses) => Some(lenses.removed(label))
              case _ => None
            }
      }
      .map { (k, v) => (k, v.zipWithIndex.map {
        case ((label, value), index) => focusingPower(k, index, value)
      }) }
      .values
      .map(_.sum)
      .sum
      .pipe(println)
}