TypewriterMonkey.scala

object TypewriterMonkey extends App {

  def expectedBanana(keyboard: String, target: String, numberOfTyping: Int): Double = {

    if ((target.toSet -- keyboard.toSet).nonEmpty) 0
    else {
      val maxBanana = {

        val head = (1 to target.size).find { i =>
          target startsWith target.drop(i)
        }.get

        1 + (numberOfTyping - target.size) / head
      }

      val probabilityOfATarget = {
        val pMap = keyboard groupBy identity mapValues (_.size.toDouble / keyboard.size)
        target.map(ch => pMap(ch)).fold(1.0)(_ * _)
      }

      maxBanana - (probabilityOfATarget * (numberOfTyping - target.size + 1))
    }
  }

  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)
  }
  
  ignore("full small case") {
    val input = io.Source.fromFile("C-small-practice-1.in").getLines()
    val expected = io.Source.fromFile("C-small-practice-1.out").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-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.")
  }

}