WCC 2012.23

scala.log

scala> println(f(522, List(100, 5, 5, 2, 6, 8)).map(f => f.toString + " = " + f.r).mkString("\n"))
(((100.0 - 5.0) - 8.0) * 6.0) = 522.0
(((100.0 + 6.0) * 5.0) - 8.0) = 522.0
(((100.0 - 8.0) - 5.0) * 6.0) = 522.0
(((6.0 + 100.0) * 5.0) - 8.0) = 522.0
(((((5.0 - 8.0) * 5.0) + 100.0) + 2.0) * 6.0) = 522.0
(((((5.0 - 8.0) * 5.0) + 2.0) + 100.0) * 6.0) = 522.0
(((((2.0 / 5.0) * 8.0) + 100.0) * 5.0) + 6.0) = 522.0
(((((2.0 * 8.0) / 5.0) + 100.0) * 5.0) + 6.0) = 522.0
(((((2.0 * 8.0) + 6.0) / 5.0) + 100.0) * 5.0) = 522.0
(((((8.0 / 5.0) * 2.0) + 100.0) * 5.0) + 6.0) = 522.0
(((((8.0 * 2.0) / 5.0) + 100.0) * 5.0) + 6.0) = 522.0
(((((8.0 * 2.0) + 6.0) / 5.0) + 100.0) * 5.0) = 522.0

solution.scala

case class Op(rep: String, op: (Double, Double) => Double) {
    def apply(a: Double, b: Double) : Double = op(a,b)
    override def toString = rep
}
val ops = List(Op("+", (_ + _)),  Op("-", (_ - _)), Op("*", (_ * _)), Op("/", (_ / _)))

trait Result { def r : Double }
case class NumResult(r: Double) extends Result { override def toString = r.toString }
case class OpResult(a: Result, b: Result, op: Op) extends Result { 
    lazy val r = op(a.r, b.r)
    override def toString = "("+a+" "+op+" "+b+")"
}

def numberCombinations(l: List[Int]) : Seq[Seq[Result]] = {
    val r = l.map(NumResult(_))
    (2 to r.size).flatMap { i => r.combinations(i).flatMap(_.permutations) }
}

def operationCombinations(size: Int) = {
    def oc(size: Int, l: List[List[Op]]) : List[List[Op]] = size match {
        case 1 => l
        case _ => oc(size - 1, l.flatMap { ol: List[Op] => ops.map(_ :: ol) })
    }
    oc(size, ops.map(List(_)))
}

def f(x: Int, l: List[Int]) = {
    val combinations = for {
        nc <- numberCombinations(l)
        oc <- operationCombinations(nc.size - 1)
    } yield nc.tail.zip(oc).foldLeft(nc.head) { case (func, (r, op)) => OpResult(func, r, op) }

    val result = combinations.tail.foldLeft(combinations.head) { (currentResult, otherResult) =>
        if (math.abs(otherResult.r - x) < math.abs(currentResult.r - x)) otherResult else currentResult
    }

    combinations.filter(_.r == result.r)
}