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

1. האתגר - הצלבת נתונים

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

#.#.### 1,1,3

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

.#.###.#.###### 1,3,1,6

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

???.### 1,1,3

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

?###???????? 3,2,1

כל ההשלמות האלה חוקיות:

.###.##.#...
.###.##..#..
.###.##...#.
.###.##....#
.###..##.#..
.###..##..#.
.###..##...#
.###...##.#.
.###...##..#
.###....##.#

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

2. איך לא לפתור את התרגיל

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

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

3. מה כן עובד

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

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

קוד? הנה בסקאלה-

import scala.io.Source
import scala.util.chaining._
import scala.collection.mutable
object aoc2023day12 {
  val demoInput: String = """???.### 1,1,3
                            |.??..??...?##. 1,1,3
                            |?#?#?#?#?#?#?#? 1,3,1,6
                            |????.#...#... 4,1,1
                            |????.######..#####. 1,6,5
                            |?###???????? 3,2,1""".stripMargin


  def unfoldLine(factor: Int)(line: String): (String, List[Int]) =
    line.split(' ') match
      case Array(springs, counts) =>
        val unfoldedCounts = ((counts + ",") * factor).stripSuffix(",")
        val unfoldedSprings = ((springs + "?") * factor).stripSuffix("?")
        (unfoldedSprings, unfoldedCounts.split(',').map(_.toInt).toList)


  def assignGroup(springs: String, groupSize: Int): Option[String] =
    val startRe = s"""^[#?]{${groupSize}}[.?].*""".r
    val finalRe = s"""^[#?]{${groupSize}}""".r

    if (startRe.matches(springs)) {
      Some(springs.substring(groupSize + 1))
    } else if (finalRe.matches(springs)) {
      Some("")
    } else {
      None
    }


  def arrangements(mem: mutable.HashMap[String, Long] = new mutable.HashMap[String, Long]())(springs: String, counts: List[Int]): Long =
    counts match
      case Nil if springs.forall(Set('.', '?').contains(_)) =>
        1
      case Nil =>
        0
      case head :: tail =>
        mem.getOrElseUpdate(s"${springs} ${counts}", {
          val firstDamaged = springs.indexOf('#')
          val end = if (firstDamaged != -1) firstDamaged else springs.length - 1
          0.to(end)
            .map { i => assignGroup(springs.substring(i), head) }
            .collect {
              case Some(springs) => arrangements(mem)(springs, tail)
            }
            .sum
        })



  @main
  def day12part1(): Unit =
    Source.fromResource("day12.txt")
      .getLines()
      .map(unfoldLine(1))
      .map(arrangements())
      .toList
      .sum
      .pipe(println)
}

4. חלק 2

חדי העין ביניכם יכלו לשים לב לפונקציה בשם unfoldLine שהפעלתי על כל שורה כדי לפצל את המחרוזת לשני החלקים שלה:

  def unfoldLine(factor: Int)(line: String): (String, List[Int]) =
    line.split(' ') match
      case Array(springs, counts) =>
        val unfoldedCounts = ((counts + ",") * factor).stripSuffix(",")
        val unfoldedSprings = ((springs + "?") * factor).stripSuffix("?")
        (unfoldedSprings, unfoldedCounts.split(',').map(_.toInt).toList)

אבל חוץ מהשורה הפונקציה מקבלת גם ערך בשם factor. הסיבה לערך הזה היא החלק השני של התרגיל.

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

.# 1

הם בעצם מתכוונים שהקלט שלנו הוא:

.#?.#?.#?.#?.# 1,1,1,1,1

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