The problem that the pearl solves is given a number (1, 2, 3, 4, 5, 6, 7, 8, 9) return all expressions containing + and * that make 100. In this case, the output is:
1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9
1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9
12 + 3 * 4 + 5 + 6 + 7 * 8 + 9
1 + 2 * 3 + 4 + 5 + 67 + 8 + 9
1 * 2 + 34 + 5 + 6 * 7 + 8 + 9
12 + 34 + 5 * 6 + 7 + 8 + 9
The following is the specification written using BDD library in Scala:
class MakeNumberSpec extends FlatSpec with ShouldMatchers { "Make Number" should "return all expressions that make a number" in { val xs = (1 to 9).toList solutions(xs, 100).map(displayE(_)) should equal( List("1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9", "1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9", "1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9", "12 + 3 * 4 + 5 + 6 + 7 * 8 + 9", "1 + 2 * 3 + 4 + 5 + 67 + 8 + 9", "1 * 2 + 34 + 5 + 6 * 7 + 8 + 9", "12 + 34 + 5 * 6 + 7 + 8 + 9")) }
}
The complete solution described in this blog is available at my github here.
Let's first define the expression, term, and factor. A factor is a list of digit, like List(1, 2) is interpreted as 12. Then, term is a multiplication of factors, like 4 * 15, and expression is sum of terms.
It might be tempted to introduce class Expression, Term, or Factor. But I prefer to make the solution simple by using type alias instead:
type Factor = List[Int] type Term = List[Factor] type Expr = List[Term]
To display factor, term, and expression, I introduced displayF, displayT, and displayE as follow:
def displayF(f: Factor) = f.reduceLeft(10 * _ + _).toString
def displayT(t: Term) = t.map(displayF(_)).mkString(" * ")
def displayE(e: Expr) = e.map(displayT(_)).mkString(" + ")
Let's test first the displayE method:
scala> displayE(List(List(List(1), List(2), List(3)), List(List(4)), List(List(5)), List(List(6)), List(List(7)), List(List(8), List(9))))
1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9
The book (Bird, 2010) provides an excellent theory of the solution described here. I will try to be more practical here.
The problem can be attacked by exhaustive search, which means for each two consecutive number, either we add '+', '*' or simply concatenating the numbers.
For example, for 8 and 9 we can have 89 by concatenation, 8 + 9 by summation, and 8 * 9 by multiplication. Given the description of the problem, there will be then 3n expression candidates to evaluate. For the problem of make century here, it is not that big, only 38 = 6561 candidates.
To do the exhaustive search, we need the following function that expands an expression to a list of expressions when a number is introduced to the list of candidates so far. Three possibilities: concatenating, summing, and multiplying. The code is (with xs is the factor, xss is the term, and xsss is the rest of the expression).
case (xs::xss):: xsss => List( ((x::xs)::xss)::xsss, // concatenating List(x) :: xs::xss) :: xsss, // multiplying ( List(List(x)) :: (xs::xss):: xsss)) // sum
We need of course to take into account the basic case, which is inserting to an empty expression. The empty expression itself is List(List(Nil)) . The complete function becomes:
def glue(expr: Expr, x: Int) : List[Expr]= expr match { case (Nil::Nil)::Nil => List(List(List(List(x)))) case (xs::xss):: xsss => List( ((x::xs)::xss)::xsss, (List(x) :: xs::xss) :: xsss, ( List(List(x)) :: (xs::xss):: xsss)) case _ => Nil // or throw IllegalArgumentException ? }
Let's do some tests:
scala> glue(List(List(Nil)), 9).map(displayE(_)) res3: List[String] = List(9) scala> glue( List(List(List(9))), 2).map(displayE(_)) res4: List[String] = List(29, 2 * 9, 2 + 9) scala> glue( List(List(List(2), List(9))), 1).map(displayE(_)) res5: List[String] = List(12 * 9, 1 * 2 * 9, 1 + 2 * 9)
The exhaustive solution can then be implemented by continuously applying the glue for each insertion of new number taken into account. This is done by using foldRight of flatMap functions. Then, of course we filter only the one that makes the number to be kept. The following is the code that executes the exhaustive search:
def valueF(f: Factor) = f.reduceLeft(10 * _ + _) def valueT(t: Term) = t.foldLeft(1)( _ * valueF(_)) def valueE(e: Expr) = e.foldLeft(0)(_ + valueT(_))
val emptyExpression: Expr = List(List(Nil)) def solutions(xs: List[Int], n: Int): List[Expr] = { def good(exp: Expr) = valueE(exp) == n xs.foldRight(List(emptyExpression))( (x, ys) => ys.flatMap(glue(_,x))). filter(good) }
The code can be optimized using a simple enhancement, that is, by using an ok method that has the property good(candidate) => ok(candidate). In this case, we can use ok definition as follow:
def ok(exp: Expr) = valueE(exp) <= n
and use it as the the filter of the glue operation. The implementation of solutions method becomes:
def solutions(xs: List[Int], n: Int): List[Expr] = { def ok(exp: Expr) = valueE(exp) <= n def good(exp: Expr) = valueE(exp) == n xs.foldRight(List(emptyExpression))( (x, ys) => ys.flatMap(glue(_,x).filter(ok))).filter(good)
} The solution above can still be optimized by observing that value method executes the same expressions several times. To avoid recalculation, we propagate the last factor, term, and expression.
The following is the improved code, a little bit obscure, I admit.
First, the factor, term, and expression is represented by Intermediate class:
case class Intermediate(k: Int, f: Int, t: Int, e: Int) { def value = f * t + e }
And, finally the modified glue and solution:
def glue(expr: Expr, x: Int, im: Intermediate):
List[(Expr,Intermediate)]= {
expr match {
case (Nil::Nil)::Nil =>
val exp = List(List(List(x)))
List( (exp, Intermediate(10, x, 1, 0)) )
case (xs::xss):: xsss =>
List( ( ((x::xs)::xss)::xsss,
Intermediate(10*im.k, im.k * x + im.f , im.t, im.e)),
( (List(x) :: xs::xss) :: xsss,
Intermediate(10, x, im.f * im.t, im.e)),
( (List(List(x)) :: (xs::xss):: xsss),
Intermediate(10, x, 1, im.f*im.t + im.e)))
case _ => Nil
}
}def solutions(xs: List[Int], n: Int): List[Expr] = {
def ok(exp: (Expr, Intermediate)) = exp._2.value <= n def good(exp: (Expr, Intermediate)) = exp._2.value == n xs.foldRight(List( (emptyExpression, Intermediate(0,0,0,0))))( (x: Int, ys: List[(Expr, Intermediate)]) => ys.flatMap( y => glue(y._1, x, y._2).filter(ok))). filter(good).unzip._1 }
Reference
Bird R(2010), Pearls of Functional Algorithm Design. Cambridge University Press.
No comments:
Post a Comment