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 + 10*b + c= 10*d

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

#
100*x + 10*y + 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