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

1. חיפוש מעגל בגרף

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

.....
.F-7.
.|.|.
.L-J.
.....

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

1. קו אנכי מחבר את המשבצות שמעליו ומתחתיו
2. קו אופקי מחבר את המשבצות משני צדדיו
3. האות L מחברת את המשבצת שמעליה עם זאת שמימינה
4. האות J מחברת את המשבצת שמעליה לזו שמשמאלה
5. האות F מחברת את המשבצת שמתחתיה עם זאת שמימינה
6. האות L מחברת את המשבצת שמעליה לזו שמימינה

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

.....
.S-7.
.|.|.
.L-J.
.....

המשימה שלנו היא למצוא את המעגל ולהדפיס את המרחק של הנקודה הרחוקה ביותר שבתוכו מנקודת ההתחלה. בקלט הדוגמה התשובה היא 4 והנקודה הכי רחוקה היא איפה שמופיעה האות J (תספרו ותראו).

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

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

  def connections(ch: Char, row: Int, column: Int): List[(Int, Int)] =
    ch match
      case '.' => List()
      case '|' => List((row - 1, column), ((row + 1), column))
      case '-' => List((row, column - 1), (row, column + 1))
      case 'L' => List((row - 1, column), (row, column + 1))
      case 'J' => List((row - 1, column), (row, column - 1))
      case '7' => List((row + 1, column), (row, column - 1))
      case 'F' => List((row + 1, column), (row, column + 1))
      case 'S' => List((-1, -1)) // marker

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

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

  def parseInput(input: Source): Map[(Int, Int), List[(Int, Int)]] =
    input
      .getLines()
      .zipWithIndex
      .collect {
        case (line: String, index: Int) => line.toList.zipWithIndex.map((ch, column) => (index, column, ch))
      }
      .flatten
      .flatMap { case (row, column, ch) => Map((row, column) -> connections(ch, row, column))}
      .toMap

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

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

  @tailrec
  def findCycleSizeDFS(map: Map[(Int, Int), List[(Int, Int)]],
                       workQueue: List[(Int, Int)],
                       seen: Set[(Int, Int)] = Set()): Int =

    workQueue match
      case start :: tail if seen.contains(start) =>
        // Loop
        seen.size

      case start :: tail =>
        val neighbors = map.getOrElse(start, List()).filterNot { p => seen.contains(p) }
        findCycleSizeDFS(map, neighbors ++ workQueue, seen + start)

      case Nil =>
        // Dead End
        0

האנוטציה tailrec מבטיחה לי שהפונקציה לא תשתמש בטעות במחסנית הרקורסיה ותמיד תאפשר אופטימיזציה על ידי מחיקת זנב הרקורסיה (רקורסיית זנב).

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

  @main
  def day10part1(): Unit =
    val pipes = List('|', '-', 'L', 'J', '7', 'F')
    pipes.map { startChar =>
      val map = parseInput(Source.fromResource("day10.txt"))
      val start = map
        .find { case (_, c: List[(Int, Int)]) => c == List((-1, -1)) }
        .map { case (s: (Int, Int), _) => s }
        .get

      findCycleSizeDFS(
        map.updated(start, connections(startChar, start(0), start(1))),
        List(start))
    }.max
     .pipe(_ / 2)
     .pipe(println)

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

https://adventofcode.com/2023/day/10