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

1. האתגר

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

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

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

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

    123456789
        ><   
    #.##..##.
    ..#.##.#.
    ##......#
    ##......#
    ..#.##.#.
    ..##..##.
    #.#.##.#.
        ><   
    123456789

אפשר לראות איך מה שמשמאל לעמודה הוא תמונת ראי של מה שמימין לה, חוץ מהנקודות שנמצאות "רחוק מדי" למשל העמודה הראשונה שהיא לא בתמונה. בתמונה השניה המראה היא אופקית בין השורה הרביעית לחמישית:

1 #...##..# 1
2 #....#..# 2
3 ..##..### 3
4v#####.##.v4
5^#####.##.^5
6 ..##..### 6
7 #....#..# 7

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

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

2. פיתרון לחלק הראשון

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

  def findMirrorInList(items: List[String], except: Set[Int] = Set()): Int =
    1.until(items.length).map { i =>
      if (i <= items.length / 2) {
        items.slice(0, i) == items.slice(i, i * 2).reverse
      } else {
        val distanceFromEnd = items.length - i
        items.slice(i - distanceFromEnd, i) == items.slice(i, items.length).reverse
      }
    }.zipWithIndex
      .indexWhere { case (item, index) => item && !except.contains(index + 1) } + 1

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

class ChunkedIterator[T](iterator: Iterator[T])(p: (T => Boolean)) extends Iterator[List[T]] {
  override def hasNext: Boolean = iterator.hasNext

  override def next(): List[T] = {
    if (!hasNext) throw new NoSuchElementException("next on empty iterator")
    iterator.takeWhile(p).toList
  }
}

extension (i: Iterator[String]) {
  def toParagraphs: ChunkedIterator[String] = {
    ChunkedIterator[String](i) { f => f.nonEmpty }
  }
}

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

  def toMatrix(block: List[String]): Map[(Long, Long), Char] =
    block
      .zipWithIndex
      .collect {
          case (line: String, index: Int) => line.toList.zipWithIndex.map((ch, column) => (index, column, ch))
      }
      .flatten
      .flatMap {
        case (row, column, ch) => Map((row.toLong, column.toLong) -> ch)
      }
      .toMap

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

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

  def toLines(matrix: Map[(Long, Long), Char]): List[String] =
    val lastRow = matrix
      .keys
      .collect { (row, column) => row }
      .max
      .toInt

    0.to(lastRow)
      .map { row =>
        matrix
          .keys
          .filter { case (r, _) => row == r }
          .toList
          .sortBy(_._2)
          .map(matrix)
          .mkString
      }.toList


  def toColumns(matrix: Map[(Long, Long), Char]): List[String] =
    val lastColumn = matrix
      .keys
      .collect { (row, column) => column }
      .max
      .toInt

    0.to(lastColumn)
      .map { col =>
        matrix
          .keys
          .filter { case (_, c) => col == c }
          .toList
          .sortBy(_._1)
          .map(matrix)
          .mkString
      }.toList

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

  @main
  def day13part1(): Unit =
    Source
      .fromResource("day13.txt")
      .getLines()
      .toParagraphs
      .map(toMatrix)
      .toList
      .map { m => (toLines(m), toColumns(m)) }
      .collect { case (rows, column) =>
        findMirrorInList(rows) * 100 + findMirrorInList(column)
      }
      .sum
      .pipe(println)

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

3. פיתרון חלק 2

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

  def swap(ch: Char): Char =
    if (ch == '.') { '#' } else { '.' }

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

בקיצור זה הקוד של החלק השני:

  @main
  def day13part2(): Unit =
    Source
      .fromResource("day13.txt")
      .getLines()
      .toParagraphs
      .map(toMatrix)
      .toList
      .map { m => (m, toLines(m), toColumns(m)) }
      .collect { case (m, rows, columns) =>
        val horizontalMirror = findMirrorInList(rows)
        val verticalMirror = findMirrorInList(columns)

        m
          .keys
          .map { k => m.updatedWith(k) { case Some(ch) => Some(swap(ch)) } }
          .map { m => (findMirrorInList(toLines(m), Set(horizontalMirror)), findMirrorInList(toColumns(m), Set(verticalMirror))) }
          .find { i => i != (0, 0) }
          .map {
            case (0, altVertical) => altVertical
            case (altHorizontal, 0) => altHorizontal * 100
          }
      }
      .map(_.getOrElse(0))
      .sum
      .pipe(println)

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

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