Day13.scala

package sungkmi.aoc2020.day13

import scala.util.Try

type Timestamp = Long
type Id = Int
type Minute = Long

def parse(s: String): (Timestamp, Seq[Option[Id]]) =
  val Array(line1, line2) = s.split("\n")
  (line1.toLong, line2.split(",").toSeq.map(s => Try(s.toInt).toOption))

def waitingTime(m: Timestamp, id: Id): Timestamp =
  val r = m % id
  if r == 0L then 0 else m + id.toLong - r

def earliestBus(m: Timestamp, ids: Seq[Id]): (Minute, Id) =
  ids.map(id => (waitingTime(m, id) - m, id)).min

def earliestTimestamp(buses: Map[Id, Int]): BigInt =
  val m = buses.keys.map(BigInt(_)).product
  val x = buses.map:
    (m, a) =>
      val n = buses.keys.map(_ % m).map(BigInt(_)).product % m
      val s = (0 until n.toInt).map{ i => (n * i % m, i) }.find(_._1 == 1).get._2
      a * n * s
  .sum
  x % m


@main def part1: Unit =
  val (minTime, ids) = parse(input)
  val (minutes, id) = earliestBus(minTime, ids.flatten)
  val ans = minutes * id
  println(ans)

@main def part2: Unit = 
  val ids = parse(input)._2
  val buses = ids.zipWithIndex.flatMap:
    case (Some(id), index) => Seq(id -> index)
    case (None, _) => Seq.empty
  .toMap
  val ans = earliestTimestamp
  println(ans)

lazy val input: String = """1004345
41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,379,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,557,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,19"""

Day13Test.scala

package sungkmi.aoc2020.day13

class Day13Test extends munit.FunSuite {

  val minTime: Timestamp = 939

  test("waitingTime bus 7") {
    assertEquals(waitingTime(minTime, 7), 945L)
  }

  test("waitingTime bus 13") {
    assertEquals(waitingTime(minTime, 13), 949L)
  }

  test("waitingTime bus 59") {
    assertEquals(waitingTime(minTime, 59), 944L)
  }
  
  test("earliestBus") {
    assertEquals(earliestBus(minTime, Seq(7, 13, 59, 31, 19)), (5L, 59))
  }

  test("parse day13") {
    val testInput = """939
7,13,x,x,59,x,31,19"""

    val expected = (
      939L,
      Seq(Some(7), Some(13), None, None, Some(59), None, Some(31), Some(19))
    )

    assertEquals(parse(testInput), expected)
  }

  test("earliestTimestamp") {
    val buses = Map(7 -> 0, 13 -> 1, 59 -> 4, 31 -> 6, 19 ->7)
    assertEquals(earliestTimestamp(buses), BigInt(1068781))
  }
}