```--Boundary-00
OWdGcXhV+5KlxB
Content-Type: Multipart/Mixed;
boundaryoundary-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|
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.
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--

```