ExprParser.scala

package info.daviot.lceb
import scala.util.parsing.combinator._

sealed trait Expr { def eval: Int }
case class Number(value: Int) extends Expr {
  val eval = value
}
case class Prod(left: Expr, right: Expr) extends Expr {
  def eval = left.eval * right.eval
}
case class Sum(left: Expr, right: Expr) extends Expr {
  def eval = left.eval + right.eval
}
case class Subs(left: Expr, right: Expr) extends Expr {
  def eval = left.eval - right.eval
}
case class Div(left: Expr, right: Expr) extends Expr {
  def eval = {
    val (l, r) = (left.eval, right.eval)
    assert(l % r == 0, s"$l % $r is not 0")
    l / r
  }
}

// PackratParsers improves performance thanks to memorization
object ExprParser extends JavaTokenParsers with PackratParsers {
  def expr: Parser[Expr] =
    (term ~ "+" ~ term) ^^ { case lhs ~ plus ~ rhs => Sum(lhs, rhs) } |
      (term ~ "-" ~ term) ^^ { case lhs ~ minus ~ rhs => Subs(lhs, rhs) } |
      term

  def term: Parser[Expr] =
    (factor ~ "*" ~ factor) ^^ { case lhs ~ times ~ rhs => Prod(lhs, rhs) } |
      (factor ~ "/" ~ factor) ^^ { case lhs ~ div ~ rhs => Div(lhs, rhs) } |
      factor

  def factor: Parser[Expr] =
    "(" ~> expr <~ ")" |
      wholeNumber ^^ { x => Number(x.toInt) }

  def parse(text: String) = parseAll(expr, text)
}

GenLcebSpecs.scala

package info.daviot.lceb

import org.junit.runner.RunWith
import org.specs2.mutable._
import org.specs2.runner.JUnitRunner
import scala.collection.JavaConversions._

class GenLcebSpecs(lcebBuilder: => LCEB) extends SpecificationWithJUnit {

  "LCEB" should {
    val lceb = lcebBuilder

    "solve a basic problem" in {
      val inputs = Array(5, 100)
      val res = lceb.solve(inputs, 500)
      val operations = ExprParser.parse(res).get
      operations.eval must beEqualTo(500)
      operations match {
        case Prod(Number(a), Number(b)) => Seq(a, b) must haveTheSameElementsAs(Seq(5, 100))
        case _ => failure("product expected")
      }
    }

    "solve a complex problem" in {
      val inputs = Array(2, 7, 10, 3)
      val res = "(2+7)*(10+3)" //lceb.solve(inputs, 9 * 13)
      val operations = ExprParser.parse(res).get
      operations.eval must beEqualTo(9 * 13)
    }
  }

}

object ScalaImplLcebSpecs extends GenLcebSpecs(LcebScala)

Lceb.scala

object LCEB {

  def resolve(expected: Int, numbers: Vector[Int]): Vector[String] = {
    def recSolutions(numbers: Vector[Int], r: Int, operation: String): Vector[String] =
      if (expected == r)
        Vector(operation)
      else
        numbers flatMap { i =>
          val rest = numbers diff Vector(i)
          val maybeDiv = if (r % i == 0) Some(r / i, "/") else None
          (for ((newResult, op) <- maybeDiv ++ Seq((r + i, "+"), (r - i, "-"), (r * i, "*")))
            yield recSolutions(rest, newResult, (s"( $operation $op $i )"))).flatten
        }

    numbers flatMap { i =>
      val rest = numbers diff Vector(i)
      recSolutions(rest, i, i.toString)
    }
  }                                               //> resolve: (expected: Int, numbers: Vector[Int])Vector[String]

  resolve(1252, Vector(1, 3, 5, 50, 4, 7)) foreach println
                                                  //> ( ( ( ( ( 50 - 5 ) * 7 ) + 1 ) - 3 ) * 4 )
                                                  //| ( ( ( ( ( 50 - 5 ) * 7 ) - 3 ) + 1 ) * 4 )
}