------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!

(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  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  arshal::load(Marshal::dump(lvalues))
    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
> on Ruby Talk 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+moreney'
>         s: 9
>         e: 5
>         n: 6
>         d: 7
>         m: 1
>         o: 0
>         r: 8
>         y: 2
>
>

------art_66533_6289323.1182137288807--