Advent of Code 13.scala

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

@main def solve13() =

  def gcd(a: BigInt, b: BigInt): BigInt = {
    if b == 0 then a else gcd(b, a % b)
  }

  def lcm(a: BigInt, b: BigInt): BigInt = {
    a * b / gcd(a, b)
  }

  def solve1(departTime: BigInt, busIds: Vector[Option[BigInt]]): BigInt = {
    val depratTimeListOfBus = busIds.flatten.map(id => (id, (departTime + id - 1) / id * id))
    val (busId, depratTimeOfBus) = depratTimeListOfBus.minBy(_._2)
    (depratTimeOfBus - departTime) * busId
  }
  
  case class Bus(id: BigInt, idx: Int, increment: BigInt)

  def solve2(busIds: Vector[Option[BigInt]]): BigInt = {
    def merge(bus1: Bus, bus2: Bus): Bus = {
      def _merge(timestamp: BigInt): BigInt = {
        if 0 == (timestamp + bus2.idx) % bus2.increment then
          timestamp
        else
          _merge(timestamp + bus1.increment)
      }
      val mergedTimestamp = _merge(bus1.id - bus1.idx)
      Bus(mergedTimestamp, 0, lcm(bus1.increment, bus2.increment))
    }
    
    val busIdAndIndex: Vector[Bus] = busIds.zipWithIndex.flatMap((id, idx) => id.map(_id => Bus(_id, idx, _id)))
    busIdAndIndex.reduce(merge).id
  }
  
  val in = new FileInputStream("example13-1.in")
  System.setIn(in)

  val inputs = Iterator.continually(StdIn.readLine())
  val departTime = inputs.next().toInt
  val busIds = inputs.next().split(",").map(x => x.toIntOption.map(BigInt.apply)).toVector
  val answer1 = solve1(departTime, busIds)
  println(answer1)
  val answer2 = solve2(busIds)
  println(answer2)