Google Code Jam: solves goo.gl/NyPoz in O(n log n)

solve.scala

// solves goo.gl/NyPoz in O(n log n)

def solveAll(credit: Int, items: Seq[Int]): (Int, Int) = {
  // build a map from items to their indices in the input (lists of length 1 or 2)
  val indices: Map[Int, Seq[Int]] =
    items.zipWithIndex
      .groupBy(_._1)
      .mapValues(_.map(_._2 + 1))
  def solve(item: Int): Option[(Int, Int)] =
    if(item * 2 == credit)
      indices(item) match {
        case Seq(i, j) => Some((i, j))
        case _ => None
      }
    else indices.get(credit - item) map {
      case Seq(i, _*) => (indices(item).head, i)
    }
  items.view.flatMap(solve).head
}

def processInput(source: io.Source) {
  val groups = source.getLines.drop(1).grouped(3) 
  for{(Seq(credit, _, items), n) <- groups.zipWithIndex
      solution = solveAll(credit.toInt, items.split(" ").map(_.toInt))}
    println("Case #" + (n + 1) + ": " + solution._1 + " " + solution._2)
}

/*
processInput(io.Source.fromString(
  """|3
     |100
     |3
     |5 75 25
     |200
     |7
     |150 24 79 50 88 345 3
     |8
     |8
     |2 1 9 4 4 56 90 3""".stripMargin))
*/

processInput(io.Source.fromFile("A-large-practice.in.txt"))

// "Judge's response for last submission: Correct."