Advent of Code 20.scala

import java.io.FileInputStream
import scala.io.StdIn

case class Image(id: BigInt = 0, orientation: String = "", lines: Vector[String] = Vector()) {
  def turnRight: Image = {
    val chars: Vector[Vector[Char]] = lines.map(_.toVector)
    val newLines = (0 until chars.size).map { y =>
      (0 until chars.size).map { x =>
        chars(chars.size - x - 1)(y)
      }.mkString
    }.toVector
    copy(orientation = orientation + "R", lines = newLines)
  }

  def mirrored: Image = {
    copy(orientation = orientation + "M", lines = lines.map(_.reverse))
  }

  def asString(): String = {
    lines.mkString("\n")
  }

  def left: String = {
    lines.map(_.head).mkString
  }

  def top: String = {
    lines.head
  }

  def right: String = {
    lines.map(_.last).mkString
  }

  def bottom: String = {
    lines.last
  }

  def removeBorders(): Image = {
    val linesWithoutBorders: Vector[String] = lines.init.tail.map(_.init.tail)
    copy(lines = linesWithoutBorders)
  }

  def mergeHorizontally(another: Image): Image = {
    val newLines: Vector[String] = (lines zip another.lines).map(_ + _)
    copy(lines = newLines)
  }

  def mergeVertically(another: Image): Image = {
    val newLines: Vector[String] = lines ++ another.lines
    copy(lines = newLines)
  }
}

def allOrientation(image: Image): Vector[Image] = {
  Vector(
    image,
    image.mirrored,
    image.turnRight,
    image.turnRight.mirrored,
    image.turnRight.turnRight,
    image.turnRight.turnRight.mirrored,
    image.turnRight.turnRight.turnRight,
    image.turnRight.turnRight.turnRight.mirrored
  )
}

def available(images: Vector[Image], x: Int, y: Int, acc: Array[Array[Image]]): Vector[Image] = {
  var result = images
  if 0 < x then
    val leftSide = acc(y)(x - 1).right
    result = result.filter { _.left == leftSide }
  if 0 < y then
    val topSide = acc(y - 1)(x).bottom
    result = result.filter { _.top == topSide }
  result
}

def solve1(images: Vector[Image]): (Array[Array[Image]], BigInt) = {
  val allOrientationImages = images.flatMap(allOrientation)
  val squareSize = math.sqrt(images.size).toInt
  val acc = Array.ofDim[Image](squareSize, squareSize)

  def step(images: Vector[Image], x: Int, y: Int): Option[BigInt] = {
    if images.isEmpty then
      if y == squareSize then
        Some(acc(0)(0).id * acc(0)(squareSize - 1).id * acc(squareSize - 1)(0).id * acc(squareSize - 1)(squareSize - 1).id)
      else
        None
    else
      var availableImages = available(images, x, y, acc)
      val nextX = (x + 1) % squareSize
      val nextY = y + (x + 1) / squareSize
      for (image <- availableImages) {
        acc(y)(x) = image
        step(images.filter { _.id != image.id }, nextX, nextY) match {
          case Some(v) =>
            return Some(v)
          case _ =>
        }
      }
      return None
  }

  (acc, step(allOrientationImages, 0, 0).getOrElse(0))
}

val seaMonster = Vector(
  "                  # ",
  "#    ##    ##    ###",
  " #  #  #  #  #  #   "
)

def isSeaMonsterLine(srcLine: String, index: Int, seaMonsterLine: String): Boolean = {
  (0 until seaMonsterLine.size).forall(delta => {
    if '#' == seaMonsterLine(delta) then
      '#' == srcLine(index + delta)
    else
     true
  })
}

def isSeaMonster(image: Image, x: Int, y: Int): Boolean = {
  if image.lines.size < y + seaMonster.size then
    false
  else
    isSeaMonsterLine(image.lines(y), x, seaMonster(0)) && isSeaMonsterLine(image.lines(y + 1), x, seaMonster(1)) && isSeaMonsterLine(image.lines(y + 2), x, seaMonster(2))
}

def removeSeaMonster(lines: Vector[String], x: Int, y: Int, dx: Int = 0, dy: Int = 0): Vector[String] = {
  if dy >= seaMonster.size then
    lines
  else if dx >= seaMonster(0).size then
    removeSeaMonster(lines, x, y, 0, dy + 1)
  else if '#' == seaMonster(dy)(dx) then
    val nextLines = lines.updated(y + dy, lines(y + dy).updated(x + dx, '0'))
    removeSeaMonster(nextLines, x, y, dx + 1, dy)
  else
    removeSeaMonster(lines, x, y, dx + 1, dy)
}

def removeAllSeaMonster(image: Image, x: Int = 0, y: Int = 0, numberOfSeaMonster: Int = 0): (Int, Image) = {
  if image.lines.size < y + seaMonster.size then
    (numberOfSeaMonster, image)
  else if image.lines(0).size < x + seaMonster(0).size then
    removeAllSeaMonster(image, 0, y + 1, numberOfSeaMonster)
  else if isSeaMonster(image, x, y) then
    val lines = removeSeaMonster(image.lines, x, y)
    removeAllSeaMonster(image.copy(lines = lines), x + 1, y, numberOfSeaMonster + 1)
  else
    removeAllSeaMonster(image, x + 1, y, numberOfSeaMonster)
}

def solve2(mergedMap: Array[Array[Image]]): Int = {
  val mergedImage = mergedMap.map { yImages =>
    yImages.map(_.removeBorders()).reduce(_.mergeHorizontally(_))
  }.reduce(_.mergeVertically(_))
  allOrientation(mergedImage).map(image => {
    val (monsterNum, resultImage) = removeAllSeaMonster(image)
    (monsterNum, resultImage.lines.map(_.count('#' == _)).sum)
  }).find(0 != _._1).get._2
}

@main def solve20() =
  val in = new FileInputStream("example20-1.in")
  System.setIn(in)

  val inputs = Iterator.continually(StdIn.readLine()).takeWhile(_ != null).toVector
  val (images, _, _) = (inputs :+ "").foldLeft((Vector[Image](), Image(), Option.empty[BigInt])) { (acc, line) =>
    if line.isEmpty then
      (acc._1 :+ acc._2, Image(), None)
    else if acc._3.isEmpty then
      val id = BigInt(line.filter(_.isDigit))
      (acc._1, acc._2.copy(id), Some(id))
    else
      val image = acc._2.copy(lines = acc._2.lines :+ line)
      (acc._1, image, acc._3)
  }
  val (mergedMap, answer1) = solve1(images.filter(_.lines.nonEmpty))
  println(answer1)
  println(solve2(mergedMap))