From: James Edward Gray II <james@...>
Date: 2007-06-18T22:46:55+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-1--143741339
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

Begin forwarded message:

> From: lagroue@free.fr
> Date: June 16, 2007 11:15:34 AM CDT
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> Hello, I've just played with the Verbal Arithmetic game.
>
> You'll find my solution in attachment. It is able to solve many  
> problems, but slowly, since it relies on brute force.
>
> The idea is to translate the input expression into a ruby  
> expression, and to evaluate it with every digits permutations until  
> one fits.
>
> Words and '=' character only are modified : 'a + b = cd' is  
> translated to the 'a + b == 10*(c)+d'. Then the program evaluates  
> it with each digit permutation :
> eval 'a=1;b=2;c=3;d=4;a + b == 10*(c)+d' => false
> ...
> eval 'a=2;b=8;c=1;d=0;a + b == 10*(c)+d' => true
>
> Thanks for the game !
> Gwendal
>
> Sample outputs :
>
> $ ./verbal_arithmetics.rb 'forty+ten+ten=sixty'
> f: 2
> t: 8
> s: 3
> o: 9
> r: 7
> y: 6
> e: 5
> n: 0
> i: 1
> x: 4
> 29786+850+850=31486
>
> $ ./verbal_arithmetics.rb 'oz**z=odd'
> o: 1
> z: 2
> d: 4
> 12**2=144
>

--Apple-Mail-1--143741339
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0775;
	x-mac-creator=54784D74;
	name=verbal_arithmetics.rb
Content-Disposition: attachment;
	filename=verbal_arithmetics.rb

#!/usr/local/bin/ruby
# lagroue@free.fr

class Array
  # Yields all permutations of elements of self.
  # Provide with max_length in order to limit permutations length
  #
  # perms=[]; [0,1,2].permutations { |perm| perms << perm }; perms
  # => [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
  # perms=[]; [0,1,2,3].permutations(2) { |perm| perms << perm }; perms
  # => [[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]
  
  def permutations(max_length=nil)
    if empty? || max_length == 0
      yield []
    else
      max_length -= 1 if max_length
      (0...length).each { |index| (self[0...index]+self[(index+1)..-1]).permutations(max_length) { |perm| yield [self[index]]+perm } }
    end
  end
end

# Given a sentence, like 'forty+ten+ten=sixty', return a translation Array, or nil if none could be found.
#
# verbal_arithmetics('forty+ten+ten=sixty')
# => [["f", 2], ["t", 8], ["s", 3], ["o", 9], ["r", 7], ["y", 6], ["e", 5], ["n", 0], ["i", 1], ["x", 4]]
def verbal_arithmetics(sentence)
  digits = []           # all digits actually used in sentence.
  primary_digits = []   # the digits which should not translate to zero.
  sentence.scan(/\b(\w+)\b/).each { |number|
    number_digits = number.first.split('')
    primary_digits |= [number_digits.first]
    digits |= number_digits
  }
  raise "Too many digits" if digits.length > 10
  
  # reorder digits : primary first, then secondary
  secondary_digits = digits - primary_digits
  digits = primary_digits + secondary_digits
  
  # rewrite sentence : "hello" => 10*(10*(10*(10*(h)+e)+l)+l)+o
  sentence = sentence.gsub(/\b(\w+)\b/) { '('+$1.split('').inject('') { |s,d| if s.empty? then d else "10*(#{s})+#{d}" end } + ')'}.gsub('=', '==')
    
  # test all permutations of actual digits
  (0..9).to_a.permutations(digits.length) { |permutation|
    next if permutation[0...(primary_digits.length)].include?(0) # reject 0 for primary digits
    translation = digits.zip(permutation)
    # evalute "a=1;b=2;c=3;...;sentence"
    return translation if eval((translation.map { |(digit, number)| "#{digit}=#{number}" } << "#{sentence}").join(';'))
  }
  
  # no solution
  nil
end

if ARGV.empty?
  puts "exemple: verbal_arithmetics 'send+more=money'"
else
  sentence = ARGV[0].dup
  translation = verbal_arithmetics(sentence)
  if translation
    translation.each { |(digit, number)|
      sentence.gsub!(digit, number.to_s)
      puts "#{digit}: #{number}"
    }
    puts sentence
  else
    puts "no solution"
  end
end

--Apple-Mail-1--143741339
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

>


--Apple-Mail-1--143741339--