```------art_66533_6289323.1182137288807
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

# 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  quation.split("+")
rvalue  values[-1].split("
lvalues[-1]  value[0] # Get last lvalue
rvalue  value[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.push(rvalue)
letters  }
words.each do |word|
word.split("").each do |letter|
letters[letter]  etter 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  value.reverse.split("")

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

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

# Map each combination of numbers to the underlying letters
map  }
parry  .project
for i in 0...letters.size
map[letters.values[i]]  arry[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
for i in 0...rvalue.size
lvalues.each do |lval|
remainder  emainder + map[lval[i]] if map[lval[i]] ! il # Sum
values
end

return false if (remainder % 10) ! ap[rvalue[i]] # Validate digit
remainder  emainder / 10                         # Truncate value at
this place
end

true
end
end

Finally, this code puts everything together:

va  erbalArithmetic.new
lvalues, rvalue  a.parse_equation("send+moreney")
map  a.find_solution(lvalues, rvalue)

puts "Solution: ", map if map ! il

And here is the output:

Solution:
m1n6y2d7o0e5r8s9

Thanks,

Justin

On 6/15/07, Ruby Quiz <james / grayproductions.net> wrote:
>
> The three rules of Ruby Quiz:
>
> 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 Quiz 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
> 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+moreney'
>         s: 9
>         e: 5
>         n: 6
>         d: 7
>         m: 1
>         o: 0
>         r: 8
>         y: 2
>
>

------art_66533_6289323.1182137288807--

```