Skip to content

Instantly share code, notes, and snippets.

@sungkmi
Last active August 29, 2015 14:24
Show Gist options
  • Save sungkmi/89f37e8f07e18a74d8ea to your computer and use it in GitHub Desktop.
Save sungkmi/89f37e8f07e18a74d8ea to your computer and use it in GitHub Desktop.
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()
}
}
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.")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment