Day9.scala

package sungkmi.aoc2020.day9

import scala.collection.immutable.LazyList

def findFirstInvalid(prembleLength: Int, numbers: List[BigInt]): Option[BigInt] =
  if numbers.size <= prembleLength then None else
    val (front, end) = numbers `splitAt` prembleLength

    val valid = for
      i <- front.to(LazyList)
      j <- front if i != j && i + j == end.head
    yield end.head

    if valid.isEmpty then Some(end.head) else
      findFirstInvalid(prembleLength, numbers.tail)

def findRange(numbers: IndexedSeq[BigInt], target: BigInt): Option[Seq[BigInt]] =
  @annotation.tailrec
  def loop(from: Int, to: Int): Option[Seq[BigInt]] =
    println(s"===> ($from, $to)")
    if to >= numbers.size then None else
      val range = numbers.drop(from).take(to - from + 1)
      val sum = range.sum
      if sum == target then Some(range)
      else if sum > target then loop(from + 1, to)
      else loop(from, to + 1)
  loop(0, 0)
      
@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))
  }
}