WelcomeToCodeJam.scala

object WelcomeToCodeJam extends App {

  def countSubsequences(s: String): Int = {
    val ref = "welcome to code jam"

    val memo = Array.fill[Option[Int]](s.size, ref.size)(None)

    def c(i: Int, j: Int): Int =
      if (j < 0) 1
      else if (i < 0) 0
      else memo(i)(j) match {
        case Some(ans) => ans
        case None =>
          val ans = {
            if (s(i) == ref(j)) (c(i - 1, j) + c(i, j - 1))
            else c(i - 1, j)
          } % 10000
          memo(i)(j) = Some(ans)
          ans
      }

    c(s.size - 1, ref.size - 1)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      lineOut(f"Case #$i: ${countSubsequences(lineIn.next())}%04d")
    }

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

}

WelcomeToCodeJamTest.scala

import org.scalatest._

import WelcomeToCodeJam._

class WelcomeToCodeJamTest extends FunSuite {

  test("sample #1") {
    assert(countSubsequences("elcomew elcome to code jam") === 1)
  }

  test("sample #2") {
    assert(countSubsequences("wweellccoommee to code qps jam") === 256)
  }
  
  test("sample #3") {
    assert(countSubsequences("welcome to codejam") === 0)
  }
  
  test("large digit") {
    assert(countSubsequences("wweellccoommee  ttoo  ccoodde jam") === 6384)
  }
  
  
  test("sample case") {
    val input = """3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam""".lines

    val expected = """Case #1: 0001
Case #2: 0256
Case #3: 0000""".lines

    lineComparison(input, expected)
  }

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

    lineComparison(input, expected)
  }

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