From: Jesse Merriman <jesse.d.merriman@...>
Date: 2007-06-18T02:27:22+09:00
Subject: [QUIZ][SOLUTION] Verbal Arithmetic (#128)

--Boundary-00=_s1WdG2CAmTEGH1s
Content-Type: Multipart/Mixed;
  boundary="Boundary-00=_s1WdG2CAmTEGH1s"

--Boundary-00=_s1WdG2CAmTEGH1s
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

[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


-- 
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

--Boundary-00=_s1WdG2CAmTEGH1s
Content-Type: application/x-ruby;
  name="perms_and_combs.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="perms_and_combs.rb"

# Ruby Quiz 128: Verbal Arithmetic
# perms_and_combs.rb

# Add methods for generating permutations and combinations of Arrays. There's
# a lot of ugliness here - its a copy-paste-slightly-modify job of a bunch of
# old ugly code.
class Array
  # Get the first r-combination of the elements in this Array.
  def first_combination r
    return nil if r < 1 or size < r
    first_combo = Array.new r
    (0...r).each { |i| first_combo[i] = self[i] }
    first_combo
  end

  # Get the combination after start_combo of the elements in this Array.
  def next_combination start_combo
    # Create the positions array
    positions = Array.new start_combo.size
    (0...positions.size).each do |i|
      positions[i] = self.index(start_combo[i]) + 1
    end

    # bump up to the next position
    r, n = start_combo.size, self.size
    i = r
    i -= 1 while positions[i-1] == n - r + i
    return nil if i.zero?

    positions[i-1] = positions[i-1] + 1
    ((i+1)..r).each do |j|
      positions[j-1] = positions[i-1] + j - i
    end

    # translate the next position back into a combination
    next_combo = Array.new r
    (0...next_combo.size).each do |i|
      next_combo[i] = self[positions[i] - 1]
    end
    next_combo
  end

  # Yields every r-combination of the elements in this Array.
  def each_combination r
    combo = first_combination r
    while not combo.nil?
      yield combo
      combo = next_combination combo
    end
  end

  # Swap the elements at the two given positions.
  def swap! i, j
    self[i], self[j] = self[j], self[i]
  end

  # Generates all permutations of this Array, yielding each one.
  # Based on: http://www.geocities.com/permute_it/
  # This does not generate them in lexicographic order, but it is fairly quick.
  def each_permutation
    # This is pretty ugly..
    a, p, i = self.clone, (0..self.size).to_a, 0
    while i < self.size
      p[i] -= 1
      (i % 2) == 1 ? j = p[i] : j = 0
      a.swap! i, j
      yield a
      i = 1
      while p[i].zero?
        p[i] = i
        i += 1
      end
    end
  end
end

--Boundary-00=_s1WdG2CAmTEGH1s
Content-Type: application/x-ruby;
  name="verbal_arithmetic.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="verbal_arithmetic.rb"

#!/usr/bin/env ruby
# Ruby Quiz 128: Verbal Arithmetic
# verbal_arithmetic.rb

require 'perms_and_combs.rb'
require 'set'

class VerbalArithmetic
  # Create a new VerbalArithmetic.
  # - words:  an array of words
  # - op:     a string representation of an operation ('+', '-', or '*')
  # - result: desired result
  # - base:   numeric base
  def initialize words, op, result, base = 10
    @words, @op, @result, @base = words, Ops[op], result, base
    @first_letters = Set[ *(words.map { |w| w[0..0] } + [result[0..0]]) ]
    @max_level = (words + [result]).max { |x,y| x.length <=> y.length}.length
    self
  end

  # Returns a hash of letter => number.
  def decode level = 1, partial_mapping = {}
    words_chunk, result_chunk = right_chunk level

    each_valid_mapping(words_chunk, result_chunk, partial_mapping) do |mapping|
      if level == @max_level
        if operate_on_words(words_chunk, mapping) ==
           translate(@result, mapping) and
           not @first_letters.map{ |c| mapping[c]}.include?(0)
          return mapping
        end
      else
        d = decode(level + 1, mapping)
        return d if not d.nil?
      end
    end
  end

  private

  Ops = { '+' => lambda { |x,y| x+y },
          '-' => lambda { |x,y| x-y },
          '*' => lambda { |x,y| x*y } }

  # Yield each valid mapping.
  def each_valid_mapping words, result, partial_mapping = {}
    level = words.first.size

    each_mapping(words + [result], partial_mapping) do |mapping|
      if adjust(operate_on_words(words, mapping), level) ==
         adjust(translate(result, mapping), level)
        yield mapping
      end
    end
  end

  def operate_on_words words, mapping
    nums = []
    words.each { |word| nums << translate(word, mapping) }
    operate nums
  end

  # Operate on the given numbers.
  def operate nums
    nums.inject { |memo, n| @op[memo, n] }
  end

  # Convert a word to a number using the given mapping of letters => numbers.
  def translate word, mapping
    t = word.split(//).map { |c| mapping[c] }
    t.map { |n| n.nil? ? 0 : n }.join.to_i(@base)
  end

  # Generate possible ways of mapping the letters in words to numbers.
  # - words: an array of words
  # - determined: a previously-determined partial mapping which is to be filled
  #               out the rest of the way
  def each_mapping words, determined = {}
    letters = Set[]
    words.each do |word|
      word.each_byte { |b| letters << b.chr if not determined.has_key?(b.chr) }
    end

    # Find all arrangements of letters.size undetermined numbers and for each
    # match them up with letters.
    pool = (0...@base).to_a - determined.values
    if pool.size.zero? or letters.size.zero?
      yield determined.clone
    else
      pool.each_combination(letters.size) do |comb|
        comb.each_permutation do |perm|
          mapping = determined.clone
          letters.each_with_index { |let, i| mapping[let] = perm[i] }
          yield mapping
        end
      end
    end
  end

  # Return the result of cutting off the left-side of each word in @words and
  # @result, leaving level-length right-side strings. '0' is prepended to
  # too-short strings.
  def right_chunk level
    words_chunk = @words.map { |word| chunk(word, level) }
    res_chunk = chunk(@result, level)
    [words_chunk, res_chunk]
  end

  def chunk word, level
    word.length < level ? word : word[(word.length - level)...word.length]
  end

  # Adjust the intermediate number num. If its positive, return num modulus
  # @base ** level. Else, return the first digit of the number mod @base
  # appended to the rest of the number.
  def adjust num, level
    if num >= 0
      num % (@base ** level)
    else
      s = num.to_s
      s[0..1] = (s[0..1].to_i(@base) % @base).to_s
      s.to_i @base
    end
  end
end

# Usage:
#   verbal_arithmetic.rb WORDS OP RESULT [BASE]
#
# WORDS:  a list of words
# OP:     the operation (either +, -, or *)
# RESULT: the result of applying OP to all WORDS
# BASE:   the number base to use (default: 10)
#
# Examples:
#   verbal_arithmetic.rb 'send more' + money
#   verbal_arithmetic.rb 'forty ten ten' + sixty
if __FILE__ == $0
  words, op, result = ARGV[0].split(' '), ARGV[1], ARGV[2]
  base = (ARGV[3].nil? ? 10 : ARGV[3].to_i)

  if op == '-' and words.size != 2
    $stderr.puts 'Subtraction of anything but 2 words is not supported.'
    exit 1
  elsif ['+', '*', '-'].include? op
    va = VerbalArithmetic.new words, op, result, base
    mapping = va.decode
    if mapping
      puts 'Found mapping:'
      mapping.each { |c,n| puts "  #{c}: #{n}" }
    else
      puts 'No mapping could be found.'
    end
  else
    $stderr.puts "#{op} is not a supported operation."
    exit 1
  end
end

--Boundary-00=_s1WdG2CAmTEGH1s--
--Boundary-00=_s1WdG2CAmTEGH1s--