Forum: Ruby Verbal Arithmetic (#128)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-06-15 16:24
(Received via mailing list)
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/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion.  Please reply to the original quiz
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
anansi (Guest)
on 2007-06-15 16:55
(Received via mailing list)
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
James G. (Guest)
on 2007-06-15 16:58
(Received via mailing list)
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 (Guest)
on 2007-06-15 17:10
(Received via mailing list)
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
Sammy L. (Guest)
on 2007-06-15 17:17
(Received via mailing list)
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
James G. (Guest)
on 2007-06-15 17:26
(Received via mailing list)
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
Robert D. (Guest)
on 2007-06-15 17:27
(Received via mailing list)
Hmm maybe this helps to clarify (for emacs users) the problem is like
mpuzz :) (mpuz?)

Robert
Jason R. (Guest)
on 2007-06-15 19:20
(Received via mailing list)
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

So your task is to find the key.

Jason
Warren B. (Guest)
on 2007-06-15 21:36
(Received via mailing list)
Jason,

> So your task is to find the key.

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

    - Warren B.
Aureliano C. (Guest)
on 2007-06-17 03:43
(Received via mailing list)
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
>
>


--
"Es también nuestra intención erradicar la corrupción, ofreciendo como
norma la honestidad, la idoneidad y la eficiencia. Con madurez y
sentido de unidad es fácil pensar en la recomposición del ser
argentino. Ese ser argentino, basado en madurez y en sentido de
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
darren kirby (Guest)
on 2007-06-17 04:10
(Received via mailing list)
quoth the Aureliano C.:

> When can I send my solution to be
> reviewed?

I think about 12 hours from now...

-d
Raf C. (Guest)
on 2007-06-17 18:04
(Received via mailing list)
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
Aureliano C. (Guest)
on 2007-06-17 19:12
(Received via mailing list)
Well, I think I can send it now. My implementation is on
http://pastie.caboo.se/71198.


On 6/16/07, Aureliano C. <removed_email_address@domain.invalid> 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
> "Es también nuestra intención erradicar la corrupción, ofreciendo como
> norma la honestidad, la idoneidad y la eficiencia. Con madurez y
> sentido de unidad es fácil pensar en la recomposición del ser
> argentino. Ese ser argentino, basado en madurez y en sentido de
> 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
>


--
"Es también nuestra intención erradicar la corrupción, ofreciendo como
norma la honestidad, la idoneidad y la eficiencia. Con madurez y
sentido de unidad es fácil pensar en la recomposición del ser
argentino. Ese ser argentino, basado en madurez y en sentido de
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
Holger M. (Guest)
on 2007-06-17 21:19
(Received via mailing list)
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 && a*c==d'
solving a*b*c*d!=0 && a+b==c && a+c==d-b && a*c==d
-- Solution ---
a: 2
b: 1
c: 3
d: 6

Please feel free to send any comments.

Regards
Holger




#!/usr/bin/ruby -w

#
# Solution to ruby quiz #128
# http://www.rubyquiz.com/quiz128.html
# by Holger
#
# Usage:
#   verbal_arithmetic.rb <equation>
#
# Examples:
#   verbal_arithmetic.rb 'send+more=money'
#   verbal_arithmetic.rb 'a+b==c && a+c==d-b && a*c==d'
#



#*********************************************************************
#  Permutator which gives all combinations of <m> elements out of
#    array <n>
#
#  usage:
#    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
already present)
puzzle = ARGV[0].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
Jesse M. (Guest)
on 2007-06-17 21:26
(Received via mailing list)
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
Jesse M. (Guest)
on 2007-06-17 21:27
(Received via mailing list)
[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
Eric I. (Guest)
on 2007-06-17 23:32
(Received via mailing list)
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 Q. #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
  attr_reader :letters

  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)
    @available_digits.add @letters[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)
      chosen_letters.add(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)
    chosen_letters.add(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)
Justin E. (Guest)
on 2007-06-18 07:29
(Received via mailing list)
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!

(see link for the code)

I packaged all of my code inside the following class:

class VerbalArithmetic

  # Parse given equation into lvalues (words on the left-hand side of
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[0] # Get last lvalue
    rvalue = rvalue[1]      # 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 = Marshal::load(Marshal::dump(lvalues))
    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

  # Determines if the given equation may be solved by
  # 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
Glen F. Pankow (Guest)
on 2007-06-18 15:33
(Received via mailing list)
#! /usr/bin/env ruby
#
#  quiz-128  --  Ruby Q. #128  --  Verbal Arithmetic.
#
#  Usage:  quiz-128 [ -v ] '<equation string>'
#     or:  quiz-128 [ -v ] <addend> <addend> [ <addend> ... ] <sum>
#
#  See the Ruby Q. #128 documentation for more information
#  (http://www.rubyquiz.com/quiz128.html).
#
#  Glen Pankow      06/17/07        Original version.
#
#  Licensed under the Ruby License.
#
#-----------------------------------------------------------------------------
#
#  I take a slightly different approach to this quiz:  I build up code
that
#  kinda-sorta models addition as taught in U.S. elementary schools
(taking
#  into account the various constraints of the problem), then eval it.
#
#  And instead of generating permutations of unassigned digits and using
#  recursion for backtracking, I have a single array of digits that is
used
#  sort of as a mask (nil entries mark assigned digits) and use Ruby's
#  wonderful magic iterator facility to scan through it.
#
#  $ uname -srmpio
#  Linux 2.6.9-55.ELsmp i686 i686 i386 GNU/Linux
#
#  $ time ./quiz-128 'send + more = money'
#  d = 7, e = 5, y = 2, n = 6, r = 8, o = 0, s = 9, m = 1
#      1   0   1   1
#        s:9 e:5 n:6 d:7
#  +     m:1 o:0 r:8 e:5
#  ---------------------
#    m:1 o:0 n:6 e:5 y:2
#  0.065u 0.003s 0:00.07 85.7%     0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 forty ten ten sixty
#  y = 6, n = 0, t = 8, e = 5, r = 7, x = 4, o = 9, i = 1, f = 2, s = 3
#      1   2   1   0
#    f:2 o:9 r:7 t:8 y:6
#            t:8 e:5 n:0
#  +         t:8 e:5 n:0
#  ---------------------
#    s:3 i:1 x:4 t:8 y:6
#  0.029u 0.002s 0:00.03 66.6%     0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 eat+that=apple
#  t = 9, e = 8, a = 1, l = 3, h = 2, p = 0
#      1   1   0   1
#            e:8 a:1 t:9
#  +     t:9 h:2 a:1 t:9
#  ---------------------
#    a:1 p:0 p:0 l:3 e:8
#  0.008u 0.002s 0:00.01 0.0%      0+0k 0+0io 0pf+0w
#
#  $ time ./quiz-128 ruby rubber baby buggy bumper
#  y = 0, r = 7, b = 8, e = 1, g = 4, u = 2, a = 3, p = 9, m = 6
#  ...
#  y = 0, r = 7, b = 8, e = 5, g = 4, u = 2, a = 3, p = 9, m = 6
#      1   2   1   2   0
#            r:7 u:2 b:8 y:0
#    r:7 u:2 b:8 b:8 e:5 r:7
#            b:8 a:3 b:8 y:0
#  +     b:8 u:2 g:4 g:4 y:0
#  -------------------------
#    b:8 u:2 m:6 p:9 e:5 r:7
#  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
addend_strs = [ ]
ARGV.each do |arg|
    if (arg == '-v')
        verbose = true
    else
        arg.split(/[\s+=]+/).each { |term| addend_strs << term }
    end
end
addend_strs = [ 'send', 'more', 'money' ] if (addend_strs.empty?)
sum_str = addend_strs.pop

#
# Split the strings up into their component letters; create some (ugly)
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"
addends = [ ]
first_letters = { }
(0...addend_strs.size).each do |i|
    addend_str = addend_strs[i]
    addend_chars = addend_str.split(//).reverse
    addends << addend_chars
    first_letters[addend_chars[-1]] = 1
    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

#
# Build the addition code.
#
# This, too, is quite ugly and I don't bother to document it, as
printing out
# the generated code will probably give one a better idea of how it
works than
# my usual verbose documentation (i.e., run this script with -v).
#
seen_chars = { }
code_head = "rem_digs = (0..9).to_a\n"
code_tail = ''
answer_print_code = 'print "'
indent = ''
(0...sum_chars.size).each do |col|
    sum_char = sum_chars[col]
    col_sum_code = "#{indent}carry#{col+1}, #{sum_char} = (carry#{col}"
    addends.inject([ ]) { |dc, addend| dc << addend[col] }.each do
|dig_char|
        next if (dig_char.nil?)
        if (seen_chars[dig_char].nil?)
            code_head << "#{indent}rem_digs.unmarkeds do
|#{dig_char}|\n"
            code_tail[0,0] = "#{indent}end\n"
            indent << '   '
            seen_chars[dig_char] = 1
            code_head << "#{indent}next if (#{dig_char} == 0)  # leading
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?)
        code_head << col_sum_code
        code_head << "#{indent}next if (#{sum_char} == 0)  # leading
0?\n" \
          if (first_letters.has_key?(sum_char))
        code_head << "#{indent}rem_digs.if_unmarked(#{sum_char}) do\n"
        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 = ')
        code_head \
          << col_sum_code \
          << "#{indent}next unless (#{sum_char}2 == #{sum_char})  #
inconsistent?\n"
    end
end
answer_print_code.sub!(/\", /, '"\n')
answer_print_code << "\\n\"\n"

#
# And print out the code (if verbose) and run it!
#
code = code_head + answer_print_code + table_print_code + code_tail
print code, "\n" if (verbose)
eval(code)
Morton G. (Guest)
on 2007-06-18 18:56
(Received via mailing list)
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:

<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 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
</code>

And here are the library classes:

<code>
#  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 
(removed_email_address@domain.invalid).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 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
</code>

Regards, Morton
Eric I. (Guest)
on 2007-06-18 20:46
(Received via mailing list)
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/alphametic/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 G. (Guest)
on 2007-06-19 04:01
(Received via mailing list)
On Jun 17, 2007, at 9:03 AM, Raf C. 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 G. II
Morton G. (Guest)
on 2007-06-19 08:40
(Received via mailing list)
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 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
</code>

And here are the library classes:

<code>
#  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 
(removed_email_address@domain.invalid).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 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
</code>

Regards, Morton
Eugene K. (Guest)
on 2007-06-19 18:30
(Received via mailing list)
On Jun 18, 4:59 pm, James Edward G. II <removed_email_address@domain.invalid>
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
James G. (Guest)
on 2007-06-19 21:20
(Received via mailing list)
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. (Guest)
on 2007-06-19 22:49
(Received via mailing list)
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
+ 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
# 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] http://www.gecode.org/download.html
[4] http://www.gecode.org/gecode-doc-latest/PageComp.html
Andreas L. (Guest)
on 2007-06-20 02:34
(Received via mailing list)
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).
Bob S. (Guest)
on 2007-06-20 17:14
(Received via mailing list)
On 6/15/07, Ruby Q. <removed_email_address@domain.invalid> 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.
Andreas L. (Guest)
on 2007-06-21 09:55
(Received via mailing list)
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)
This topic is locked and can not be replied to.