# Verbal Arithmetic (#128)

If anyone would like more samples to try their code with, I found the
following on the web:

The first is a script which poses the problems to their own solving-
program. The second shows the solutions that their program produces.

Some of the sample equations have multiple solutions, such as ‘eins
+eins=zwei’. ‘united+states=america’ has no solutions. And of the
few that I’ve tested with my own solution, ‘saturn+pluto+uranus
+neptune=planets’ takes the longest to solve.

## Eric

Interested in hands-on, on-site Ruby training? See http://LearnRuby.com
for information about a well-reviewed class.

On Jun 17, 2007, at 9:03 AM, Raf C. wrote:

Here’s my solution: Parked at Loopia

It’s of the dumb-brute-force-slow-as-hell variety:

Mine was too:

#!/usr/bin/env ruby -wKU

EQUATION = ARGV.shift.to_s.downcase.sub(“=”, “==”)
LETTERS = EQUATION.scan(/[a-z]/).uniq
CHOICES = LETTERS.inject(Hash.new) do |all, letter|
all.merge(letter => EQUATION =~ /\b#{letter}/ ? 1…9 : 0…9)
end

def search(choices, mapping = Hash.new)
if choices.empty?
letters, digits = mapping.to_a.flatten.partition { |e| e.is_a?
String }
return mapping if eval(EQUATION.tr(letters.join, digits.join))
else
new_choices = choices.dup
letter = new_choices.keys.first
digits = new_choices.delete(letter).to_a - mapping.values

`````` digits.each do |choice|
if result = search(new_choices, mapping.merge(letter => choice))
return result
end
end

return nil
``````

end
end

if solution = search(CHOICES)
LETTERS.each { |letter| puts “#{letter}: #{solution[letter]}” }
else
puts “No solution found.”
end

END

James Edward G. II

On Jun 18, 4:59 pm, James Edward G. II [email protected]
wrote:

def search(choices, mapping = Hash.new)
if result = search(new_choices, mapping.merge(letter => choice))
else
puts “No solution found.”
end

END

I really like it - your solution covers any type of expression :).
Perhaps some preprocessing of CHOICES can save the performance…

The only thing, assuming that all examples are always integers, I’d add

.sub(/([a-z])([^a-z])/,‘\1.0\2’)

to EQUATION to cover examples with division (to drop the assumption,
before
adding .0 one can regexp it for '.'s)

for ‘boaogr/foo=bar’ (arbitrary example) your code gives

b: 1
o: 0
a: 2
g: 3
r: 7
f: 8

and modified one corrects it to

b: 1
o: 0
a: 2
g: 3
r: 7
f: 8

I can expect that this modification may break on rounding errors, but in
this task domain I do not think it will

Sorry for the second post, but I just noticed that I pasted a wrong
(earlier) version of solver.rb into my first post. This is what I
intended to post.

The difference between the two versions is minor, but this version
eliminates some commented-out experimental code and corrects a minor
bug.

Sample output:

Solution found after 15 steps SEND+MORE=MONEY 9567+1085=10652

Solution found after 27 steps
FORTY+TEN+TEN=SIXTY
29786+850+850=31486

And here is the corrected code:

``` #! /usr/bin/env ruby -w # # solution.rb # Quiz 128 # # Created by Morton G. on 2007-06-18. Assumption: equations take the form: term + term + … term = sum ROOT_DIR = File.dirname(FILE) \$LOAD_PATH << File.join(ROOT_DIR, “lib”) require “cryptarithm” require “solver” EQUATION_1 = “SEND+MORE=MONEY” EQUATION_2 = “FORTY+TEN+TEN=SIXTY” POP_SIZE = 400 FECUNDITY = 2 STEPS = 50 Cryptarithm.equation(EQUATION_1) s = Solver.new(POP_SIZE, FECUNDITY, STEPS) s.run puts s.show Cryptarithm.equation(EQUATION_2) s = Solver.new(POP_SIZE, FECUNDITY, STEPS) s.run puts s.show ```

And here are the library classes:

``` # lib/cryptarithm.rb # Quiz 128 # # Created by Morton G. on 2007-06-18. DIGITS = (0…9).to_a class Cryptarithm @@equation = “” @@max_rank = -1 def self.equation(str=nil) if str @@equation = str.upcase lhs, rhs = @@equation.gsub(/[A-Z]/, “9”).split("=") @@max_rank = [eval(lhs), eval(rhs)].max else @@equation end end attr_accessor :ranking, :solution def initialize @solution = @@equation.delete(“±=”).split("").uniq @solution = @solution.zip((DIGITS.sort_by {rand})[0, @solution.size]) rank end def mutate(where=rand(@solution.size)) raise RangeError unless ([email protected]).include?(where) digits = @solution.collect { |pair| pair[1] } digits = DIGITS - digits return if digits.empty? @solution[where][1] = digits[rand(digits.size)] end def swap m = rand(@solution.size) n = m while n == m n = rand(@solution.size) end @solution[m][1], @solution[n][1] = @solution[n][1], @solution [m][1] end def rank sum = @@equation.dup solution.each { |chr, num| sum.gsub!(chr, num.to_s) } lhs, rhs = sum.split("=") terms = lhs.split("+") << rhs if terms.any? { |t| t[0] == ?0 } @ranking = @@max_rank else @ranking = eval("#{lhs} - #{rhs}").abs end end def initialize_copy(original) @solution = original.solution.collect { |pair| pair.dup } rank end def inspect [@ranking, @solution].inspect end def to_s sum = @@equation.dup solution.each { |chr, num| sum.gsub!(chr, num.to_s) } “#{@@equation}\n#{sum}” end end ``` ``` # lib/solver.rb # Quiz 128 # # Created by Morton G. on 2007-06-18. # # Attempts to a solve cryptarithm puzzle by applying a Darwinian search # (aka genetic algorithm). It can thought of as a stochastic breadth- first # search. Although this method doesn't guarantee a solution will be # found, it often finds one quite quickly. MUTATION = 0.5 SWAP = 1.0 class Solver attr_reader :best, :population, :step def initialize(pop_size, fecundity, steps) @pop_size = pop_size @fecundity = fecundity @steps = steps @mid_step = steps / 2 @step = 1 @population = [] @pop_size.times { @population << Cryptarithm.new } select end def run @steps.times do replicate select break if @best.ranking.zero? @step += 1 end @best end def replicate @pop_size.times do |n| crypt = @population[n] @fecundity.times do child = crypt.dup child.mutate if crypt.solution.size < 10 && rand <= MUTATION child.swap if rand <= SWAP @population << child end end end def select @population = @population.sort_by { |crypt| crypt.rank } @population = @population[0, @pop_size] @best = @population.first end def show if @step > @steps “No solution found after #{step} steps” else “Solution found after #{step} steps\n” + @best.to_s end end end ```

Regards, Morton

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

• e, which corresponds to the problem

a

• bc

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’

# ( Verbal arithmetic - Wikipedia ). Only supports

class VerbalArithmetic < Gecode::Model

# 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

# 100x + 10y + z .

def equation_row(variables)
variables.inject{ |result, variable| variable + result*10 }
end

# 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

On Jun 19, 2007, at 9:30 AM, Eugene K. wrote:

end

Perhaps some preprocessing of CHOICES can save the performance…
Thanks. There have been far more clever submissions though.

o: 0
a: 2
g: 3
r: 7
f: 8

I can expect that this modification may break on rounding errors,
but in
this task domain I do not think it will

Good points.

James Edward G. II

Andreas L. wrote:

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.

The last part is probably a bit misleading/incorrect. We are not
directly exploring the space of all possible assignments when we branch,
so saying that we have explored 4 nodes in that space is incorrect (i.e.
we have not just explored 4 possible assignments, but we have visited
just 4 nodes in our search space).

On 6/15/07, Ruby Q. [email protected] 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.

Here’s my solution: Parked at Loopia

It’s a brute-force search, but has reasonable speed. +, -, and *
operators are supported.

Andreas L. wrote:

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.

I forgot a node in the middle there (since there are 4 nodes). The
complete search is:

1. Root: s=9, e=4…7, n=5…8, d=2…8, m=1, o=0, r=2…8, y=2…8
2. Tries e = 4: fails.
3. Knows e != 4: s=9, e=5…7, n=6…8, d=2…8, m=1, o=0, r=2…8, y=2…8
4. Tries e = 5: s=9, e=5, n=6, d=7, m=1, o=0, r=8, y=2 (success)