Advent of Code 16.scala

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

case class Range(min: Int, max: Int)
case class Field(name: String, ranges: Vector[Range])
case class Input(fields: Vector[Field], myTicket: Vector[Int], nearbyTickets: Vector[Vector[Option[Int]]])
case class FieldAndPositions(field: Field, positions: Vector[Int])

enum InputType {
  case field
  case myTicket
  case nearbyTicket
}

extension (range: Range)
  def contains(x: Int): Boolean = range.min <= x && range.max >= x

extension (field: Field)
  def contains(x: Int): Boolean = field.ranges.exists(_.contains(x))

@main def solve16() =
  def solve1(input: Input): Int = {
    val fields = input.fields
    input.nearbyTickets.flatten.map(_.get).filter(x => !fields.exists(_.contains(x))).sum
  }

  def isValidFieldAndPosition(field: Field, idx: Int, nearbyTickets: Vector[Vector[Option[Int]]]): Boolean = {
    nearbyTickets.forall { ticket =>
      ticket(idx).map(field.contains).getOrElse(true)
    }
  }

  def findValidFieldAndPosition(fieldAndPositionsVector: Vector[FieldAndPositions], history: Vector[Int] = Vector()): Option[Vector[(Field, Int)]] = {
    if fieldAndPositionsVector.length == history.length then
      Some((fieldAndPositionsVector zip history).map { (field, idx) => (field.field, idx) })
    else {
      val fieldAndPositions = fieldAndPositionsVector(history.length)
      fieldAndPositions.positions.filter(idx => !history.contains(idx)).to(LazyList).map { idx =>
        findValidFieldAndPosition(fieldAndPositionsVector, history :+ idx)
      }.collectFirst { case Some(x) => x }
    }
  }

  def solve2(input: Input): BigInt = {
    val allRanges = input.fields.flatMap(_.ranges)
    val nearbyTickets = input.nearbyTickets.map(_.map(x => if allRanges.exists(_.contains(x.get)) then x else None))
    val fieldsAndPositions = input.fields.map(field => FieldAndPositions(field, (0 until input.fields.length).toVector))
    val validFieldsAndPositions = fieldsAndPositions.map { fieldsAndPosition =>
      val validPositions = fieldsAndPosition.positions.filter(isValidFieldAndPosition(fieldsAndPosition.field, _, nearbyTickets))
      fieldsAndPosition.copy(positions = validPositions)
    }.sortBy(_.positions.length)

    val validFields = findValidFieldAndPosition(validFieldsAndPositions)
    validFields match {
      case Some(fields) =>
        val departureFields = fields.filter(_._1.name.startsWith("departure"))
        val numbers = departureFields.map((_, idx) => input.myTicket(idx))
        numbers.map(BigInt.apply).foldLeft(BigInt(1))(_ * _)
      case _ =>
        0
    }
  }

  def parse(inputs: Iterator[String], acc: Input = Input(Vector(), Vector(), Vector()), stage: InputType = InputType.field): Input = {
    val line = inputs.next()
    if null != line then
      if line.trim.isEmpty then
        parse(inputs, acc, stage)
      else
        stage match {
          case InputType.field =>
            if line.contains("your ticket:") then
              parse(inputs, acc, InputType.myTicket)
            else
              val name = line.split(":")(0).trim
              val numbers = line.map(x => if x.isDigit then x else ' ').split(" ").filter(_.nonEmpty).map(_.toInt)
              val field = Field(name, Vector(Range(numbers(0), numbers(1)), Range(numbers(2), numbers(3))))
              parse(inputs, acc.copy(fields = acc.fields :+ field), stage)
          case InputType.myTicket =>
            if line.contains("nearby tickets:") then
              parse(inputs, acc, InputType.nearbyTicket)
            else
              val numbers = line.split(",").map(_.toInt).toVector
              parse(inputs, acc.copy(myTicket = acc.myTicket ++ numbers), stage)
          case InputType.nearbyTicket =>
            val numbers = line.split(",").map(x => Some(x.toInt)).toVector
            parse(inputs, acc.copy(nearbyTickets = acc.nearbyTickets :+ numbers), stage)
      }
    else
      acc
  }

  val in = new FileInputStream("example16-1.in")
  System.setIn(in)

  val inputs = Iterator.continually(StdIn.readLine())
  val input = parse(inputs)
  val answer1 = solve1(input)
  println(answer1)
  val answer2 = solve2(input)
  println(answer2)