Google Code Jam 2014 Qualification Round D Deceitful War

deceitful_war.scala

object deceitful_war extends App {
    val NAOMI = true
    val KEN = false
    
    def remove_first(who: Boolean, all: List[(Double, Boolean)]): List[(Double, Boolean)] = {
        all.takeWhile(_._2 != who) ::: all.dropWhile(_._2 != who).tail
    }

    def remove_last(who: Boolean, all: List[(Double, Boolean)]): List[(Double, Boolean)] = {
        remove_first(who, all.reverse).reverse
    }

    def deceitful(naomis: List[(Double, Boolean)], kens: List[(Double, Boolean)]): Int = {
        def deceitful_inner(all: List[(Double, Boolean)]): Int = all match {
            case Nil => 0
            case head :: tail => head match {
                case (_, KEN) => {
                    0 + deceitful_inner(remove_last(NAOMI, tail))
                }
                case (_, NAOMI) => {
                    1 + deceitful_inner(remove_first(KEN, tail))
                }
            }
        }
        
        val all = (naomis ::: kens).sortWith((x, y) => x._1 > y._1)
        deceitful_inner(all)
    }
    
    def war(naomis: List[(Double, Boolean)], kens: List[(Double, Boolean)]): Int = {
        def war_inner(all: List[(Double, Boolean)]): Int = all match {
            case Nil => 0
            case head :: tail => head match {
                case (_, KEN) => {
                    0 + war_inner(remove_first(NAOMI, tail))
                }
                case (_, NAOMI) => {
                    1 + war_inner(remove_last(KEN, tail))
                }
            }
        }
        
        val all = (naomis ::: kens).sortWith((x, y) => x._1 > y._1)
        war_inner(all)
    }
    
    def solve(naomi: List[Double], ken: List[Double]): (Int, Int) = {
        val naomis = for (n <- naomi) yield (n, NAOMI)
        val kens = for (k <- ken) yield (k, KEN)
        (deceitful(naomis, kens), war(naomis, kens))
    }

    //////////
    // main //
    //////////
    if (args.length > 0) Console.setIn(new java.io.FileInputStream(args(0)))
    if (args.length > 1) Console.setOut(new java.io.FileOutputStream(args(1)))

    for (t <- 1 to readInt) {
        val N = readInt
        val naomi = readLine.split(" ").map(_.toDouble).toList
        val ken = readLine.split(" ").map(_.toDouble).toList
        val (y, z) = solve(naomi, ken)
        println("Case #" + t + ": " + y + " " + z)
    }
}