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

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

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 |

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 |

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 |

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

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 |

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 |

Re: [QUIZ] Verbal Arithmetic (#128)Jason,
> So your task is to find the key. Just think of these as a cryptogram with numbers instead of letters. - Warren Brown |

[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| 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=_AOWdGcXhV+5KlxB-- --Boundary-00=_AOWdGcXhV+5KlxB-- |

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

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

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.