SavingTheUniverse.scala

object SavingTheUniverse extends App {

  @annotation.tailrec
  def minSwitch(searchEngines: Seq[String], queries: Seq[String], acc: Int = 0): Int =
    if ((searchEngines diff queries).nonEmpty) acc
    else {
      val (engine, index) = queries.zipWithIndex.groupBy(_._1).mapValues(_.map(_._2).min).maxBy(_._2)
      minSwitch(searchEngines, queries drop index, acc + 1)
    }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next().toInt) {
      def read() = Seq.fill(lineIn.next().toInt)(lineIn.next())
      lineOut(s"Case #$i: ${minSwitch(read(), read())}")
    }

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

}

SavingTheUniverseTest.scala

import org.scalatest._

import SavingTheUniverse._

class SavingTheUniverseTest extends FunSuite {

  test("sample #1") {
    
    val engines = Seq("Yeehaw", "NSM", "Dont Ask", "B9", "Googol")
    val queries = Seq("Yeehaw", "Yeehaw", "Googol", "B9", "Googol",
        "NSM", "B9", "NSM", "Dont Ask", "Googol")
    
    assert(minSwitch(engines, queries) === 1)
  }
  
  
  test("sample #2") {
    
    val engines = Seq("Yeehaw", "NSM", "Dont Ask", "B9", "Googol")
    val queries = Seq("Googol", "Dont Ask", "NSM", "NSM", "Yeehaw", "Yeehaw", "Googol")
    
    assert(minSwitch(engines, queries) === 0)
  }
  
  test("sample case") {
    val input = """2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol""".lines

    val expected = """Case #1: 1
Case #2: 0""".lines

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

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

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

  test("full large case") {
    val input = io.Source.fromFile("A-large-practice.in").getLines()
    val expected = io.Source.fromFile("a.large.out.ref").getLines()

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