Ruby Q. wrote:
This week’s quiz is to build a program that reads in equations and outputs
solutions. You can decide how complex of an equation you want to support, with
the examples above being the minimum implementation.
This solution requires Gecode/R[1] 0.2.0 (need to install Gecode[3,4]
followed by Gecode/R[2]). Gecode does the actual search, so we just
specify the constraints. Two important aspects that are used to make the
solution quick to compute are:
== Propagation rather than branching (deduction rather than exploration)
Branching (i.e. testing a guess, i.e. exploring the search space) costs
since we have to save the old state and start a new one. Rather Gecode
tries to prune as much of the search space as it can before resorting to
exploration. In the case of linear constraints (e.g. a + 10b + c= 10d
de
) it takes each variable and considers the smallest and largest values
it can possibly take. E.g. if we consider a in the above example we can
rewrite the linear equation to
a = 10*(d - b) + e - c
From that equation we can check how large and small the right hand side
can be and then remove all other possibilities from the domain of a. We
can end up pruning quite a lot if we do this for each variable until
there are no more possibilities left to remove (coupled with the
distinct constraint).
In fact when we use this for send+more=money, without doing any sort of
exploration we can directly reduce the domains of the variables down to
s=9, e=4…7, n=5…8, d=2…8, m=1, o=0, r=2…8, y=2…8
So without any guessing at all we already know the value of three
letters and have pruned the domains of the others (i.e. pruned the
number of possibilities left, i.e. reduced the search space).
Since we now have to start exploring the search space we make a guess
that e=4. Propagating the constraints once again with e given the domain
4 will directly result in a failure, so we backtrack and now know that
e!=4. With that information we redo the propagation and directly end up
at the solution with no need to explore any further. So in total we only
need to explore 4 out of 9^2*10^6 nodes in the search space.
== Branching with a good heuristic
We don’t randomly select where to go next in the search space, rather we
use a fail-first heuristic to try to cut down the search space faster.
The heuristic is to simply try to fixate a value for the variable with
the smallest domain. The reason that it works well is that we exhaust
domains quicker, hence forcing failures quicker (hence fail-first)
== The code
require ‘rubygems’
require ‘gecoder’
Solves verbal arithmetic problems
addition.
class VerbalArithmetic < Gecode::Model
Creates a model for the problem where the left and right hand sides
are given as an array with one element per term. The terms are given
as strings
def initialize(lhs_terms, rhs_terms)
super()
# Set up the variables needed as a hash mapping the letter to its
# variable.
lhs_terms.map!{ |term| term.split(//) }
rhs_terms.map!{ |term| term.split(//) }
all_terms = (lhs_terms + rhs_terms)
unique_letters = all_terms.flatten.uniq
letter_vars = int_var_array(unique_letters.size, 0..9)
@letters = Hash[*unique_letters.zip(letter_vars).flatten!]
# Must satisfy the equation.
sum_terms(lhs_terms).must == sum_terms(rhs_terms)
# Must be distinct.
letter_vars.must_be.distinct
# Must not begin with a 0.
all_terms.map{ |term| term.first }.uniq.each do |letter|
@letters[letter].must_not == 0
end
# Select a branching, we go for fail first.
branch_on letter_vars, :variable => :smallest_size, :value => :min
end
def to_s
@letters.map{ |letter, var| “#{letter}: #{var.val}” }.join(“\n”)
end
private
A helper to make the linear equation a bit tidier. Takes an array of
variables and computes the linear combination as if the variable
were digits in a base 10 number. E.g. x,y,z becomes
100x + 10y + z .
def equation_row(variables)
variables.inject{ |result, variable| variable + result*10 }
end
Computes the sum of the specified terms (given as an array of arrays
of characters).
def sum_terms(terms)
rows = terms.map{ |term| equation_row(@letters.values_at(*term)) }
rows.inject{ |sum, term| sum + term }
end
end
if ARGV.empty?
abort “Usage: #{$0} ‘<word_1>+<word_2>+…+<word_n>=<word_res>’”
end
lhs, rhs = ARGV[0].split(‘=’).map{ |eq_side| eq_side.split(‘+’) }
solution = VerbalArithmetic.new(lhs, rhs).solve!
if solution.nil?
puts ‘Failed’
else
puts solution.to_s
end
[1] http://gecoder.rubyforge.org/
[2] http://gecoder.rubyforge.org/installation.html
[3] GECODE download
[4] http://www.gecode.org/gecode-doc-latest/PageComp.html