[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Verbal Arithmetic (#128

James Gray

6/15/2007 12:24:00 PM

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

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
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
20 Answers

mrpink

6/15/2007 12:52:00 PM

0

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 Gray

6/15/2007 12:58:00 PM

0

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

mrpink

6/15/2007 1:06:00 PM

0

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

6/15/2007 1:17:00 PM

0

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 Gray

6/15/2007 1:26:00 PM

0

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

6/15/2007 1:27:00 PM

0

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

6/15/2007 5:36:00 PM

0

Jason,

> So your task is to find the key.

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

- Warren Brown

Jesse Merriman

6/17/2007 5:26:00 PM

0


Content-Type: Multipart/Mixed;
boundary="Boundary-00=_AOWdGcXhV+5KlxB"
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.jessemer...

Jesse Merriman

6/17/2007 5:27:00 PM

0


Content-Type: Multipart/Mixed;
boundary="Boundary-00=_s1WdG2CAmTEGH1s"
[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.jessemer...

Eric I.

6/17/2007 7:28:00 PM

0

This program solves addition problems with any number of terms. It
finds and displays all solutions to the problem.

The solving process is broken up into a sequence of simple steps all
derived from class Step. A Step can be something such as 1) choosing
an available digit for a given letter or 2) summing up a column and
seeing if the result matches an already-assigned letter. As steps
succeed the process continues with the following steps. But if a step
fails (i.e., there's a contradiction) then the system backs up to a
point where another choice can be made. This is handled by recursing
through the sequence of steps. In fact, even when a solution is
found, the program still backtracks to find other solutions.

The expectation is that by testing for contradictions as early as
possible in the process we'll tend to avoid dead ends and the result
will be much better than an exhaustive search.

For example, here are the steps for a sample equation:

send
+more
-----
money

1. Choose a digit for "d".
2. Choose a digit for "e".
3. Sum the column using letters "d", "e" (and include carry).
4. Set the digit for "y" based on last column summed.
5. Choose a digit for "n".
6. Choose a digit for "r".
7. Sum the column using letters "n", "r" (and include carry).
8. Verify that last column summed matches current digit for "e".
9. Choose a digit for "o".
10. Sum the column using letters "e", "o" (and include carry).
11. Verify that last column summed matches current digit for "n".
12. Choose a digit for "s".
13. Verify that "s" has not been assigned to zero.
14. Choose a digit for "m".
15. Verify that "m" has not been assigned to zero.
16. Sum the column using letters "s", "m" (and include carry).
17. Verify that last column summed matches current digit for "o".
18. Sum the column using letters (and include carry).
19. Verify that last column summed matches current digit for "m".
20. Display a solution (provided carry is zero)!

Eric
----
Are you interested in on-site Ruby training that's been highly
reviewed by former students? http://Lea...

====

# This is a solution to Ruby Quiz #128. As input it takes a "word
# equation" such as "send+more=money" and determines all possible
# mappings of letters to digits that yield a correct result.
#
# The constraints are: 1) a given digit can only be mapped to a single
# letter, 2) the first digit in any term cannot be zero.
#
# The solving process is broken up into a sequence of simple steps all
# derived from class Step. A Step can be something such as 1)
# choosing an available digit for a given letter or 2) summing up a
# column and seeing if the result matches an already-assigned letter.
# As steps succeed the process continues with the following steps.
# But if a step fails (i.e., there's a contradiction) then the system
# backs up to a point where another choice can be made. This is
# handled by recursing through the sequence of steps. In fact, even
# when a solution is found, the program still backtracks to find other
# solutions.


require 'set'


# State represents the stage of a partially solved word equation. It
# keeps track of what digits letters map to, which digits have not yet
# been assigned to letters, and the results of the last summed column,
# including the resulting digit and any carry if there is one.
class State
attr_accessor :sum, :carry
attr_reader :letters

def initialize()
@available_digits = Set.new(0..9)
@letters = Hash.new
@sum, @carry = 0, 0
end

# Return digit for letter.
def [](letter)
@letters[letter]
end

# The the digit for a letter.
def []=(letter, digit)
# if the letter is currently assigned, return its digit to the
# available set
@available_digits.add @letters[letter] if @letters[letter]

@letters[letter] = digit
@available_digits.delete digit
end

# Clear the digit for a letter.
def clear(letter)
@available_digits.add @letters[letter]
@letters[letter] = nil
end

# Return the available digits as an array copied from the set.
def available_digits
@available_digits.to_a
end

# Tests whether a given digit is still available.
def available?(digit)
@available_digits.member? digit
end

# Receives the total for a column and keeps track of it as the
# summed-to digit and any carry.
def column_total=(total)
@sum = total % 10
@carry = total / 10
end
end


# Step is an "abstract" base level class from which all the "concrete"
# steps can be deriveds. It simply handles the storage of the next
# step in the sequence. Subclasses should provide 1) a to_s method to
# describe the step being performed and 2) a perform method to
# actually perform the step.
class Step
attr_writer :next_step
end


# This step tries assigning each available digit to a given letter and
# continuing from there.
class ChooseStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Choose a digit for \"#{@letter}\"."
end

def perform(state)
state.available_digits.each do |v|
state[@letter] = v
@next_step.perform(state)
end
state.clear(@letter)
end
end


# This step sums up the given letters and changes to state to reflect
# the sum. Because we may have to backtrack, it stores the previous
# saved sum and carry for later restoration.
class SumColumnStep < Step
def initialize(letters)
@letters = letters
end

def to_s
list = @letters.map { |l| "\"#{l}\"" }.join(', ')
"Sum the column using letters #{list} (and include carry)."
end

def perform(state)
# save sum and carry
saved_sum, saved_carry = state.sum, state.carry

state.column_total =
state.carry +
@letters.inject(0) { |sum, letter| sum + state[letter] }
@next_step.perform(state)

# restore sum and carry
state.sum, state.carry = saved_sum, saved_carry
end
end


# This step determines the digit for a letter given the last column
# summed. If the digit is not available, then we cannot continue.
class AssignOnSumStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Set the digit for \"#{@letter}\" based on last column summed."
end

def perform(state)
if state.available? state.sum
state[@letter] = state.sum
@next_step.perform(state)
state.clear(@letter)
end
end
end


# This step will occur after a column is summed, and the result must
# match a letter that's already been assigned.
class CheckOnSumStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Verify that last column summed matches current " +
"digit for \"#{@letter}\"."
end

def perform(state)
@next_step.perform(state) if state[@letter] == state.sum
end
end


# This step will occur after a letter is assigned to a digit if the
# letter is not allowed to be a zero, because one or more terms begins
# with that letter.
class CheckNotZeroStep < Step
def initialize(letter)
@letter = letter
end

def to_s
"Verify that \"#{@letter}\" has not been assigned to zero."
end

def perform(state)
@next_step.perform(state) unless state[@letter] == 0
end
end


# This step represents finishing the equation. The carry must be zero
# for the perform to have found an actual result, so check that and
# display a digit -> letter conversion table and dispaly the equation
# with the digits substituted in for the letters.
class FinishStep < Step
def initialize(equation)
@equation = equation
end

def to_s
"Display a solution (provided carry is zero)!"
end

def perform(state)
# we're supposedly done, so there can't be anything left in carry
return unless state.carry == 0

# display a letter to digit table on a single line
table = state.letters.invert
puts
puts table.keys.sort.map { |k| "#{table[k]}=#{k}" }.join(' ')

# display the equation with digits substituted for the letters
equation = @equation.dup
state.letters.each { |k, v| equation.gsub!(k, v.to_s) }
puts
puts equation
end
end


# Do a basic test for the command-line arguments validity.
unless ARGV[0] =~ Regexp.new('^[a-z]+(\+[a-z]+)*=[a-z]+$')
STDERR.puts "invalid argument"
exit 1
end


# Split the command-line argument into terms and figure out how many
# columns we're dealing with.
terms = ARGV[0].split(/\+|=/)
column_count = terms.map { |e| e.size }.max


# Build the display of the equation a line at a time. The line
# containing the final term of the sum has to have room for the plus
# sign.
display_columns = [column_count, terms[-2].size + 1].max
display = []
terms[0..-3].each do |term|
display << term.rjust(display_columns)
end
display << "+" + terms[-2].rjust(display_columns - 1)
display << "-" * display_columns
display << terms[-1].rjust(display_columns)
display = display.join("\n")
puts display


# AssignOnSumStep which letters cannot be zero since they're the first
# letter of a term.
nonzero_letters = Set.new
terms.each { |e| nonzero_letters.add(e[0, 1]) }


# A place to keep track of which letters have so-far been assigned.
chosen_letters = Set.new


# Build up the steps needed to solve the equation.
steps = []
column_count.times do |column|
index = -column - 1
letters = [] # letters for this column to be added

terms[0..-2].each do |term| # for each term that's being added...
letter = term[index, 1]
next if letter.nil? # skip term if no letter in column
letters << letter # note that this letter is part of sum

# if the letter does not have a digit, create a ChooseStep
unless chosen_letters.member? letter
steps << ChooseStep.new(letter)
chosen_letters.add(letter)
steps << CheckNotZeroStep.new(letter) if
nonzero_letters.member? letter
end
end

# create a SumColumnStep for the column
steps << SumColumnStep.new(letters)

summed_letter = terms[-1][index, 1] # the letter being summed to

# check whether the summed to letter should already have a digit
if chosen_letters.member? summed_letter
# should already have a digit, check that summed digit matches it
steps << CheckOnSumStep.new(summed_letter)
else
# doesn't already have digit, so create a AssignOnSumStep for
# letter
steps << AssignOnSumStep.new(summed_letter)
chosen_letters.add(summed_letter)

# check whether this letter cannot be zero and if so add a
# CheckNotZeroStep
steps << CheckNotZeroStep.new(summed_letter) if
nonzero_letters.member? summed_letter
end
end

# should be done, so add a FinishStep
steps << FinishStep.new(display)

# print out all the steps
# steps.each_with_index { |step, i| puts "#{i + 1}. #{step}" }

# let each step know about the one that follows it.
steps.each_with_index { |step, i| step.next_step = steps[i + 1] }

# start performing with the first step.
steps.first.perform(State.new)