פיתרון Advent Of Code יום 18 בסקאלה

30/05/2024

יומי

מזמן לא כתבנו Advent Of Code וזו הזדמנות מצוינת להיזכר ולהתקדם. יש לנו 25 חידות סך הכל אז אנחנו ממש מתקרבים לסיום. בואו נראה את יום 18, את הניסיון הראשון הארוך והלא מוצלח שלי ואז את הפיתרון האמיתי.

1. מה צריך לחשב

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

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

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

R 6 (#70c710)
D 5 (#0dc571)
L 2 (#5713f0)
D 2 (#d2c081)
R 2 (#59c680)
D 2 (#411b91)
L 5 (#8ceee2)
U 2 (#caa173)
L 1 (#1b58a2)
U 2 (#caa171)
R 2 (#7807d2)
U 3 (#a77fa3)
L 2 (#015232)
U 2 (#7a21e3)

האותיות R, D, L ו U קובעות לאיזה כיוון לחפור (שמאלה, למטה, ימינה או למעלה) והמספר קובע כמה מטר. נתעלם בינתיים מהמספר האחרון בשורה.

אחרי שחפרנו את הבריכה ממלאים אותה במים וזה נראה ככה:

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

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

2. איך לא לספור סולמיות

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

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

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

case class PaintingInstruction(dir: String, count: Long, color: String)

  def dig(input: Source): Canvas =
    val lineRE = """(\w) (\d+) \((#\w+)\)""".r

    input
      .getLines()
      .foldLeft(((0, 0), Map[(Int, Int), PaintingInstruction]())) { (acc, line) =>
        Try {
          val (pos, canvas) = acc
          val List(d, count, color) = lineRE.findFirstMatchIn(line).get.subgroups
          val paintingInstruction = PaintingInstruction(d, count.toInt, color)
          paint(pos, canvas, paintingInstruction)
        }.recover { err =>
          // skip line in case of error
          println(s"Error in line ${line} - ${err}")
          acc
        }.get
      }._2

  def paint(pos: Point, canvas: Canvas, cmd: PaintingInstruction): (Point, Canvas) =
    0L.until(cmd.count).foldLeft((pos, canvas)) { (acc, count) =>
      val ((row, column), canvas) = acc

      val nextCanvas = canvas.updated((row, column), cmd)
      cmd.dir match
        case "R" => ((row, column + 1), nextCanvas)
        case "L" => ((row, column - 1), nextCanvas)
        case "U" => ((row - 1, column), nextCanvas)
        case "D" => ((row + 1, column), nextCanvas)
    }

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

@tailrec
def floodFill(canvas: Canvas, finished: Set[Point], inProgress: List[Point]): Set[Point] =
  inProgress match
    case head :: tail =>
      val (row, column) = head
      println(head)
      val neighbors = List(
        (row-1, column),
        (row+1, column),
        (row, column-1),
        (row, column+1),
      ).filterNot { p => canvas.contains(p) }
      .filterNot(finished.contains)
      .filterNot(inProgress.contains)

      floodFill(canvas, finished + head, tail ++ neighbors)

    case Nil => finished

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

3. ניסיון שני

בחלק השני של התרגיל מספרים לנו שבעצם קראנו את השורה לא נכון כל הזמן. המספר האחרון הוא הדבר החשוב - חמש הספרות הראשונות שלו הן מספר בבסיס 16, והסיפרה האחרונה מייצגת את הכיוון 0 עבור ימינה, 1 עבור למטה 2 עבור שמאלה ו 3 אומר למעלה. המספרים גדולים ולכן כבר לא ריאלי לשמור את כל המשבצות במטריצה. אם היינו שומרים ומחשבים קלט הדוגמה היה מסתכם ב 952408144115 משבצות.

פה כמעט התייאשתי עד שמצאתי את הפוסט הזה: https://aymarino.github.io/polygon-area/

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

def coordinates(input: Source, parseLine: (line: String) => PaintingInstruction): List[(Long, Long, Long)] =
    input
      .getLines()
      .scanLeft((0L, 0L, 0L)) { (acc, line) =>
        val (row, column, distance) = acc
        val paintingInstruction = parseLine(line)

        paintingInstruction.dir match
          case "L" => (row, column - paintingInstruction.count, distance + paintingInstruction.count)
          case "R" => (row, column + paintingInstruction.count, distance + paintingInstruction.count)
          case "U" => (row - paintingInstruction.count, column, distance + paintingInstruction.count)
          case "D" => (row + paintingInstruction.count, column, distance + paintingInstruction.count)
      }.toList

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

  def parsePart1(line: String): PaintingInstruction =
    val lineRE = """(\w) (\d+) \((#\w+)\)""".r
    val List(d, count, color) = lineRE.findFirstMatchIn(line).get.subgroups
    PaintingInstruction(d, count.toInt, color)

  def parsePart2(line: String): PaintingInstruction =
    val lineRE = """\w \d+ \(#(\w\w\w\w\w)(\w)\)""".r
    val List(count, d) = lineRE.findFirstMatchIn(line).get.subgroups
    val distance = java.lang.Long.parseLong(count, 16)
    val direction = d match
      case "0" => "R"
      case "1" => "D"
      case "2" => "L"
      case "3" => "U"

    PaintingInstruction(direction, distance, "...")

ואז את הנוסחה לשטח פוליגון:

  def shoelace(coordinates: List[(Long, Long, Long)]): Long =
    coordinates.zip(coordinates.tail).map { pair =>
      val ((x1, y1, d1), (x2, y2, d2)) = pair
      x1 * y2 - y1 * x2
    }
    .sum
    .abs / 2

זה הקוד לחלק הראשון:

  def day18part1(): Unit =
    val coords = coordinates(Source.fromResource("day18.txt"), parsePart1)
    val distance = coords.last._3
    val area = shoelace(coords)
    val poolSize = area + distance / 2 + 1

    println(poolSize)

וזה החלק השני:

  def day18part1(): Unit =
    val coords = coordinates(Source.fromResource("day18.txt"), parsePart2)
    val distance = coords.last._3
    val area = shoelace(coords)
    val poolSize = area + distance / 2 + 1

    println(poolSize)

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