Velocity Reviews > Ruby > [QUIZ] Verbal Arithmetic (#128)

# [QUIZ] Verbal Arithmetic (#128)

Eric I.
Guest
Posts: n/a

 06-17-2007
This program solves addition problems with any number of terms. It
finds and displays all solutions to the problem.

The solving process is broken up into a sequence of simple steps all
derived from class Step. A Step can be something such as 1) choosing
an available digit for a given letter or 2) summing up a column and
seeing if the result matches an already-assigned letter. As steps
succeed the process continues with the following steps. But if a step
fails (i.e., there's a contradiction) then the system backs up to a
point where another choice can be made. This is handled by recursing
through the sequence of steps. In fact, even when a solution is
found, the program still backtracks to find other solutions.

The expectation is that by testing for contradictions as early as
possible in the process we'll tend to avoid dead ends and the result
will be much better than an exhaustive search.

For example, here are the steps for a sample equation:

send
+more
-----
money

1. Choose a digit for "d".
2. Choose a digit for "e".
3. Sum the column using letters "d", "e" (and include carry).
4. Set the digit for "y" based on last column summed.
5. Choose a digit for "n".
6. Choose a digit for "r".
7. Sum the column using letters "n", "r" (and include carry).
8. Verify that last column summed matches current digit for "e".
9. Choose a digit for "o".
10. Sum the column using letters "e", "o" (and include carry).
11. Verify that last column summed matches current digit for "n".
12. Choose a digit for "s".
13. Verify that "s" has not been assigned to zero.
14. Choose a digit for "m".
15. Verify that "m" has not been assigned to zero.
16. Sum the column using letters "s", "m" (and include carry).
17. Verify that last column summed matches current digit for "o".
18. Sum the column using letters (and include carry).
19. Verify that last column summed matches current digit for "m".
20. Display a solution (provided carry is zero)!

Eric
----
Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://LearnRuby.com

====

# This is a solution to Ruby Quiz #128. As input it takes a "word
# equation" such as "send+more=money" and determines all possible
# mappings of letters to digits that yield a correct result.
#
# The constraints are: 1) a given digit can only be mapped to a single
# letter, 2) the first digit in any term cannot be zero.
#
# The solving process is broken up into a sequence of simple steps all
# derived from class Step. A Step can be something such as 1)
# choosing an available digit for a given letter or 2) summing up a
# column and seeing if the result matches an already-assigned letter.
# As steps succeed the process continues with the following steps.
# But if a step fails (i.e., there's a contradiction) then the system
# backs up to a point where another choice can be made. This is
# handled by recursing through the sequence of steps. In fact, even
# when a solution is found, the program still backtracks to find other
# solutions.

require 'set'

# State represents the stage of a partially solved word equation. It
# keeps track of what digits letters map to, which digits have not yet
# been assigned to letters, and the results of the last summed column,
# including the resulting digit and any carry if there is one.
class State
attr_accessor :sum, :carry

def initialize()
@available_digits = Set.new(0..9)
@letters = Hash.new
@sum, @carry = 0, 0
end

# Return digit for letter.
def [](letter)
@letters[letter]
end

# The the digit for a letter.
def []=(letter, digit)
# if the letter is currently assigned, return its digit to the
# available set
@available_digits.add @letters[letter] if @letters[letter]

@letters[letter] = digit
@available_digits.delete digit
end

# Clear the digit for a letter.
def clear(letter)
@letters[letter] = nil
end

# Return the available digits as an array copied from the set.
def available_digits
@available_digits.to_a
end

# Tests whether a given digit is still available.
def available?(digit)
@available_digits.member? digit
end

# Receives the total for a column and keeps track of it as the
# summed-to digit and any carry.
def column_total=(total)
@sum = total % 10
@carry = total / 10
end
end

# Step is an "abstract" base level class from which all the "concrete"
# steps can be deriveds. It simply handles the storage of the next
# step in the sequence. Subclasses should provide 1) a to_s method to
# describe the step being performed and 2) a perform method to
# actually perform the step.
class Step
attr_writer :next_step
end

# This step tries assigning each available digit to a given letter and
# continuing from there.
class ChooseStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Choose a digit for \"#{@letter}\"."
end

def perform(state)
state.available_digits.each do |v|
state[@letter] = v
@next_step.perform(state)
end
state.clear(@letter)
end
end

# This step sums up the given letters and changes to state to reflect
# the sum. Because we may have to backtrack, it stores the previous
# saved sum and carry for later restoration.
class SumColumnStep < Step
def initialize(letters)
@letters = letters
end

def to_s
list = @letters.map { |l| "\"#{l}\"" }.join(', ')
"Sum the column using letters #{list} (and include carry)."
end

def perform(state)
# save sum and carry
saved_sum, saved_carry = state.sum, state.carry

state.column_total =
state.carry +
@letters.inject(0) { |sum, letter| sum + state[letter] }
@next_step.perform(state)

# restore sum and carry
state.sum, state.carry = saved_sum, saved_carry
end
end

# This step determines the digit for a letter given the last column
# summed. If the digit is not available, then we cannot continue.
class AssignOnSumStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Set the digit for \"#{@letter}\" based on last column summed."
end

def perform(state)
if state.available? state.sum
state[@letter] = state.sum
@next_step.perform(state)
state.clear(@letter)
end
end
end

# This step will occur after a column is summed, and the result must
# match a letter that's already been assigned.
class CheckOnSumStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Verify that last column summed matches current " +
"digit for \"#{@letter}\"."
end

def perform(state)
@next_step.perform(state) if state[@letter] == state.sum
end
end

# This step will occur after a letter is assigned to a digit if the
# letter is not allowed to be a zero, because one or more terms begins
# with that letter.
class CheckNotZeroStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Verify that \"#{@letter}\" has not been assigned to zero."
end

def perform(state)
@next_step.perform(state) unless state[@letter] == 0
end
end

# This step represents finishing the equation. The carry must be zero
# for the perform to have found an actual result, so check that and
# display a digit -> letter conversion table and dispaly the equation
# with the digits substituted in for the letters.
class FinishStep < Step
def initialize(equation)
@equation = equation
end

def to_s
"Display a solution (provided carry is zero)!"
end

def perform(state)
# we're supposedly done, so there can't be anything left in carry
return unless state.carry == 0

# display a letter to digit table on a single line
table = state.letters.invert
puts
puts table.keys.sort.map { |k| "#{table[k]}=#{k}" }.join(' ')

# display the equation with digits substituted for the letters
equation = @equation.dup
state.letters.each { |k, v| equation.gsub!(k, v.to_s) }
puts
puts equation
end
end

# Do a basic test for the command-line arguments validity.
unless ARGV[0] =~ Regexp.new('^[a-z]+(\+[a-z]+)*=[a-z]+\$')
STDERR.puts "invalid argument"
exit 1
end

# Split the command-line argument into terms and figure out how many
# columns we're dealing with.
terms = ARGV[0].split(/\+|=/)
column_count = terms.map { |e| e.size }.max

# Build the display of the equation a line at a time. The line
# containing the final term of the sum has to have room for the plus
# sign.
display_columns = [column_count, terms[-2].size + 1].max
display = []
terms[0..-3].each do |term|
display << term.rjust(display_columns)
end
display << "+" + terms[-2].rjust(display_columns - 1)
display << "-" * display_columns
display << terms[-1].rjust(display_columns)
display = display.join("\n")
puts display

# AssignOnSumStep which letters cannot be zero since they're the first
# letter of a term.
nonzero_letters = Set.new
terms.each { |e| nonzero_letters.add(e[0, 1]) }

# A place to keep track of which letters have so-far been assigned.
chosen_letters = Set.new

# Build up the steps needed to solve the equation.
steps = []
column_count.times do |column|
index = -column - 1
letters = [] # letters for this column to be added

terms[0..-2].each do |term| # for each term that's being added...
letter = term[index, 1]
next if letter.nil? # skip term if no letter in column
letters << letter # note that this letter is part of sum

# if the letter does not have a digit, create a ChooseStep
unless chosen_letters.member? letter
steps << ChooseStep.new(letter)
steps << CheckNotZeroStep.new(letter) if
nonzero_letters.member? letter
end
end

# create a SumColumnStep for the column
steps << SumColumnStep.new(letters)

summed_letter = terms[-1][index, 1] # the letter being summed to

# check whether the summed to letter should already have a digit
if chosen_letters.member? summed_letter
# should already have a digit, check that summed digit matches it
steps << CheckOnSumStep.new(summed_letter)
else
# doesn't already have digit, so create a AssignOnSumStep for
# letter
steps << AssignOnSumStep.new(summed_letter)

# check whether this letter cannot be zero and if so add a
# CheckNotZeroStep
steps << CheckNotZeroStep.new(summed_letter) if
nonzero_letters.member? summed_letter
end
end

# should be done, so add a FinishStep
steps << FinishStep.new(display)

# print out all the steps
# steps.each_with_index { |step, i| puts "#{i + 1}. #{step}" }

# let each step know about the one that follows it.
steps.each_with_index { |step, i| step.next_step = steps[i + 1] }

# start performing with the first step.
steps.first.perform(State.new)

Morton Goldberg
Guest
Posts: n/a

 06-18-2007
Here is my solution for Ruby Quiz 128. It's a little rough, but I
can't afford to spend any more time working on it. One thing I didn't
have time to do was to provide a user interface. Another thing I
didn't do was proper commenting. I apologize for the latter.

I thought a Darwinian search (aka genetic algorithm) would be an
interesting way to tackle this quiz. I have been looking for a excuse
to write such a search in Ruby for quite awhile and this seemed to be
it.

Here are is the output from one run of my quiz solution:

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

Solution found after 27 steps
FORTY+TEN+TEN=SIXTY
29786+850+850=31486
</result>

And here is the code:

<code>
#! /usr/bin/env ruby -w
#
# solution.rb
# Quiz 128
#
# Created by Morton Goldberg 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
</code>

And here are the library classes:

<code>
# lib/cryptarithm.rb
# Quiz 128
#
# Created by Morton Goldberg 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 ((E-Mail Removed)).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 }
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
</code>

<code>
# lib/solver.rb
# Quiz 128
#
# Created by Morton Goldberg 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, opulation, :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.rank.zero?
@step += 1
end
@best
end
def replicate
@pop_size.times do |n|
crypt = @population[n]
# mate = crypt
# while mate.equal?(crypt)
# mate = @population[rand(@pop_size)]
# end
@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
</code>

Regards, Morton

Eric I.
Guest
Posts: n/a

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

* http://www.gtoal.com/wordgames/alphametic/testscript

* http://www.gtoal.com/wordgames/alpha...testscript.out

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.

James Edward Gray II
Guest
Posts: n/a

 06-18-2007
On Jun 17, 2007, at 9:03 AM, Raf Coremans wrote:

> Here's my solution: http://pastie.caboo.se/71188
>
> 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 Gray II

Morton Goldberg
Guest
Posts: n/a

 06-19-2007
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:

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

Solution found after 27 steps
FORTY+TEN+TEN=SIXTY
29786+850+850=31486
</result>

And here is the corrected code:

<code>
#! /usr/bin/env ruby -w
#
# solution.rb
# Quiz 128
#
# Created by Morton Goldberg 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
</code>

And here are the library classes:

<code>
# lib/cryptarithm.rb
# Quiz 128
#
# Created by Morton Goldberg 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 ((E-Mail Removed)).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
</code>

<code>
# lib/solver.rb
# Quiz 128
#
# Created by Morton Goldberg 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, opulation, :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
</code>

Regards, Morton

Eugene Kalenkovich
Guest
Posts: n/a

 06-19-2007
On Jun 18, 4:59 pm, James Edward Gray II <(E-Mail Removed)>
wrote:
>> 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__
>

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

James Edward Gray II
Guest
Posts: n/a

 06-19-2007
On Jun 19, 2007, at 9:30 AM, Eugene Kalenkovich wrote:

> On Jun 18, 4:59 pm, James Edward Gray II <(E-Mail Removed)>
> wrote:
>>> 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__
>>

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

Thanks. There have been far more clever submissions though.

> The only thing, assuming that all examples are always integers, I'd
>
> .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

Good points.

James Edward Gray II

Andreas Launila
Guest
Posts: n/a

 06-19-2007
Ruby Quiz 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
+ 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'

# Solves verbal arithmetic problems
# ( http://en.wikipedia.org/wiki/Verbal_arithmetic ). Only supports
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
[4] http://www.gecode.org/gecode-doc-latest/PageComp.html

--
Andreas Launila

Andreas Launila
Guest
Posts: n/a

 06-19-2007
Andreas Launila 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).

--
Andreas Launila

Bob Showalter
Guest
Posts: n/a

 06-20-2007
On 6/15/07, Ruby Quiz <(E-Mail Removed)> 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: http://pastie.caboo.se/72030

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