--Boundary-00
OWdGcXhV+5KlxB
Content-Type: Multipart/Mixed;
  boundaryoundary-00
OWdGcXhV+5KlxB"

--Boundary-00
OWdGcXhV+5KlxB
Content-Type: text/plain;
  charsettf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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  )

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
OWdGcXhV+5KlxB
Content-Type: application/x-ruby;
  nameerms_and_combs.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filenameerms_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  rray.new r
    (0...r).each { |i| first_combo[i]  elf[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  rray.new start_combo.size
    (0...positions.size).each do |i|
      positions[i]  elf.index(start_combo[i]) + 1
    end

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

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

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

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

  # Swap the elements at the two given positions.
  def swap! i, j
    self[i], self[j]  elf[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  elf.clone, (0..self.size).to_a, 0
    while i < self.size
      p[i] - 
      (i % 2) 1 ? j  [i] : j  
      a.swap! i, j
      yield a
      i  
      while p[i].zero?
        p[i]  
        i + 
      end
    end
  end
end

--Boundary-00
OWdGcXhV+5KlxB
Content-Type: application/x-ruby;
  nameerbal_arithmetic.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filenameerbal_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  0
    @words, @op, @result, @base  ords, Ops[op], result, base
    @first_letters  et[ *(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  , partial_mapping  }
    words_chunk, result_chunk  ight_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  ecode(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  ords.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  ord.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  et[]
    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  etermined.clone
          letters.each_with_index { |let, i| mapping[let]  erm[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  hunk(@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 > 
      num % (@base ** level)
    else
      s  um.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  RGV[0].split(' '), ARGV[1], ARGV[2]
  base  ARGV[3].nil? ? 10 : ARGV[3].to_i)

  if op '-' and words.size ! 
    $stderr.puts 'Subtraction of anything but 2 words is not supported.'
    exit 1
  elsif ['+', '*', '-'].include? op
    va  erbalArithmetic.new words, op, result, base
    mapping  a.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
OWdGcXhV+5KlxB--
--Boundary-00
OWdGcXhV+5KlxB--