Advent of Code 2022-15.scala

import java.io.FileInputStream
import scala.annotation.{tailrec, targetName}
import scala.io.StdIn
import scala.language.postfixOps
import scala.math.abs

case class Point(x: Int, y: Int):
  def distance(other: Point): Int = abs(x - other.x) + abs(y - other.y)

case class Range(min: Int, max: Int):
  def length: Int = max - min + 1

  def contains(v: Int): Boolean = min <= v && v <= max

  def contains(v: Range): Boolean = min <= v.min && v.max <= max

case class RangeSet(ranges: Vector[Range]):
  def + (range: Range): RangeSet =
    val newRanges = (ranges :+ range).sortBy(_.min).foldLeft(Vector.empty[Range]) { (acc, r) =>
      acc.lastOption match
        case None =>
          Vector(r)
        case Some(last) =>
          if last.max < r.min then
            acc :+ r
          else
            acc.init :+ Range(last.min min r.min, last.max max r.max)
    }
    RangeSet(newRanges)


  def ++(rangeSet: RangeSet): RangeSet =
    rangeSet.ranges.foldLeft(this)(_ + _)

  def contains(v: Int): Boolean = ranges.exists(_.contains(v))

  def contains(v: Range): Boolean = ranges.exists(_.contains(v))

object RangeSet:
  def empty(): RangeSet = RangeSet(Vector.empty)

case class Input(sensor: Point, beacon: Point)

object Input {
  def apply(input: String): Input =
    val parts = input.filter(c => c != ',' && c != ':').split(" ")
    val sensor = Point(parts(2).split("=")(1).toInt, parts(3).split("=")(1).toInt)
    val beacon = Point(parts(8).split("=")(1).toInt, parts(9).split("=")(1).toInt)
    Input(sensor, beacon)
}

def nonBeaconXList(input: Input, y: Int): RangeSet =
  val maxDistance = input.sensor.distance(input.beacon)
  val height = abs(y - input.sensor.y)
  if maxDistance < height then
    RangeSet.empty()
  else
    val deltaX = maxDistance - height
    RangeSet(Vector(Range(input.sensor.x - deltaX, input.sensor.x + deltaX)))

def nonBeaconXList(input: Vector[Input], y: Int): RangeSet =
  input.map(nonBeaconXList(_, y)).reduce(_ ++ _)

def solve15_1(input: Vector[Input], y: Int): Int =
  val nonBeaconXs = nonBeaconXList(input, y)
  val beaconXs: Set[Int] = input.filter(_.beacon.y == y).map(_.beacon.x).toSet
  nonBeaconXs.ranges.map(_.length).sum - beaconXs.count(nonBeaconXs.contains)

def solve15_2(input: Vector[Input], maxCoordinate: Int): BigInt =
  val result: Vector[(Int, Int)] = (0 to maxCoordinate).toVector.flatMap { y =>
    val rangeSet = nonBeaconXList(input, y)
    if !rangeSet.contains(Range(0, maxCoordinate)) then
      (0 to maxCoordinate).filter(x => !rangeSet.contains(x)).map(x => (x, y)).toVector
    else
      Vector.empty
  }
  BigInt(result.head._1) * 4000000 + BigInt(result.head._2)


@main def solve15(): Unit =
  val in = new FileInputStream("example15-2.in")
  System.setIn(in)
  val inputs = Iterator.continually(StdIn.readLine())
    .takeWhile(line => null != line)
    .map(Input)
    .toVector
  println(solve15_1(inputs, 2000000))
  println(solve15_2(inputs, 4000000))