From: Justin Ethier <justin.ethier@...>
Date: 2007-06-18T12:28:10+09:00
Subject: Re: [QUIZ] Verbal Arithmetic (#128)

------=_Part_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 = 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

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+more=money'
>         s: 9
>         e: 5
>         n: 6
>         d: 7
>         m: 1
>         o: 0
>         r: 8
>         y: 2
>
>

------=_Part_66533_6289323.1182137288807--