עוד שבוע מתחיל וסופי שבוע הם זמן מצוין לפתור עוד תרגיל של Advent Of Code. הפעם אנחנו ביום 14 ועדיין עם מטריצות.

1. התרגיל

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

    O....#....
    O.OO#....#
    .....##...
    OO.#O....O
    .O.....O#.
    O.#..O.#.#
    ..O..#O..O
    .......O..
    #....###..
    #OO..#....

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

    OOOO.#.O..
    OO..#....#
    OO..O##..O
    O..#.OO...
    ........#.
    ..#....#.#
    ..O..#.O.O
    ..O.......
    #....###..
    #....#....

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

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

OOOO.#.O.. 10
OO..#....#  9
OO..O##..O  8
O..#.OO...  7
........#.  6
..#....#.#  5
..O..#.O.O  4
..O.......  3
#....###..  2
#....#....  1

יש 5 כדורים בשורה של 10 אז זה נותן 50, עוד שני כדורים בשורה של 9 שמוסיפים 18, וככה ממשיכים ומחברים עד שמקבלים את הסכום 136.

המשימה היא לכתוב תוכנית שמקבלת את המטריצה ומחשבת את הסכום אחרי כל הטלטלה.

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

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

"OO.O.O..##".split('#').map(_.sorted.reverse).mkString("#")

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

import scala.annotation.tailrec
import scala.io.Source
import scala.util.chaining.*

object aoc2023day14 {
  val demoInput: String =
    """O....#....
      |O.OO#....#
      |.....##...
      |OO.#O....O
      |.O.....O#.
      |O.#..O.#.#
      |..O..#O..O
      |.......O..
      |#....###..
      |#OO..#....""".stripMargin

  def parseInput(input: Source): Map[(Int, Int), Char] =
      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

  def printMatrix(matrix: Map[(Int, Int), Char]): Unit =
    val maxRow = matrix.keys.maxBy(_._1)._1
    val maxColumn = matrix.keys.maxBy(_._2)._2
    0.to(maxRow).foreach { row =>
      0.to(maxColumn).foreach { col =>
        print(matrix((row, col)))
      }
      println()
    }

  def updateColumnAsString(matrix: Map[(Int, Int), Char],
                           columnNumber: Int,
                           updater: (String) => String): Map[(Int, Int), Char] =
    val column = matrix.collect {
      case ((row, col), ch) if col == columnNumber => (row, ch)
    }.toList.sortBy(_._1).map(_._2).mkString
    val updatedColumn = updater(column)
    updatedColumn.zipWithIndex.foldLeft(matrix) { case (matrix, (ch, idx)) =>
      matrix.updated((idx, columnNumber), ch)
    }

  def tiltUp(column: String): String =
    column
      .split('#')
      .map(_.sorted.reverse)
      .mkString("#")

  def totalLoad(matrix: Map[(Int, Int), Char]): Long =
    val maxRow = matrix.keys.maxBy(_._1)._1
    matrix.map {
      case ((row, col), 'O') => maxRow + 1 - row
      case ((row, col), _) => 0
    }.sum

  @main
  def day14part1(): Unit =
    val matrix = parseInput(Source.fromResource("day14.txt"))
    val maxColumn = matrix.keys.maxBy(_._2)._2

    0.to(maxColumn).foldLeft(matrix) {(matrix, c) =>
      updateColumnAsString(matrix, c, tiltUp)
    }.pipe(totalLoad)
    .pipe(println)
}

3. מחשבות על חלק 2

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

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

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

  def updateRowAsString(matrix: Map[(Int, Int), Char],
                        rowNumber: Int,
                        updater: String => String): Map[(Int, Int), Char] =
    val row = matrix.collect {
      case ((row, col), ch) if row == rowNumber => (col, ch)
    }.toList.sortBy(_._1).map(_._2).mkString
    val updated = updater(row)
    updated.zipWithIndex.foldLeft(matrix) { case (matrix, (ch, idx)) =>
      matrix.updated((rowNumber, idx), ch)
    }

  def tiltUp(column: String): String =
    column
      .split('#')
      .map(_.sorted.reverse)
      .mkString("#")

  def tiltDown(column: String): String =
    column
      .split('#')
      .map(_.sorted)
      .mkString("#")

  def tiltLeft(row: String): String =
    row
      .split('#')
      .map(_.sorted.reverse)
      .mkString("#")

  def tiltRight(row: String): String =
    row
      .split('#')
      .map(_.sorted)
      .mkString("#")

  def spinCycle(matrix: Map[(Int, Int), Char]): Map[(Int, Int), Char] =
    val maxColumn = matrix.keys.maxBy(_._2)._2
    val maxRow = matrix.keys.maxBy(_._1)._1

    val s1 = 0.to(maxColumn).foldLeft(matrix) { (matrix, c) => updateColumnAsString(matrix, c, tiltUp) }
    val s2 = 0.to(maxRow).foldLeft(s1) { (matrix, c) => updateRowAsString(matrix, c, tiltLeft) }
    val s3 = 0.to(maxColumn).foldLeft(s2) { (matrix, c) => updateColumnAsString(matrix, c, tiltDown) }
    val s4 = 0.to(maxRow).foldLeft(s3) { (matrix, c) => updateRowAsString(matrix, c, tiltRight) }
    s4

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

  @tailrec
  def findCycle(matrix: Map[(Int, Int), Char],
                iterate: (Map[(Int, Int), Char] => Map[(Int, Int), Char]),
                seen: List[Map[(Int, Int), Char]] = List()): List[Map[(Int, Int), Char]] =
    if (seen.contains(matrix)) {
      seen :+ matrix
    } else {
      findCycle(iterate(matrix), iterate, seen :+ matrix)
    }

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

  @main
  def day14part2(): Unit =
    val matrix = parseInput(Source.fromResource("day14.txt"))
    val maxColumn = matrix.keys.maxBy(_._2)._2
    val maxRow = matrix.keys.maxBy(_._1)._1
    val cycle :+ dup = findCycle(matrix, spinCycle)
    val prefix = cycle.indexOf(dup)
    val actualCycle = cycle.drop(prefix)
    LazyList.iterate(matrix)(spinCycle).take(prefix + ((1000000000 - prefix) % actualCycle.size) + 1)
      .last
      .pipe(totalLoad)
      .pipe(println)

יש לכם רעיונות אחרים? פיתרונות מעניינים בשפות אחרות? מוזמנים תמיד לשתף בתגובות או בטלגרם.