KingdomRush.scala

object KingdomRush extends App {

  def minNumberOfLevels(levels: Seq[(Int, Int)]): Option[Int] = {
    @annotation.tailrec
    def loop(levels: List[(Int, Int)], partials: List[(Int, Int)], currentStar: Int, count: Int): Option[Int] = {
      if (levels.isEmpty && partials.isEmpty) Some(count)
      else (partials partition (_._2 <= currentStar) match {
        case (Nil, unclearables) => levels partition (_._2 <= currentStar) match {
          case (Nil, unclearables) => levels find (_._1 <= currentStar) match {
            case Some(partial) =>
              Some(levels diff partial :: Nil, partial :: partials, currentStar + 1, count + 1)
            case None =>
              None
          }
          case (clearables, unclearables) =>
            Some(unclearables, partials, currentStar + 2 * clearables.size, count + clearables.size)
        }
        case (clearables, unclearables) =>
          Some(levels, unclearables, currentStar + clearables.size, count + clearables.size)

      }) match {
        case Some((levels, partials, currentStar, count)) =>
          loop(levels, partials, currentStar, count)
        case None =>
          None
      }
    }
    loop(levels.sortBy(-_._2).toList, Nil, 0, 0)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val n = lineIn.next().toInt
      val levels = Seq.fill(n) {
        val Array(a, b) = lineIn.next() split ' ' map (_.toInt)
        (a, b)
      }
      lineOut(s"Case #$i: ${minNumberOfLevels(levels) getOrElse "Too Bad"}")
    }

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

}

KingdomRushTest.scala

import org.scalatest._

import KingdomRush._

class KingdomRushTest extends FunSuite {

  test("sample #1") {
    assert(minNumberOfLevels(Seq((0, 1), (0, 2))) === Some(3))

  }

  test("sample #2") {
    assert(minNumberOfLevels(Seq((2, 2), (0, 0), (4, 4))) === Some(3))

  }

  test("sample #3") {
    assert(minNumberOfLevels(Seq((1, 1))) === None)

  }

  test("sample #4") {
    assert(minNumberOfLevels(Seq((0, 5), (0, 1), (1, 1), (4, 7), (5, 6))) === Some(6))
  }

  test("small #5") {
    val input = """1
9
6 9
14 18
3 14
0 0
2 9
7 13
5 7
4 5
7 14""".lines

    val expected = """Case #1: Too Bad""".lines

    lineComparison(input, expected)
  }

  test("small #9") {
    val levels = List((0, 5), (0, 7), (0, 2), (0, 3), (0, 1), (0, 2), (0, 13))
    assert(minNumberOfLevels(levels) === Some(8))
  }

  test("small #42") {
    val levels = List((0, 3), (1, 1), (6, 7), (4, 5), (1, 7))
    assert(minNumberOfLevels(levels) === Some(7))
  }

  test("small #100") {
    val levels = List((0, 6), (1, 8), (3, 8), (1, 4), (0, 5))
    assert(minNumberOfLevels(levels) === Some(9))
  }

  test("sample case") {
    val input = """4
2
0 1
0 2
3
2 2
0 0
4 4
1
1 1
5
0 5
0 1
1 1
4 7
5 6""".lines

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

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

  test("full large case") {
    val input = io.Source.fromFile("B-large-practice.in").getLines()
    val expected = io.Source.fromFile("b.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.")
  }

}