Day9.scala

package sungkmi.aoc2020.day9

import scala.collection.immutable.LazyList

def findFirstInvalid(prembleLength: Int, numbers: List[BigInt]): Option[BigInt] =
  numbers.sliding(prembleLength + 1, 1).find:
    (window: List[BigInt]) =>
      val target :: premble = window.reverse
      val valid = for
        i <- premble.to(LazyList)
        j <- premble if i != j && i + j == target
      yield target
      valid.isEmpty
  .map(_.last)

def findRange(numbers: IndexedSeq[BigInt], target: BigInt): Option[Seq[BigInt]] =
  @annotation.tailrec
  def loop(from: Int, to: Int, sum: BigInt): Option[(Int, Int)] =
    (sum - target).signum match
      case 0 => Some((from, to))
      case 1 => loop(from + 1, to, sum - numbers(from))
      case -1 if to + 1 < numbers.size => loop(from, to + 1, sum + numbers(to + 1))
      case _ => None
  for
    head <- numbers.headOption
    (from, to) <- loop(0, 0, head)
  yield numbers.drop(from).take(to - from + 1)

@main def part1: Unit =
  val ans = findFirstInvalid(25, numbers.toList)
  println(ans)

@main def part2: Unit =
  val ans = for
    target <- findFirstInvalid(25, numbers.toList)
    range <- findRange(numbers.toIndexedSeq, target)
  yield
    range.min + range.max
  println(ans)

val numbers = input.split("\n").map(BigInt(_))

// lazy val input: String = """38

Day9Test.scala

package sungkmi.aoc2020.day9

class Day9Test extends munit.FunSuite {

  val numbers = List(
    35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299, 277, 309, 576
  ).map(BigInt(_))

  test("findFirstInvalid") {
    assertEquals(findFirstInvalid(5, numbers), Some(BigInt(127)))
  }

  test("findRange") {
    val expected = Seq(15, 25, 47, 40).map(BigInt(_))
    assertEquals(findRange(numbers.toIndexedSeq, BigInt(127)), Some(expected))
  }
}