# Verbal Arithmetic (#128)

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

A famous set of computer problems involve verbal arithmetic. In these
problems,
you are given equations of words like:

``````send
``````
• more

money

or:

``````forty
ten
``````
• ten

``````sixty
``````

The goal is to find a single digit for each letter that makes the
equation true.
Normal rules of number construction apply, so the first digit of a
multi-digit
number should be nonzero and each letter represents a different digit.

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 a solution you can test against:

\$ ruby verbal_arithmetic.rb ‘send+more=money’
s: 9
e: 5
n: 6
d: 7
m: 1
o: 0
r: 8
y: 2

I really don’t get it How did you figured out that 2 = y in your
example?

y: 2

greets

``````                 one must still have chaos in oneself to be able to
``````

give birth to a dancing star

On Jun 15, 2007, at 7:55 AM, anansi wrote:

I really don’t get it How did you figured out that 2 = y in your
example?

Well, a non-clever way is to try an exhaustive search of each digit
for each letter.

James Edward G. II

anansi wrote, On 6/15/2007 8:10 AM:

ohh I totally misunderstood the task here… I thought the input would
be send+more and my app should give money as answer trough calculation…

For perhaps a reason to change the wording, that’s what I thought as
well until I read the explanation to anansi’s question.

Sam

ohh I totally misunderstood the task here… I thought the input would be
send+more and my app should give money as answer trough calculation…

James Edward G. II wrote:

On Jun 15, 2007, at 7:55 AM, anansi wrote:

I really don’t get it How did you figured out that 2 = y in your
example?

Well, a non-clever way is to try an exhaustive search of each digit for
each letter.

James Edward G. II

greets

``````                 one must still have chaos in oneself to be able to
``````

give birth to a dancing star

On Jun 15, 2007, at 8:17 AM, Sammy L. wrote:

anansi wrote, On 6/15/2007 8:10 AM:

ohh I totally misunderstood the task here… I thought the input
would be send+more and my app should give money as answer trough
calculation…

For perhaps a reason to change the wording, that’s what I thought
as well until I read the explanation to anansi’s question.

Sorry for the confusion folks. You get both sides of the equation
and are expected to fine the digit to represent each letter.

James Edward G. II

Hmm maybe this helps to clarify (for emacs users) the problem is like
mpuzz (mpuz?)

Robert

I hate these puzzles, but to clarify what you want to do:

## send +more

money

using the key becomes: s: 9 e: 5 n: 6 d: 7 m: 1 o: 0 r: 8 y: 2

9567

• 1085

10652

Jason

Mi implementation is “working”. For instance:

./quiz_128.rb “a+b=c”
a: 5
b: 1
c: 6

But
./quiz_128.rb “send+more=money” is taking ages!

time ./quiz_128.rb “send+more=money”
m: 1
y: 2
n: 6
o: 0
d: 7
e: 5
r: 8
s: 9

real 7m17.065s
user 2m46.806s
sys 0m6.676s

Is there some trick to cut the solution space (I’m just scanning the
solution space) ? I know I have a crappy PC but I have a feeling that
this is not the real problem! When can I send my solution to be
reviewed?

``````    + more

\$ ruby verbal_arithmetic.rb 'send+more=money'
s: 9
e: 5
n: 6
d: 7
m: 1
o: 0
r: 8
y: 2
``````

sentido de unidad es fÃ¡cil pensar en la recomposiciÃ³n del ser
unidad, permitirÃ¡ inspirar para elevarnos por encima de la miseria que
la antinomia nos ha planteado, para dejar, de una vez por todas, ese
ser “anti” y ser, de una vez por todas, “pro”: “Pro argentinos””

Jorge Rafael Videla para el 25 de mayo de 1976

quoth the Aureliano C.:

When can I send my solution to be
reviewed?

I think about 12 hours from now…

-d

Jason,

``````Just think of these as a cryptogram with numbers instead of letters.

- Warren B.``````

Hi,

Here’s my solution: http://pastie.caboo.se/71188

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

\$ time ./rq128_verbalarithmetic_rafc.rb ‘send + more = money’
{“m”=>1, “y”=>2, “n”=>6, “o”=>0, “d”=>7, “e”=>5, “r”=>8, “s”=>9}

real 2m51.197s
user 2m39.722s
sys 0m11.397s

\$ time ./rq128_verbalarithmetic_rafc.rb ‘forty + ten + ten = sixty’
{“x”=>4, “n”=>0, “y”=>6, “o”=>9, “e”=>5, “f”=>2, “r”=>7, “s”=>3, “i”=>1,
“t”=>8}

real 7m28.151s
user 6m55.114s
sys 0m32.938s

But on the other hand, it can handle any operator as well as bases other
than 10. Did you know for instance that in base 9, ruby is worth up to 4
perls with some extra fun thrown in?

\$ ./rq128_verbalarithmetic_rafc.rb ‘n * perl + fun = ruby’ 9
{“l”=>8, “b”=>7, “y”=>0, “n”=>1, “e”=>5, “p”=>3, “f”=>6, “r”=>4, “u”=>2}
{“l”=>8, “b”=>7, “y”=>0, “n”=>1, “e”=>6, “p”=>3, “f”=>5, “r”=>4, “u”=>2}
{“l”=>1, “b”=>7, “y”=>4, “n”=>2, “e”=>6, “p”=>3, “f”=>5, “r”=>8, “u”=>0}
{“l”=>2, “b”=>5, “y”=>0, “n”=>3, “e”=>7, “p”=>1, “f”=>8, “r”=>6, “u”=>4}
{“l”=>4, “b”=>5, “y”=>6, “n”=>3, “e”=>0, “p”=>2, “f”=>8, “r”=>7, “u”=>1}
{“l”=>4, “b”=>0, “y”=>6, “n”=>3, “e”=>1, “p”=>2, “f”=>8, “r”=>7, “u”=>5}
{“l”=>4, “b”=>7, “y”=>6, “n”=>3, “e”=>5, “p”=>2, “f”=>1, “r”=>8, “u”=>0}
{“l”=>2, “b”=>6, “y”=>3, “n”=>4, “e”=>7, “p”=>1, “f”=>5, “r”=>8, “u”=>0}

Regards,
Raf

Well, I think I can send it now. My implementation is on
http://pastie.caboo.se/71198.

On 6/16/07, Aureliano C. [email protected] wrote:

time ./quiz_128.rb “send+more=money”
user 2m46.806s

1. Please do not post any solutions or spoiler discussion for this quiz until
if you can.

number should be nonzero and each letter represents a different digit.
n: 6
sentido de unidad es fÃ¡cil pensar en la recomposiciÃ³n del ser
unidad, permitirÃ¡ inspirar para elevarnos por encima de la miseria que
la antinomia nos ha planteado, para dejar, de una vez por todas, ese
ser “anti” y ser, de una vez por todas, “pro”: “Pro argentinos””

Jorge Rafael Videla para el 25 de mayo de 1976

sentido de unidad es fÃ¡cil pensar en la recomposiciÃ³n del ser
unidad, permitirÃ¡ inspirar para elevarnos por encima de la miseria que
la antinomia nos ha planteado, para dejar, de una vez por todas, ese
ser “anti” y ser, de una vez por todas, “pro”: “Pro argentinos””

Jorge Rafael Videla para el 25 de mayo de 1976

Hello,

here is my solution for the arithmetic quiz. I am a ruby beginner and
this
is my first ruby program (ok, my second one, the first was “puts ‘hello
world’”).
So please forgive me the dirty trick using eval (why build an own parser
if
ruby provides such a fine solution?). I build in a brute force search
algorithm
via an iterative method for permutations. Therefore, any valid ruby
expression is allowed, e.g.

verbal_arithmetic.rb 'a+b==c && a+c==d-b && ac==d’
solving a
bcd!=0 && a+b==c && a+c==d-b && a*c==d
– Solution —
a: 2
b: 1
c: 3
d: 6

Regards
Holger

#!/usr/bin/ruby -w

# verbal_arithmetic.rb ‘a+b==c && a+c==d-b && a*c==d’

#*********************************************************************

# perms(m, n) { |x| … }

#*********************************************************************

def perms(m, n)
p = [nil] * m
t = [-1] * m
k = 0
while k >= 0
if k==m
yield p
k = k-1
end
n[t[k]] = p[k] if t[k]>=0
while(t[k]<n.length())
t[k] = t[k]+1
if n[t[k]]
p[k] = n[t[k]]
n[t[k]] = nil
k = k+1
t[k] = -1
break
end
end
k = k-1 if t[k]==n.length()
end
end

# Read from command line and make valid ruby expression (= -> == if not

puzzle = ARGV.gsub(/=+/,"==")

# Extract all letters and all first letters

digits = puzzle.gsub(/\W/,"").split(//).uniq
starts = puzzle.gsub(/(\w)\w*|\W/,"\1").split(//).uniq

if digits.length()>= 10
puts “oops, too much letters”
else

# String containing all digits

digitss = digits.join

# Build “first digit must not be zero” condition

cond0 = starts.join("*") + “!=0”

# And now perform an exhaustive search

puts “solving #{cond0} && #{puzzle}”

perms(digits.length(), (0…10).to_a) { |v|
p0 = cond0.tr(digitss, v.join)
p1 = puzzle.tr(digitss, v.join)
if eval(p0) && eval(p1) # Hint: first evaluate p0 as p1 may not be
a
valid expression
puts ‘-- Solution —’
[digits, v].transpose.each do |x,y| puts “#{x}: #{y}” end
end
}
end

My solution works with addition and multiplication of any sized list of
words,
and subtraction of a list of exactly two words. Its also a fair bit
faster
than brute force. Unfortunately it got pretty messy, and after some
rough
debugging I’m not in the mood to clean it up just now.

I came up with the basic idea by noticing that the equations can be
built
up and checked from simpler equations taken from the right-hand side.
Er…
lemme give an example to explain better:

9567

• 1085

10652

Start off by looking for ways to satisfy:
7

• 5

2

Then move further to the left:

67

• 85

152

The 52 is right, but not the 1. For addition and multiplication, we can
just
take it mod 100, and if that works then its a possible partial solution.
For subtraction of two numbers, though, it doesn’t work when it goes
negative.
The trick in that case is to just mod the left-most digit:

9567

• 1085

8482

7

• 5

2 OK

67

• 85

-22 => 82 (-2 mod 10 = 8)

verbal_arithmetic.rb contains (old, ugly) code for generating
permutations
and combinations. So the program works from right-to-left, finding
partial
solutions that work by going through ways of mapping letters to numbers,
and for each one trying to move further left. Basically a depth-first
search.

There are a number of other subteties, but like I said, I’m tired of
messing
with this now, so I’ll leave it there. Ask if you must.

Examples:

\$ time ./verbal_arithmetic.rb ‘send more’ + money
Found mapping:
m: 1
y: 2
n: 6
o: 0
d: 7
e: 5
r: 8
s: 9

real 0m1.074s
user 0m0.993s
sys 0m0.019s

\$ ./verbal_arithmetic.rb ‘forty ten ten’ + sixty
Found mapping:
x: 4
y: 6
n: 0
o: 9
e: 5
f: 2
r: 7
s: 3
t: 8
i: 1

\$ ./verbal_arithmetic.rb ‘foo bar’ - ‘zag’
Found mapping:
a: 0
b: 3
z: 4
o: 1
f: 7
r: 9
g: 2

\$ ./verbal_arithmetic.rb ‘fo ba’ * ‘wag’
Found mapping:
w: 4
a: 2
b: 1
o: 5
f: 3
g: 0

[Note: this didn’t seem to get through the first time. Apologies if it
did.]

My solution works with addition and multiplication of any sized list of
words,
and subtraction of a list of exactly two words. Its also a fair bit
faster
than brute force. Unfortunately it got pretty messy, and after some
rough
debugging I’m not in the mood to clean it up just now.

I came up with the basic idea by noticing that the equations can be
built
up and checked from simpler equations taken from the right-hand side.
Er…
lemme give an example to explain better:

9567

• 1085

10652

Start off by looking for ways to satisfy:
7

• 5

2

Then move further to the left:

67

• 85

152

The 52 is right, but not the 1. For addition and multiplication, we can
just
take it mod 100, and if that works then its a possible partial solution.
For subtraction of two numbers, though, it doesn’t work when it goes
negative.
The trick in that case is to just mod the left-most digit:

9567

• 1085

8482

7

• 5

2 OK

67

• 85

-22 => 82 (-2 mod 10 = 8)

verbal_arithmetic.rb contains (old, ugly) code for generating
permutations
and combinations. So the program works from right-to-left, finding
partial
solutions that work by going through ways of mapping letters to numbers,
and for each one trying to move further left. Basically a depth-first
search.

There are a number of other subteties, but like I said, I’m tired of
messing
with this now, so I’ll leave it there. Ask if you must.

Examples:

\$ time ./verbal_arithmetic.rb ‘send more’ + money
Found mapping:
m: 1
y: 2
n: 6
o: 0
d: 7
e: 5
r: 8
s: 9

real 0m1.074s
user 0m0.993s
sys 0m0.019s

\$ ./verbal_arithmetic.rb ‘forty ten ten’ + sixty
Found mapping:
x: 4
y: 6
n: 0
o: 9
e: 5
f: 2
r: 7
s: 3
t: 8
i: 1

\$ ./verbal_arithmetic.rb ‘foo bar’ - ‘zag’
Found mapping:
a: 0
b: 3
z: 4
o: 1
f: 7
r: 9
g: 2

\$ ./verbal_arithmetic.rb ‘fo ba’ * ‘wag’
Found mapping:
w: 4
a: 2
b: 1
o: 5
f: 3
g: 0

Hello everyone,

At the outset, I had no idea how difficult this problem would be. In
fact,
it turns out that this is actually an NP-complete problem if the number
base
is not fixed at 10. Anyway… Initially I experimented with a
backtracking
solution, but ran into trouble getting it to work properly. So for now I
am
submitting this solution. Although less than perfect, it does work for
the
test inputs, as well as additional solutions I have tried. The idea is
to
brute force a solution by trying all possible combinations of solutions
until one works.

For this solution, I used the Permutation Gem available here:
http://permutation.rubyforge.org/doc/index.html

require ‘Permutation’

To avoid having to (re)write the combination code myself, I also used
the
Combinations class from:
http://butunclebob.com/ArticleS.UncleBob.RubyCombinations
This is great code, someone really should create a gem for it!

I packaged all of my code inside the following class:

class VerbalArithmetic

the
‘=’ that

# are to be added together) and an rvalue (the single word on the

right-hand side)
def parse_equation (equation)
lvalues = equation.split("+")
rvalue = lvalues[-1].split("=")
lvalues[-1] = rvalue # Get last lvalue
rvalue = rvalue # Get rvalue

``````return lvalues, rvalue
``````

end

# Brute force a solution by trying all possible combinations

def find_solution(lvalues, rvalue)

``````# Form a list of all letters
words.push(rvalue)
letters = {}
words.each do |word|
word.split("").each do |letter|
letters[letter] = letter if letters[letter] == nil
end
end

# Format l/r values to ease solution analysis below
lvalues_formatted = []
lvalues.each {|lval| lvalues_formatted.push(lval.reverse.split(""))}
rvalue_formatted = rvalue.reverse.split("")

# For all unordered combinations of numbers...
for i in Combinations.get(10, letters.values.size)

# For all permutations of each combination...
perm = Permutation.for(i)
perm.each do |p|

# Map each combination of numbers to the underlying letters
map = {}
parry = p.project
for i in 0...letters.size
map[letters.values[i]] = parry[i]
end

# Does this mapping yield a solution?
if is_solution?(lvalues_formatted, rvalue_formatted, map)
return map
end
end
end

nil
``````

end

# substituting the given number for its letters

def is_solution?(lvalues, rvalue, map)

``````# Make sure there are no leading zero's
for lval in lvalues
return false if map[lval[-1]] == 0
end
return false if map[rvalue[-1]] == 0

# Perform arithmetic using the mappings, and make sure they are
``````

valid
remainder = 0
for i in 0…rvalue.size
lvalues.each do |lval|
remainder = remainder + map[lval[i]] if map[lval[i]] != nil #
Sum
values
end

``````  return false if (remainder % 10) != map[rvalue[i]] # Validate
``````

digit
remainder = remainder / 10 # Truncate
value at
this place
end

``````true
``````

end
end

Finally, this code puts everything together:

va = VerbalArithmetic.new
lvalues, rvalue = va.parse_equation(“send+more=money”)
map = va.find_solution(lvalues, rvalue)

puts "Solution: ", map if map != nil

And here is the output:

Solution:
m1n6y2d7o0e5r8s9

Thanks,

Justin

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

====

require ‘set’

# 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

def
@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

``````@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

# summed-to digit and any carry.

def column_total=(total)
@sum = total % 10
@carry = total / 10
end
end

# actually perform the step.

class Step
attr_writer :next_step
end

# 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

# 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

# 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

# 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

# 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

# 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 =~ Regexp.new(’^[a-z]+(+[a-z]+)*=[a-z]+\$’)
STDERR.puts “invalid argument”
exit 1
end

# columns we’re dealing with.

terms = ARGV.split(/+|=/)
column_count = terms.map { |e| e.size }.max

# 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

# 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)

# 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)

#! /usr/bin/env ruby

# Glen Pankow 06/17/07 Original version.

#-----------------------------------------------------------------------------

that

(taking

used

# 0.120u 0.002s 0:00.13 92.3% 0+0k 0+0io 0pf+0w

class Array

``````#
# For each non-nil element of the current array, (destructively) set
``````

it to
# nil (i.e., ‘marking’ it), yield the original value (to the assumed
block),
# and restore it back to what it originally was (i.e., ‘unmarking’
it).
#
# For example, the code:
# array = [ 0, nil, 2, 3 ]
# p “before: array = #{array.inspect}”
# array.unmarkeds { |elem| p “elem = #{elem}, array =
#{array.inspect}” }
# p “after: array = #{array.inspect}”
# would print:
# before: array = [0, nil, 2, 3]
# elem = 0, array = [nil, nil, 2, 3]
# elem = 2, array = [0, nil, nil, 3]
# elem = 3, array = [0, nil, 2, nil]
# after: array = [0, nil, 2, 3]
#
def unmarkeds
(0…size).each do |i|
next if (at(i).nil?)
elem = at(i) ; self[i] = nil
yield elem
self[i] = elem
end
end

``````#
# If the <i>-th element of the current array is nil, do nothing.
``````

Otherwise
# (destructively) set it to nil (i.e., ‘marking’ it), yield (to the
assumed
# block), and restore it back to what it originally was (i.e.,
‘unmarking’
# it). This is basically the guts of unmarkeds(), and is provided
for safe
# manual element marking.
#
def if_unmarked(i)
return if (at(i).nil?)
elem = at(i) ; self[i] = nil
yield
self[i] = elem
end

``````#
# Note:  typically one might say 'yield elem, self' in these
``````

methods, but
# I don’t need them for this application due to Ruby’s scoping
mechanism.
#
end

# Process the command-line arguments of addend strings and the sum

string.

verbose = false
ARGV.each do |arg|
if (arg == ‘-v’)
verbose = true
else
arg.split(/[\s+=]+/).each { |term| addend_strs << term }
end
end

code to

# eventually print out a nice table of the addition.

table_print_code = ‘print " ’
(sum_str.length - 1).downto(1) do |i|
table_print_code << " #{carry#{i}}"
end
table_print_code << “\n”\n"
first_letters = { }
table_print_code
<< ‘print "’ << ((i < addend_strs.size - 1)? ’ ’ : ‘+’)
<< ’ ’ * (sum_str.length - addend_str.length)
<< addend_str.gsub(/([a-z])/, ’ \1:#{\1}’) << “\n”\n"
end
table_print_code
<< ‘print "-’ << (’----’ * sum_str.length) << “\n”\n"
<< ‘print " ’ << sum_str.gsub(/([a-z])/, ’ \1:#{\1}’) << “\n”\n"
sum_chars = sum_str.split(//).reverse
first_letters[sum_chars[-1]] = 1

printing out

works than

# my usual verbose documentation (i.e., run this script with -v).

seen_chars = { }
code_tail = ‘’
indent = ‘’
(0…sum_chars.size).each do |col|
sum_char = sum_chars[col]
col_sum_code = “#{indent}carry#{col+1}, #{sum_char} = (carry#{col}”
|dig_char|
next if (dig_char.nil?)
if (seen_chars[dig_char].nil?)
|#{dig_char}|\n”
code_tail[0,0] = “#{indent}end\n”
indent << ’ ’
seen_chars[dig_char] = 1
0?\n”
if (first_letters.has_key?(dig_char))
col_sum_code[0,0] = ’ ’ # fix indentation
answer_print_code << “, #{dig_char} = #{#{dig_char}}”
end
col_sum_code << " + #{dig_char}"
end
col_sum_code << “).divmod(10)\n”
col_sum_code.sub!(/(carry0 + /, ‘(’)
if (seen_chars[sum_char].nil?)
0?\n”
if (first_letters.has_key?(sum_char))
code_tail[0,0] = “#{indent}end\n”
indent << ’ ’
seen_chars[sum_char] = 1
answer_print_code << “, #{sum_char} = #{#{sum_char}}”
else
col_sum_code.sub!(/ = /, '2 = ')
<< col_sum_code
<< “#{indent}next unless (#{sum_char}2 == #{sum_char}) #
inconsistent?\n”
end
end

# And print out the code (if verbose) and run it!

print code, “\n” if (verbose)
eval(code)

Here is my solution for Ruby Q. 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:

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 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 } digits = DIGITS - digits return if digits.empty? @solution[where] = digits[rand(digits.size)] end def swap m = rand(@solution.size) n = m while n == m n = rand(@solution.size) end @solution[m], @solution[n] = @solution[n], @solution [m] 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 } @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 ``` ``` # 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.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 ```

Regards, Morton