BoxFactory.scala

object BoxFactory extends App {

  def largestNumberOfBoxedToys(toys: List[(Long, Int)], boxes: List[(Long, Int)]): Long = {

    val memo = collection.mutable.Map.empty[(List[(Long, Int)], List[(Long, Int)]), Long]

    def largestNumberOfBoxedToys0(toys: List[(Long, Int)], boxes: List[(Long, Int)]): Long = {

      if (memo.contains((toys, boxes))) memo((toys, boxes))
      else {
        val result = (toys, boxes) match {

          case (Nil, boxes) => 0
          case (toys, Nil) => 0

          case ((x, xt) :: xs, (y, yt) :: ys) if xt == yt =>
            if (x >= y)
              y + largestNumberOfBoxedToys0((x - y, xt) :: xs, ys)
            else if (x == y)
              x + largestNumberOfBoxedToys0(xs, ys)
            else
              x + largestNumberOfBoxedToys0(xs, (y - x, yt) :: ys)

          case (x :: xs, y :: ys) =>
            largestNumberOfBoxedToys0(xs, boxes) max largestNumberOfBoxedToys0(toys, ys)

        }

        memo((toys, boxes)) = result

        result
      }
    }

    largestNumberOfBoxedToys0(toys, boxes)

  }
  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(n, m) = lineIn.next() split ' ' map (_.toInt)
      val toys = lineIn.next().split(' ').grouped(2).toList.map { case Array(n, t) => (n.toLong, t.toInt) }
      val boxes = lineIn.next().split(' ').grouped(2).toList.map { case Array(n, t) => (n.toLong, t.toInt) }
      lineOut(s"Case #$i: ${largestNumberOfBoxedToys(toys, boxes)}")
    }

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

}

BoxFactoryTest.scala

import org.scalatest._

import BoxFactory._

class BoxFactoryTest extends FunSuite {

  test("sample #1") {
    assert(largestNumberOfBoxedToys(List((10, 1), (20, 2), (25, 3)), List((10, 2), (30, 3), (20, 1))) === 35)
  }
  
  test("sample #2") {
    assert(largestNumberOfBoxedToys(List((10, 1), (6, 2), (10, 1)), List((5, 1), (3, 2), (10, 1), (3, 2), (5, 1))) === 20)
  }
  
  test("sample case") {
    val input = """4
3 3
10 1 20 2 25 3
10 2 30 3 20 1
3 5
10 1 6 2 10 1
5 1 3 2 10 1 3 2 5 1
3 5
10 1 6 2 10 1
5 1 6 2 10 1 6 2 5 1
1 1
5000000 10
5000000 100""".lines

    val expected = """Case #1: 35
Case #2: 20
Case #3: 21
Case #4: 0""".lines

    process(input) { s =>
      for (line <- s.lines)
        assert(line === expected.next())
    }
  }

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

    process(input) { s =>
      for (line <- s.lines)
        assert(line.trim === expected.next().trim)
    }
  }

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

    process(input) { s =>
      for (line <- s.lines)
        assert(line.trim === expected.next().trim)
    }
  }
}