Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   [QUIZ] Verbal Arithmetic (#128) (http://www.velocityreviews.com/forums/t841588-quiz-verbal-arithmetic-128-a.html)

 Ruby Quiz 06-15-2007 12:23 PM

[QUIZ] Verbal Arithmetic (#128)

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

 anansi 06-15-2007 12:51 PM

Re: [QUIZ] Verbal Arithmetic (#128)

I really don't get it :) How did you figured out that 2 = y in your example?

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

--
greets

one must still have chaos in oneself to be able to
give birth to a dancing star

 James Edward Gray II 06-15-2007 12:57 PM

Re: [QUIZ] Verbal Arithmetic (#128)

On Jun 15, 2007, at 7:55 AM, anansi wrote:

> I really don't get it :) How did you figured out that 2 = y in your
> example?

Well, a non-clever way is to try an exhaustive search of each digit
for each letter.

James Edward Gray II

 anansi 06-15-2007 01:06 PM

Re: [QUIZ] Verbal Arithmetic (#128)

ohh I totally misunderstood the task here.. I thought the input would be
send+more and my app should give money as answer trough calculation..

James Edward Gray II wrote:
> On Jun 15, 2007, at 7:55 AM, anansi wrote:
>
>> I really don't get it :) How did you figured out that 2 = y in your
>> example?

>
> Well, a non-clever way is to try an exhaustive search of each digit for
> each letter.
>
> James Edward Gray II
>

--
greets

one must still have chaos in oneself to be able to
give birth to a dancing star

 Sammy Larbi 06-15-2007 01:17 PM

Re: [QUIZ] Verbal Arithmetic (#128)

anansi wrote, On 6/15/2007 8:10 AM:
> ohh I totally misunderstood the task here.. I thought the input would
> be send+more and my app should give money as answer trough calculation..
>

For perhaps a reason to change the wording, that's what I thought as
well until I read the explanation to anansi's question.

Sam

> James Edward Gray II wrote:
>> On Jun 15, 2007, at 7:55 AM, anansi wrote:
>>
>>> I really don't get it :) How did you figured out that 2 = y in your
>>> example?

>>
>> Well, a non-clever way is to try an exhaustive search of each digit
>> for each letter.
>>
>> James Edward Gray II
>>

>
>

 James Edward Gray II 06-15-2007 01:25 PM

Re: [QUIZ] Verbal Arithmetic (#128)

On Jun 15, 2007, at 8:17 AM, Sammy Larbi wrote:

> anansi wrote, On 6/15/2007 8:10 AM:
>> ohh I totally misunderstood the task here.. I thought the input
>> would be send+more and my app should give money as answer trough
>> calculation..
>>

>
> For perhaps a reason to change the wording, that's what I thought
> as well until I read the explanation to anansi's question.

Sorry for the confusion folks. You get both sides of the equation
and are expected to fine the digit to represent each letter.

James Edward Gray II

 Robert Dober 06-15-2007 01:27 PM

Re: [QUIZ] Verbal Arithmetic (#128)

Hmm maybe this helps to clarify (for emacs users) the problem is like
mpuzz :) (mpuz?)

Robert

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

 Warren Brown 06-15-2007 05:35 PM

Re: [QUIZ] Verbal Arithmetic (#128)

Jason,

Just think of these as a cryptogram with numbers instead of letters.

- Warren Brown

 Jesse Merriman 06-17-2007 05:25 PM

[QUIZ][SOLUTION] Verbal Arithmetic (#128)

--Boundary-00=_AOWdGcXhV+5KlxB
Content-Type: Multipart/Mixed;
boundary="Boundary-00=_AOWdGcXhV+5KlxB"

--Boundary-00=_AOWdGcXhV+5KlxB
Content-Type: text/plain;
charset="utf-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 = 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=_AOWdGcXhV+5KlxB
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=_AOWdGcXhV+5KlxB
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|
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.
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=_AOWdGcXhV+5KlxB--
--Boundary-00=_AOWdGcXhV+5KlxB--

 Jesse Merriman 06-17-2007 05:27 PM

[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|
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.
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--

All times are GMT. The time now is 04:14 PM.