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

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

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

...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........

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

...........
.....###.#.
.###.##..#.
..#.#O..#..
....#.#....
.##O.O####.
.##.O#...#.
.......##..
.##.#.####.
.##..##.##.
...........

אם לוקחים צעד נוסף יהיו אפילו יותר אפשרויות:

...........
.....###.#.
.###.##..#.
..#.#.O.#..
...O#O#....
.##.OS####.
.##O.#...#.
....O..##..
.##.#.####.
.##..##.##.
...........

ואחרי 6 צעדים החייל שלנו יוכל להגיע לכל אחת ממשבצות העיגול בציור:

...........
.....###.#.
.###.##.O#.
.O#O#O.O#..
O.O.#.#.O..
.##O.O####.
.##.O#O..#.
.O.O.O.##..
.##.#.####.
.##O.##.##.
...........

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

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

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

1. מספר המשבצות שצריך 64 צעדים בשביל להגיע אליהן.

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

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

  def parseInput(input: Source): Map[(Int, Int), Double] =
    input
      .getLines()
      .zipWithIndex
      .flatMap { (line, lineNumber) =>
        line.zipWithIndex.foldLeft(Map[(Int, Int), Char]()) { (acc, item) =>
          val (char, column) = item
          acc.updated((lineNumber, column), char)
        }
      }.foldLeft(Map[(Int, Int), Double]()) { (acc, item) =>
        val (key, value) = item
        acc.updated(key, value match
          case '.' => Double.PositiveInfinity
          case '#' => Double.NegativeInfinity
          case 'S' => 0)
      }

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

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

  def bfs(map: Map[(Int, Int), Double]): Map[(Int, Int), Double] =
    var open: mutable.Queue[(Int, Int)] = mutable.Queue(map.filter(_._2 == 0).head._1)
    var mmap = mutable.Map.from(map)

    while(open.nonEmpty) {
      val start = open.dequeue()
      val steps = mmap(start)

      List[(Int, Int)]((start._1 - 1, start._2),
        (start._1 + 1, start._2),
        (start._1, start._2 - 1),
        (start._1, start._2 + 1)
      ).foreach { neighbor =>
        val currentValue = mmap.getOrElse(neighbor, Double.NegativeInfinity)
        val newValue = steps + 1
        if (!newValue.isInfinity && (newValue < currentValue)) {
          mmap.update(neighbor, newValue)
          open.enqueue(neighbor)
        }
      }
    }

    Map.from(mmap)

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

  @main
  def day21part1(): Unit =
    val map = parseInput(Source.fromResource("day21.txt"))
    val full = bfs(map)
    println(full.count { e => e._2 % 2 == 0 && e._2 <= 64 })

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

.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##..S####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................

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