BotTrust.scala

import collection.immutable.SortedSet

object BotTrust extends App {

  type OrderList = List[(String, Int)]

  def minTime(orders: OrderList): Int = {

    type ArrivalSet = SortedSet[(Int, String, Int)]

    def updatedArrivals(departureTime: Int, botPos: Int, orders: OrderList)(
      arrivals: ArrivalSet, bot: String): ArrivalSet = {
      val next = orders find (_._1 == bot) map (_._2)
      if (next.isEmpty) arrivals
      else arrivals + { (departureTime + (next.get - botPos).abs, bot, next.get) }
    }

    @annotation.tailrec
    def simulate(time: Int, orders: OrderList, botPos: Map[String, Int])(
      arrivals: ArrivalSet): Int =

      if (orders.isEmpty) time
      else {
        val (bot, button) = orders.head
        val (time1, orders1, botPos1, arrivals1) = if (botPos(bot) == button)
          (time + 1, orders.tail, botPos,
            updatedArrivals(time + 1, button, orders.tail)(arrivals, bot))
        else {
          val (arrivalTime, arrivedBot, button) = arrivals.head
          (arrivalTime max time, orders, botPos + (arrivedBot -> button), arrivals.tail)
        }
        simulate(time1, orders1, botPos1)(arrivals1)
      }

    simulate(0, orders, Map("O" -> 1, "B" -> 1)) {
      (SortedSet.empty[(Int, String, Int)] /: Seq("O", "B")) { updatedArrivals(0, 1, orders) }
    }
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val order = lineIn.next().split(' ').tail.grouped(2).map {
        case Array(bot, button) => (bot, button.toInt)
      }.toList
      lineOut(s"Case #$i: ${minTime(order)}")
    }

  val writer = new java.io.PrintWriter("a.large.out")
  try {
    process(io.Source.fromFile("A-large-practice.in").getLines) { s =>
      writer.println(s)
      writer.flush()
    }
  } finally {
    writer.flush(); writer.close()
  }

}

BotTrustTest.scala

import org.scalatest._

import BotTrust._

class BotTrustTest extends FunSuite {

  test("base #1") {
    assert(minTime(List()) === 0)
  }

  test("base #2") {
    assert(minTime(List(("O", 1))) === 1)
  }

  test("base #3") {
    assert(minTime(List(("O", 2))) === 2)
  }

  test("base #4") {
    assert(minTime(List(("O", 2), ("B", 1))) === 3)
  }

  test("base #5") {
    assert(minTime(List(("O", 2), ("B", 2))) === 3)
  }

  test("sample #1") {
    assert(minTime(List(("O", 2), ("B", 1), ("B", 2), ("O", 4))) === 6)
  }

  test("sample #2") {
    assert(minTime(List(("O", 5), ("O", 8), ("B", 100))) === 100)
  }

  test("sample #3") {
    assert(minTime(List(("B", 2), ("B", 1))) === 4)
  }
  
  test("sample case") {
    val input = """3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1""".lines

    val expected = """Case #1: 6
Case #2: 100
Case #3: 4""".lines

    lineComparison(input, expected)
  }

  test("full small case") {
    val input = io.Source.fromFile("A-small-practice.in").getLines()
    val expected = io.Source.fromFile("a.small.out.ref").getLines()

    lineComparison(input, expected)
  }

  ignore("full large case") {
    val input = io.Source.fromFile("A-large-practice.in").getLines()
    val expected = io.Source.fromFile("a.large.out.ref").getLines()

    lineComparison(input, expected)
  }

  def lineComparison(input: Iterator[String], expected: Iterator[String]) {
    process(input) { s =>
      for (line <- s.lines) assert(line.trim === expected.next().trim)
    }
    assert(expected.hasNext === false, "Finished too fast.")
  }

}