TypewriterMonkey.scala

object TypewriterMonkey extends App {

  def expectedBanana(keyboard: String, target: String, numberOfTyping: Int): Double =
    if ((target.toSet -- keyboard.toSet).nonEmpty) 0
    else {
      val redundantSpace = numberOfTyping - target.size
      1 + redundantSpace / (1 to target.size).find(target startsWith target.drop(_)).get -
        (target map (keyboard groupBy identity mapValues (_.size.toDouble / keyboard.size)))
        .fold(redundantSpace + 1.0)(_ * _)
    }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      val Array(k, l, s) = lineIn.next() split ' ' map (_.toInt)
      lineOut(s"Case #$i: ${expectedBanana(lineIn.next(), lineIn.next(), s)}")
    }

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

TypewriterMonkeyTest.scala

import org.scalatest._

import TypewriterMonkey._

class TypewriterMonkeyTest extends FunSuite with Matchers {

  test("sample #1") {
    expectedBanana("BANANAS", "MONKEY", 6) should equal(0.0 +- 1e-6)
  }

  test("sample #2") {
    expectedBanana("AA", "AAA", 4) should equal(0.0 +- 1e-6)
  }

  test("sample #3") {
    expectedBanana("AB", "B", 2) should equal(1.0 +- 1e-6)
  }

  test("sample #4") {
    expectedBanana("GOOGLE", "GO", 2) should equal(0.8888889 +- 1e-6)
  }

  test("sample #5") {
    expectedBanana("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "ROSENCRANTZ", 100) should equal(9.0 +- 1e-6)
  }

  ignore("sample case") {
    val input = """3
4
1 1 12
359 1 12
2 1 12
358 1 12
2
180 1 100000
180 1 1
1
180 2 1""".lines

    val expected = """Case #1: 0
Case #2: 1
Case #3: 0""".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-practice.out").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-practice.out").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.")
  }

}