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

1. האתגר - מבוך המראות

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

.|...\....
|.-.\.....
.....|-...
........|.
..........
.........\
..../.\\..
.-.-/..|..
.|....-|.\
..//.|....

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

1. אם היא פוגשת מראה אלכסונית היא תשנה את הכיוון לפי האלכסון (לדוגמה קרן שהולכת ימינה ופוגשת במראה / תשנה את הכיוון למעלה).

2. אם היא פוגשת מראה ישרה בצד בצד המחודד שלה לא קורה כלום.

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

האתגר שלנו הוא למצוא בכמה משבצות הקרן עברה.

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

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

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

@tailrec
def travel(beams: List[Beam],
           matrix: Map[(Int, Int), Char],
           visited: Set[Beam] = Set()): Set[Beam] =
  val activeBeams = beams.filter { b =>
    matrix.contains(b.row, b.column) && !visited.contains(b)
  }
  if (activeBeams.nonEmpty) {
    val nextRound = activeBeams.flatMap { b => step(b, matrix(b.row, b.column)) }
    travel(nextRound, matrix, visited ++ activeBeams.toSet)
  } else {
    visited
  }

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

  def step(beam: Beam, ch: Char): List[Beam] =
    ch match
      case '.' => List(beam.continue())
      case '|' if vertical(beam.direction) => List(beam.continue())
      case '|' if horizontal(beam.direction) => List(beam.up(), beam.down())

      case '-' if horizontal(beam.direction) => List(beam.continue())
      case '-' if vertical(beam.direction) => List(beam.left(), beam.right())

      case '/' if beam.direction == Direction.Right => List(beam.up())
      case '/' if beam.direction == Direction.Left => List(beam.down())
      case '/' if beam.direction == Direction.Up => List(beam.right())
      case '/' if beam.direction == Direction.Down => List(beam.left())

      case '\\' if beam.direction == Direction.Right => List(beam.down())
      case '\\' if beam.direction == Direction.Left => List(beam.up())
      case '\\' if beam.direction == Direction.Up => List(beam.left())
      case '\\' if beam.direction == Direction.Down => List(beam.right())

אחרי שכל קרן התקדמה צעד אחד תהיה לנו רשימה של קרניים חדשות, אותן נשלח שוב ל travel וכך הלאה עד שלא יהיו יותר קרניים ברשימה.

סך הכל הפיתרון בסקאלה לחלק הראשון הוא:

import aoc2023day16.Direction
import aoc2023day16.Direction.{Down, Up}

import scala.annotation.tailrec
import scala.io.Source

object aoc2023day16 {
  enum Direction {
    case Up, Down, Left, Right
  }

  def vertical(dir: Direction): Boolean = dir == Direction.Up || dir == Direction.Down
  def horizontal(dir: Direction): Boolean = dir == Direction.Left || dir == Direction.Right

  case class Beam(row: Int, column: Int, direction: Direction) {
    def continue(): Beam = {
      this.direction match
        case Direction.Right => right()
        case Direction.Left => left()
        case Direction.Up => up()
        case Direction.Down => down()
    }

    def up(): Beam = Beam(this.row - 1, this.column, Direction.Up)
    def down(): Beam = Beam(this.row + 1, this.column, Direction.Down)
    def left(): Beam = Beam(this.row, this.column - 1, Direction.Left)
    def right(): Beam = Beam(this.row, this.column + 1, Direction.Right)
  }

  val demoInput: String =
    """.|...\....
      ||.-.\.....
      |.....|-...
      |........|.
      |..........
      |.........\
      |..../.\\..
      |.-.-/..|..
      |.|....-|.\
      |..//.|....
      |""".stripMargin

  def step(beam: Beam, ch: Char): List[Beam] =
    ch match
      case '.' => List(beam.continue())
      case '|' if vertical(beam.direction) => List(beam.continue())
      case '|' if horizontal(beam.direction) => List(beam.up(), beam.down())

      case '-' if horizontal(beam.direction) => List(beam.continue())
      case '-' if vertical(beam.direction) => List(beam.left(), beam.right())

      case '/' if beam.direction == Direction.Right => List(beam.up())
      case '/' if beam.direction == Direction.Left => List(beam.down())
      case '/' if beam.direction == Direction.Up => List(beam.right())
      case '/' if beam.direction == Direction.Down => List(beam.left())

      case '\\' if beam.direction == Direction.Right => List(beam.down())
      case '\\' if beam.direction == Direction.Left => List(beam.up())
      case '\\' if beam.direction == Direction.Up => List(beam.left())
      case '\\' if beam.direction == Direction.Down => List(beam.right())




  @tailrec
  def travel(beams: List[Beam],
             matrix: Map[(Int, Int), Char],
             visited: Set[Beam] = Set()): Set[Beam] =
    val activeBeams = beams.filter { b =>
      matrix.contains(b.row, b.column) && !visited.contains(b)
    }
    if (activeBeams.nonEmpty) {
      val nextRound = activeBeams.flatMap { b => step(b, matrix(b.row, b.column)) }
      travel(nextRound, matrix, visited ++ activeBeams.toSet)
    } else {
      visited
    }

  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 countVisited(start: Beam, matrix: Map[(Int, Int), Char]) =
    val visited = travel(List(start), matrix)
    visited.map(b => (b.row, b.column)).size

  @main
  def day16part1(): Unit =
    val matrix = parseInput(Source.fromResource("day16.txt"))
    println(countVisited(Beam(0, 0, Direction.Right), matrix))
}

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

  def border(matrix: Map[(Int, Int), Char]): List[Beam] =
    val numRows = matrix.keys.maxBy(_._1)._1
    val numColumns = matrix.keys.maxBy(_._2)._2
    matrix.keys.filter { (row, col) =>
      row == 0 || row == numRows || col == 0 || col == numColumns
    }.flatMap { (row, col) =>
      if (row == 0 && col == 0) {
        // top left
        List(Beam(0, 0, Direction.Down), Beam(0, 0, Direction.Right))
      } else if (row == 0 && col == numColumns) {
        // top right
        List(Beam(row, col, Direction.Down), Beam(row, col, Direction.Left))
      } else if (row == numRows && col == 0) {
        // bottom left
        List(Beam(row, col, Direction.Up), Beam(row, col, Direction.Right))
      } else if (row == numRows && col == numColumns) {
        // bottom right
        List(Beam(row, col, Direction.Up), Beam(row, col, Direction.Left))
      } else if (row == 0) {
        // top row
        List(Beam(row, col, Direction.Down))
      } else if (col == 0) {
        // left
        List(Beam(row, col, Direction.Right))
      } else if (row == numRows) {
        // bottom
        List(Beam(row, col, Direction.Up))
      } else if (col == numColumns) {
        // right
        List(Beam(row, col, Direction.Left))
      } else {
        List()
      }
    }.toList

  @main
  def day16part2(): Unit =
    val matrix = parseInput(Source.fromResource("day16.txt"))
    val bestBeam = border(matrix).maxBy { b => countVisited(b, matrix) }
    println(countVisited(bestBeam, matrix))

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