-
-
Save tyrcho/5292422 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 ) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment