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

1. האתגר - החלל המתרחב

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

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

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

   v  v  v
 ...#......
 .......#..
 #.........
>..........<
 ......#...
 .#........
 .........#
>..........<
 .......#..
 #...#.....
   ^  ^  ^

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

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

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

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

  def distance(p1: (Int, Int), p2: (Int, Int)): Int =
      Math.max(p1._1, p2._1) - Math.min(p1._1, p2._1) +
      Math.max(p1._2, p2._2) - Math.min(p1._2, p2._2)

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

  implicit class Crossable[X](xs: Iterable[X]) {
    def cross[Y](ys: Iterable[Y]): Iterable[(X, Y)] = for {x <- xs; y <- ys} yield (x, y)
  }

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

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

  def parseInput(input: Source, expansion: Int = 1): Map[(Int, Int), Char] =
    val beforeExpansion = 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) -> ch)
      }
      .toMap

    val emptyColumnsCounts = beforeExpansion
      .keys
      .map {(i, j) => j}
      .toList
      .sorted
      .scan(0) { (acc, columnNumber) =>
        if (isEmptyColumn(beforeExpansion, columnNumber)) acc + expansion else acc
      }

    val emptyRowCounts = beforeExpansion
      .keys
      .map { (i, j) => i }
      .toList
      .sorted
      .scan(0) { (acc, rowNumber) =>
        if (isEmptyRow(beforeExpansion, rowNumber)) acc + expansion else acc
      }

    val afterExpansion = beforeExpansion.map {
      case ((row, column), ch) =>
        ((row + emptyRowCounts(row), column + emptyColumnsCounts(column)), ch)
    }

    afterExpansion

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

    val afterExpansion = beforeExpansion.map {
      case ((row, column), ch) =>
        ((row + emptyRowCounts(row), column + emptyColumnsCounts(column)), ch)
    }

והחלק האחרון הוא חישוב סכום המרחקים:

  @main
  def day11part1(): Unit =
    val map = parseInput(Source.fromResource("day11.txt"))
    val galaxies = map
      .filter { case ((i, j), ch) => ch != '.' }
      .keys
      .toList

    (galaxies cross galaxies)
      .map(distance)
      .sum
      .pipe(_ / 2)
      .pipe(println)

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

רעיונות לשיפור? פיתרונות יעילים יותר? פיתרונות בשפות אחרות? אל תתביישו ושתפו בתגובות או בטלגרם.