# \[QUIZ\] Verbal Arithmetic (#128) **URL:** \ **Category:** ruby-talk\ **Created:** [15 June 2007 12:23 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379 "2007-06-15T12:23:44Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [15 June 2007 12:23 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/1 "2007-06-15T12:23:44Z")
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/](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 ---
**Author:** ![anansi](https://avatars.discourse-cdn.com/v4/letter/a/9fc348/32.png) [@anansi](https://rubytalk.org/u/anansi)\ **Post date:** [15 June 2007 12:55 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/2 "2007-06-15T12:55:05Z")
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 ---
**Author:** ![Aureliano\_Calvo](https://avatars.discourse-cdn.com/v4/letter/a/f04885/32.png) [@Aureliano\_Calvo](https://rubytalk.org/u/Aureliano_Calvo)\ **Post date:** [16 June 2007 23:41 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/3 "2007-06-16T23:41:52Z")
Mi implementation is "working". For instance: ./quiz\_128.rb "a+b=c" b: 1 c: 6 But ./quiz\_128.rb "send+more=money" is taking ages! time ./quiz\_128.rb "send+more=money" m: 1 y: 2 n: 6 o: 0 d: 7 e: 5 r: 8 s: 9 real 7m17.065s user 2m46.806s sys 0m6.676s Is there some trick to cut the solution space (I'm just scanning the solution space) ? I know I have a crappy PC but I have a feeling that this is not the real problem! When can I send my solution to be reviewed? > **路路路** > > a: 5 > > > 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/](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 > > -- > "Es tambi茅n nuestra intenci贸n erradicar la corrupci贸n, ofreciendo como > norma la honestidad, la idoneidad y la eficiencia. Con madurez y > sentido de unidad es f谩cil pensar en la recomposici贸n del ser > argentino. Ese ser argentino, basado en madurez y en sentido de > unidad, permitir谩 inspirar para elevarnos por encima de la miseria que > la antinomia nos ha planteado, para dejar, de una vez por todas, ese > ser "anti" y ser, de una vez por todas, "pro": "Pro argentinos"" > > Jorge Rafael Videla para el 25 de mayo de 1976 ---
**Author:** ![Raf\_Coremans](https://avatars.discourse-cdn.com/v4/letter/r/9dc877/32.png) [@Raf\_Coremans](https://rubytalk.org/u/Raf_Coremans)\ **Post date:** [17 June 2007 14:03 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/4 "2007-06-17T14:03:24Z")
Hi, Here's my solution: [http://pastie.caboo.se/71188](http://pastie.caboo.se/71188) It's of the dumb-brute-force-slow-as-hell variety: $ time ./rq128\_verbalarithmetic\_rafc.rb 'send + more = money' {"m"=\>1, "y"=\>2, "n"=\>6, "o"=\>0, "d"=\>7, "e"=\>5, "r"=\>8, "s"=\>9} real 2m51.197s user 2m39.722s sys 0m11.397s $ time ./rq128\_verbalarithmetic\_rafc.rb 'forty + ten + ten = sixty' {"x"=\>4, "n"=\>0, "y"=\>6, "o"=\>9, "e"=\>5, "f"=\>2, "r"=\>7, "s"=\>3, "i"=\>1, "t"=\>8} real 7m28.151s user 6m55.114s sys 0m32.938s But on the other hand, it can handle any operator as well as bases other than 10. Did you know for instance that in base 9, ruby is worth up to 4 perls with some extra fun thrown in? $ ./rq128\_verbalarithmetic\_rafc.rb 'n \* perl + fun = ruby' 9 {"l"=\>8, "b"=\>7, "y"=\>0, "n"=\>1, "e"=\>5, "p"=\>3, "f"=\>6, "r"=\>4, "u"=\>2} {"l"=\>8, "b"=\>7, "y"=\>0, "n"=\>1, "e"=\>6, "p"=\>3, "f"=\>5, "r"=\>4, "u"=\>2} {"l"=\>1, "b"=\>7, "y"=\>4, "n"=\>2, "e"=\>6, "p"=\>3, "f"=\>5, "r"=\>8, "u"=\>0} {"l"=\>2, "b"=\>5, "y"=\>0, "n"=\>3, "e"=\>7, "p"=\>1, "f"=\>8, "r"=\>6, "u"=\>4} {"l"=\>4, "b"=\>5, "y"=\>6, "n"=\>3, "e"=\>0, "p"=\>2, "f"=\>8, "r"=\>7, "u"=\>1} {"l"=\>4, "b"=\>0, "y"=\>6, "n"=\>3, "e"=\>1, "p"=\>2, "f"=\>8, "r"=\>7, "u"=\>5} {"l"=\>4, "b"=\>7, "y"=\>6, "n"=\>3, "e"=\>5, "p"=\>2, "f"=\>1, "r"=\>8, "u"=\>0} {"l"=\>2, "b"=\>6, "y"=\>3, "n"=\>4, "e"=\>7, "p"=\>1, "f"=\>5, "r"=\>8, "u"=\>0} Regards, Raf ---
**Author:** ![Jesse\_Merriman](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@Jesse\_Merriman](https://rubytalk.org/u/Jesse_Merriman)\ **Post date:** [17 June 2007 17:25 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/5 "2007-06-17T17:25:49Z")
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 [perms\_and\_combs.rb](https://rubytalk.org/uploads/short-url/dVD6cXRWwbYX9eM3DanYAjPBY2W.rb) (2.01 KB) [verbal\_arithmetic.rb](https://rubytalk.org/uploads/short-url/78115V5YwQSweouRwZEXt8VIHu9.rb) (4.61 KB) > **路路路** > > ------ > 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](mailto:jessemerriman@warpmail.net) > [http://www.jessemerriman.com/](http://www.jessemerriman.com/) ---
**Author:** ![Jesse\_Merriman](https://avatars.discourse-cdn.com/v4/letter/j/41988e/32.png) [@Jesse\_Merriman](https://rubytalk.org/u/Jesse_Merriman)\ **Post date:** [17 June 2007 17:27 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/6 "2007-06-17T17:27:22Z")
[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 [perms\_and\_combs.rb](https://rubytalk.org/uploads/short-url/dVD6cXRWwbYX9eM3DanYAjPBY2W.rb) (2.01 KB) [verbal\_arithmetic.rb](https://rubytalk.org/uploads/short-url/78115V5YwQSweouRwZEXt8VIHu9.rb) (4.61 KB) > **路路路** > > ------ > 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](mailto:jessemerriman@warpmail.net) > [http://www.jessemerriman.com/](http://www.jessemerriman.com/) ---
**Author:** ![Eric\_I2](https://avatars.discourse-cdn.com/v4/letter/e/22d042/32.png) [@Eric\_I2](https://rubytalk.org/u/Eric_I2)\ **Post date:** [17 June 2007 19:30 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/7 "2007-06-17T19:30:24Z")
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://LearnRuby.com](http://LearnRuby.com) > > ==== > > # 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) ---
**Author:** ![Justin\_Ethier](https://avatars.discourse-cdn.com/v4/letter/j/c67d28/32.png) [@Justin\_Ethier](https://rubytalk.org/u/Justin_Ethier)\ **Post date:** [18 June 2007 03:28 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/8 "2007-06-18T03:28:10Z")
Hello everyone, At the outset, I had no idea how difficult this problem would be. In fact, it turns out that this is actually an NP-complete problem if the number base is not fixed at 10. Anyway... Initially I experimented with a backtracking solution, but ran into trouble getting it to work properly. So for now I am submitting this solution. Although less than perfect, it does work for the test inputs, as well as additional solutions I have tried. The idea is to brute force a solution by trying all possible combinations of solutions until one works. For this solution, I used the Permutation Gem available here: [http://permutation.rubyforge.org/doc/index.html](http://permutation.rubyforge.org/doc/index.html) require 'Permutation' To avoid having to (re)write the combination code myself, I also used the Combinations class from: [http://butunclebob.com/ArticleS.UncleBob.RubyCombinations](http://butunclebob.com/ArticleS.UncleBob.RubyCombinations) This is great code, someone really should create a gem for it! (see link for the code) I packaged all of my code inside the following class: class VerbalArithmetic   # Parse given equation into lvalues (words on the left-hand side of the '=' that   # are to be added together) and an rvalue (the single word on the right-hand side)   def parse\_equation (equation)     lvalues = equation.split("+")     rvalue = lvalues[-1].split("=")     lvalues[-1] = rvalue[0] # Get last lvalue     rvalue = rvalue[1] # Get rvalue     return lvalues, rvalue   end   # Brute force a solution by trying all possible combinations   def find\_solution(lvalues, rvalue)     # Form a list of all letters     words = Marshal::load(Marshal::dump(lvalues))     words.push(rvalue)     letters = {}     words.each do |word|       word.split("").each do |letter|         letters[letter] = letter if letters[letter] == nil       end     end     # Format l/r values to ease solution analysis below     lvalues\_formatted =     lvalues.each {|lval| lvalues\_formatted.push(lval.reverse.split(""))}     rvalue\_formatted = rvalue.reverse.split("")     # For all unordered combinations of numbers...     for i in Combinations.get(10, letters.values.size)       # For all permutations of each combination...       perm = Permutation.for(i)       perm.each do |p|         # Map each combination of numbers to the underlying letters         map = {}         parry = p.project         for i in 0...letters.size           map[letters.values[i]] = parry[i]         end         # Does this mapping yield a solution?         if is\_solution?(lvalues\_formatted, rvalue\_formatted, map)           return map         end       end     end     nil   end   # Determines if the given equation may be solved by   # substituting the given number for its letters   def is\_solution?(lvalues, rvalue, map)     # Make sure there are no leading zero's     for lval in lvalues       return false if map[lval[-1]] == 0     end     return false if map[rvalue[-1]] == 0     # Perform arithmetic using the mappings, and make sure they are valid     remainder = 0     for i in 0...rvalue.size       lvalues.each do |lval|         remainder = remainder + map[lval[i]] if map[lval[i]] != nil # Sum values       end       return false if (remainder % 10) != map[rvalue[i]] # Validate digit       remainder = remainder / 10 # Truncate value at this place     end     true   end end Finally, this code puts everything together: va = VerbalArithmetic.new lvalues, rvalue = va.parse\_equation("send+more=money") map = va.find\_solution(lvalues, rvalue) puts "Solution: ", map if map != nil And here is the output: Solution: m1n6y2d7o0e5r8s9 Thanks, Justin > **路路路** > > On 6/15/07, Ruby Quiz \ wrote: > > > 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/](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 ---
**Author:** ![Glen\_F\_Pankow](https://avatars.discourse-cdn.com/v4/letter/g/0ea827/32.png) [@Glen\_F\_Pankow](https://rubytalk.org/u/Glen_F_Pankow)\ **Post date:** [18 June 2007 11:33 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/9 "2007-06-18T11:33:03Z")
#! /usr/bin/env ruby > **路路路** > > # > # quiz-128 -- Ruby Quiz #128 -- Verbal Arithmetic. > # > # Usage: quiz-128 [-v] '\' > # or: quiz-128 [-v] \ \ [\ ...] \ > # > # See the Ruby Quiz #128 documentation for more information > # ([http://www.rubyquiz.com/quiz128.html](http://www.rubyquiz.com/quiz128.html)). > # > # Glen Pankow 06/17/07 Original version. > # > # Licensed under the Ruby License. > # > #----------------------------------------------------------------------------- > # > # I take a slightly different approach to this quiz: I build up code that > # kinda-sorta models addition as taught in U.S. elementary schools (taking > # into account the various constraints of the problem), then eval it. > # > # And instead of generating permutations of unassigned digits and using > # recursion for backtracking, I have a single array of digits that is used > # sort of as a mask (nil entries mark assigned digits) and use Ruby's > # wonderful magic iterator facility to scan through it. > # > # $ uname -srmpio > # Linux 2.6.9-55.ELsmp i686 i686 i386 GNU/Linux > # > # $ time ./quiz-128 'send + more = money' > # d = 7, e = 5, y = 2, n = 6, r = 8, o = 0, s = 9, m = 1 > # 1 0 1 1 > # s:9 e:5 n:6 d:7 > # + m:1 o:0 r:8 e:5 > # --------------------- > # m:1 o:0 n:6 e:5 y:2 > # 0.065u 0.003s 0:00.07 85.7% 0+0k 0+0io 0pf+0w > # > # $ time ./quiz-128 forty ten ten sixty > # y = 6, n = 0, t = 8, e = 5, r = 7, x = 4, o = 9, i = 1, f = 2, s = 3 > # 1 2 1 0 > # f:2 o:9 r:7 t:8 y:6 > # t:8 e:5 n:0 > # + t:8 e:5 n:0 > # --------------------- > # s:3 i:1 x:4 t:8 y:6 > # 0.029u 0.002s 0:00.03 66.6% 0+0k 0+0io 0pf+0w > # > # $ time ./quiz-128 eat+that=apple > # t = 9, e = 8, a = 1, l = 3, h = 2, p = 0 > # 1 1 0 1 > # e:8 a:1 t:9 > # + t:9 h:2 a:1 t:9 > # --------------------- > # a:1 p:0 p:0 l:3 e:8 > # 0.008u 0.002s 0:00.01 0.0% 0+0k 0+0io 0pf+0w > # > # $ time ./quiz-128 ruby rubber baby buggy bumper > # y = 0, r = 7, b = 8, e = 1, g = 4, u = 2, a = 3, p = 9, m = 6 > # ... > # y = 0, r = 7, b = 8, e = 5, g = 4, u = 2, a = 3, p = 9, m = 6 > # 1 2 1 2 0 > # r:7 u:2 b:8 y:0 > # r:7 u:2 b:8 b:8 e:5 r:7 > # b:8 a:3 b:8 y:0 > # + b:8 u:2 g:4 g:4 y:0 > # ------------------------- > # b:8 u:2 m:6 p:9 e:5 r:7 > # 0.120u 0.002s 0:00.13 92.3% 0+0k 0+0io 0pf+0w > # > > class Array > >     # >     # For each non-nil element of the current array, (destructively) set it to >     # nil (i.e., 'marking' it), yield the original value (to the assumed block), >     # and restore it back to what it originally was (i.e., 'unmarking' it). >     # >     # For example, the code: >     # array = [0, nil, 2, 3] >     # p "before: array = #{array.inspect}" >     # array.unmarkeds { |elem| p "elem = #{elem}, array = #{array.inspect}" } >     # p "after: array = #{array.inspect}" >     # would print: >     # before: array = [0, nil, 2, 3] >     # elem = 0, array = [nil, nil, 2, 3] >     # elem = 2, array = [0, nil, nil, 3] >     # elem = 3, array = [0, nil, 2, nil] >     # after: array = [0, nil, 2, 3] >     # >     def unmarkeds >         (0...size).each do |i| >             next if (at(i).nil?) >             elem = at(i) ; self[i] = nil >             yield elem >             self[i] = elem >         end >     end > >     # >     # If the \-th element of the current array is nil, do nothing. Otherwise >     # (destructively) set it to nil (i.e., 'marking' it), yield (to the assumed >     # block), and restore it back to what it originally was (i.e., 'unmarking' >     # it). This is basically the guts of unmarkeds(), and is provided for safe >     # manual element marking. >     # >     def if\_unmarked(i) >         return if (at(i).nil?) >         elem = at(i) ; self[i] = nil >         yield >         self[i] = elem >     end > >     # >     # Note: typically one might say 'yield elem, self' in these methods, but >     # I don't need them for this application due to Ruby's scoping mechanism. >     # > end > > # > # Process the command-line arguments of addend strings and the sum string. > # > verbose = false > addend\_strs = [] > ARGV.each do |arg| >     if (arg == '-v') >         verbose = true >     else >         arg.split(/[\s+=]+/).each { |term| addend\_strs \<\< term } >     end > end > addend\_strs = ['send', 'more', 'money'] if (addend\_strs.empty?) > sum\_str = addend\_strs.pop > > # > # Split the strings up into their component letters; create some (ugly) code to > # eventually print out a nice table of the addition. > # > table\_print\_code = 'print " ' > (sum\_str.length - 1).downto(1) do |i| >     table\_print\_code \<\< " \#{carry#{i}}" > end > table\_print\_code \<\< "\\n\"\n" > addends = [] > first\_letters = { } > (0...addend\_strs.size).each do |i| >     addend\_str = addend\_strs[i] >     addend\_chars = addend\_str.split(//).reverse >     addends \<\< addend\_chars >     first\_letters[addend\_chars[-1]] = 1 >     table\_print\_code \ >       \<\< 'print "' \<\< ((i \< addend\_strs.size - 1)? ' ' : '+') \ >       \<\< ' ' \* (sum\_str.length - addend\_str.length) \ >       \<\< addend\_str.gsub(/([a-z])/, ' \1:#{\1}') \<\< "\\n\"\n" > end > table\_print\_code \ >   \<\< 'print "-' \<\< ('----' \* sum\_str.length) \<\< "\\n\"\n" \ >   \<\< 'print " ' \<\< sum\_str.gsub(/([a-z])/, ' \1:#{\1}') \<\< "\\n\"\n" > sum\_chars = sum\_str.split(//).reverse > first\_letters[sum\_chars[-1]] = 1 > > # > # Build the addition code. > # > # This, too, is quite ugly and I don't bother to document it, as printing out > # the generated code will probably give one a better idea of how it works than > # my usual verbose documentation (i.e., run this script with -v). > # > seen\_chars = { } > code\_head = "rem\_digs = (0..9).to\_a\n" > code\_tail = '' > answer\_print\_code = 'print "' > indent = '' > (0...sum\_chars.size).each do |col| >     sum\_char = sum\_chars[col] >     col\_sum\_code = "#{indent}carry#{col+1}, #{sum\_char} = (carry#{col}" >     addends.inject([]) { |dc, addend| dc \<\< addend[col] }.each do |dig\_char| >         next if (dig\_char.nil?) >         if (seen\_chars[dig\_char].nil?) >             code\_head \<\< "#{indent}rem\_digs.unmarkeds do |#{dig\_char}|\n" >             code\_tail[0,0] = "#{indent}end\n" >             indent \<\< ' ' >             seen\_chars[dig\_char] = 1 >             code\_head \<\< "#{indent}next if (#{dig\_char} == 0) # leading 0?\n" \ >               if (first\_letters.has\_key?(dig\_char)) >             col\_sum\_code[0,0] = ' ' # fix indentation >             answer\_print\_code \<\< ", #{dig\_char} = \#{#{dig\_char}}" >         end >         col\_sum\_code \<\< " + #{dig\_char}" >     end >     col\_sum\_code \<\< ").divmod(10)\n" >     col\_sum\_code.sub!(/\(carry0 \+ /, '(') >     if (seen\_chars[sum\_char].nil?) >         code\_head \<\< col\_sum\_code >         code\_head \<\< "#{indent}next if (#{sum\_char} == 0) # leading 0?\n" \ >           if (first\_letters.has\_key?(sum\_char)) >         code\_head \<\< "#{indent}rem\_digs.if\_unmarked(#{sum\_char}) do\n" >         code\_tail[0,0] = "#{indent}end\n" >         indent \<\< ' ' >         seen\_chars[sum\_char] = 1 >         answer\_print\_code \<\< ", #{sum\_char} = \#{#{sum\_char}}" >     else >         col\_sum\_code.sub!(/ = /, '2 = ') >         code\_head \ >           \<\< col\_sum\_code \ >           \<\< "#{indent}next unless (#{sum\_char}2 == #{sum\_char}) # inconsistent?\n" >     end > end > answer\_print\_code.sub!(/\", /, '"\n') > answer\_print\_code \<\< "\\n\"\n" > > # > # And print out the code (if verbose) and run it! > # > code = code\_head + answer\_print\_code + table\_print\_code + code\_tail > print code, "\n" if (verbose) > eval(code) ---
**Author:** ![Morton\_Goldberg](https://avatars.discourse-cdn.com/v4/letter/m/7ea924/32.png) [@Morton\_Goldberg](https://rubytalk.org/u/Morton_Goldberg)\ **Post date:** [18 June 2007 14:55 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/10 "2007-06-18T14:55:32Z")
Here is my solution for Ruby Quiz 128. It's a little rough, but I can't afford to spend any more time working on it. One thing I didn't have time to do was to provide a user interface. Another thing I didn't do was proper commenting. I apologize for the latter. I thought a Darwinian search (aka genetic algorithm) would be an interesting way to tackle this quiz. I have been looking for a excuse to write such a search in Ruby for quite awhile and this seemed to be it. Here are is the output from one run of my quiz solution: \ Solution found after 15 steps SEND+MORE=MONEY 9567+1085=10652 Solution found after 27 steps FORTY+TEN+TEN=SIXTY 29786+850+850=31486 \ And here is the code: \ #! /usr/bin/env ruby -w > **路路路** > > # > # solution.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > > # Assumption: equations take the form: term + term + ... term = sum > > ROOT\_DIR = File.dirname(\_\_FILE\_\_) > $LOAD\_PATH \<\< File.join(ROOT\_DIR, "lib") > > require "cryptarithm" > require "solver" > > EQUATION\_1 = "SEND+MORE=MONEY" > EQUATION\_2 = "FORTY+TEN+TEN=SIXTY" > POP\_SIZE = 400 > FECUNDITY = 2 > STEPS = 50 > > Cryptarithm.equation(EQUATION\_1) > s = Solver.new(POP\_SIZE, FECUNDITY, STEPS) > s.run > puts s.show > > Cryptarithm.equation(EQUATION\_2) > s = Solver.new(POP\_SIZE, FECUNDITY, STEPS) > s.run > puts s.show > \ > > And here are the library classes: > > \ > # lib/cryptarithm.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > > DIGITS = (0..9).to\_a > > class Cryptarithm >     @@equation = "" >     @@max\_rank = -1 >     def self.equation(str=nil) >        if str >           @@equation = str.upcase >           lhs, rhs = @@equation.gsub(/[A-Z]/, "9").split("=") >           @@max\_rank = [eval(lhs), eval(rhs)].max >        else >           @@equation >        end >     end >     attr\_accessor :ranking, :solution >     def initialize >        @solution = @@equation.delete("+-=").split("").uniq >        @solution = @solution.zip((DIGITS.sort\_by {rand})[0, @solution.size]) >        rank >     end >     def mutate(where=rand(@solution.size)) >        raise RangeError unless (0...@solution.size).include?(where) >        digits = @solution.collect { |pair| pair[1] } >        digits = DIGITS - digits >        return if digits.empty? >        @solution[where][1] = digits[rand(digits.size)] >     end >     def swap >        m = rand(@solution.size) >        n = m >        while n == m >           n = rand(@solution.size) >        end >        @solution[m][1], @solution[n][1] = @solution[n][1], @solution[m][1] >     end >     def rank >        sum = @@equation.dup >        solution.each { |chr, num| sum.gsub!(chr, num.to\_s) } >        lhs, rhs = sum.split("=") >        terms = lhs.split("+") \<\< rhs >        if terms.any? { |t| t[0] == ?0 } >           @ranking = @@max\_rank >        else >           @ranking = eval("#{lhs} - #{rhs}").abs >        end >     end >     def initialize\_copy(original) >        @solution = original.solution.collect { |pair| pair.dup } >     end >     def inspect >        [@ranking, @solution].inspect >     end >     def to\_s >        sum = @@equation.dup >        solution.each { |chr, num| sum.gsub!(chr, num.to\_s) } >        "#{@@equation}\n#{sum}" >     end > end > \ > > \ > # lib/solver.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > # > # Attempts to a solve cryptarithm puzzle by applying a Darwinian search > # (aka genetic algorithm). It can thought of as a stochastic breadth-first > # search. Although this method doesn't guarantee a solution will be > # found, it often finds one quite quickly. > > MUTATION = 0.5 > SWAP = 1.0 > > class Solver >     attr\_reader :best, :population, :step >     def initialize(pop\_size, fecundity, steps) >        @pop\_size = pop\_size >        @fecundity = fecundity >        @steps = steps >        @mid\_step = steps / 2 >        @step = 1 >        @population = [] >        @pop\_size.times { @population \<\< Cryptarithm.new } >        select >     end >     def run >        @steps.times do >           replicate >           select >           break if @best.rank.zero? >           @step += 1 >        end >        @best >     end >     def replicate >        @pop\_size.times do |n| >           crypt = @population[n] >           # mate = crypt >           # while mate.equal?(crypt) >           # mate = @population[rand(@pop\_size)] >           # end >           @fecundity.times do >              child = crypt.dup >              child.mutate if crypt.solution.size \< 10 && rand \<= MUTATION >              child.swap if rand \<= SWAP >              @population \<\< child >           end >        end >     end >     def select >        @population = @population.sort\_by { |crypt| crypt.rank } >        @population = @population[0, @pop\_size] >        @best = @population.first >     end >     def show >        if @step \> @steps >           "No solution found after #{step} steps" >        else >           "Solution found after #{step} steps\n" + @best.to\_s >        end >     end > end > \ > > Regards, Morton ---
**Author:** ![Eric\_I2](https://avatars.discourse-cdn.com/v4/letter/e/22d042/32.png) [@Eric\_I2](https://rubytalk.org/u/Eric_I2)\ **Post date:** [18 June 2007 16:45 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/11 "2007-06-18T16:45:02Z")
If anyone would like more samples to try their code with, I found the following on the web: \* [http://www.gtoal.com/wordgames/alphametic/testscript](http://www.gtoal.com/wordgames/alphametic/testscript) \* [http://www.gtoal.com/wordgames/alphametic/testscript.out](http://www.gtoal.com/wordgames/alphametic/testscript.out) The first is a script which poses the problems to their own solving- program. The second shows the solutions that their program produces. Some of the sample equations have multiple solutions, such as 'eins +eins=zwei'. 'united+states=america' has no solutions. And of the few that I've tested with my own solution, 'saturn+pluto+uranus +neptune=planets' takes the longest to solve. Eric > **路路路** > > ---- > Interested in hands-on, on-site Ruby training? See [http://LearnRuby.com](http://LearnRuby.com) > for information about a well-reviewed class. ---
**Author:** ![Morton\_Goldberg](https://avatars.discourse-cdn.com/v4/letter/m/7ea924/32.png) [@Morton\_Goldberg](https://rubytalk.org/u/Morton_Goldberg)\ **Post date:** [19 June 2007 04:39 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/12 "2007-06-19T04:39:30Z")
Sorry for the second post, but I just noticed that I pasted a wrong (earlier) version of solver.rb into my first post. This is what I intended to post. The difference between the two versions is minor, but this version eliminates some commented-out experimental code and corrects a minor bug. Sample output: \ Solution found after 15 steps SEND+MORE=MONEY 9567+1085=10652 Solution found after 27 steps FORTY+TEN+TEN=SIXTY 29786+850+850=31486 \ And here is the corrected code: \ #! /usr/bin/env ruby -w > **路路路** > > # > # solution.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > > # Assumption: equations take the form: term + term + ... term = sum > > ROOT\_DIR = File.dirname(\_\_FILE\_\_) > $LOAD\_PATH \<\< File.join(ROOT\_DIR, "lib") > > require "cryptarithm" > require "solver" > > EQUATION\_1 = "SEND+MORE=MONEY" > EQUATION\_2 = "FORTY+TEN+TEN=SIXTY" > POP\_SIZE = 400 > FECUNDITY = 2 > STEPS = 50 > > Cryptarithm.equation(EQUATION\_1) > s = Solver.new(POP\_SIZE, FECUNDITY, STEPS) > s.run > puts s.show > > Cryptarithm.equation(EQUATION\_2) > s = Solver.new(POP\_SIZE, FECUNDITY, STEPS) > s.run > puts s.show > \ > > And here are the library classes: > > \ > # lib/cryptarithm.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > > DIGITS = (0..9).to\_a > > class Cryptarithm >     @@equation = "" >     @@max\_rank = -1 >     def self.equation(str=nil) >        if str >           @@equation = str.upcase >           lhs, rhs = @@equation.gsub(/[A-Z]/, "9").split("=") >           @@max\_rank = [eval(lhs), eval(rhs)].max >        else >           @@equation >        end >     end >     attr\_accessor :ranking, :solution >     def initialize >        @solution = @@equation.delete("+-=").split("").uniq >        @solution = @solution.zip((DIGITS.sort\_by {rand})[0, @solution.size]) >        rank >     end >     def mutate(where=rand(@solution.size)) >        raise RangeError unless (0...@solution.size).include?(where) >        digits = @solution.collect { |pair| pair[1] } >        digits = DIGITS - digits >        return if digits.empty? >        @solution[where][1] = digits[rand(digits.size)] >     end >     def swap >        m = rand(@solution.size) >        n = m >        while n == m >           n = rand(@solution.size) >        end >        @solution[m][1], @solution[n][1] = @solution[n][1], @solution[m][1] >     end >     def rank >        sum = @@equation.dup >        solution.each { |chr, num| sum.gsub!(chr, num.to\_s) } >        lhs, rhs = sum.split("=") >        terms = lhs.split("+") \<\< rhs >        if terms.any? { |t| t[0] == ?0 } >           @ranking = @@max\_rank >        else >           @ranking = eval("#{lhs} - #{rhs}").abs >        end >     end >     def initialize\_copy(original) >        @solution = original.solution.collect { |pair| pair.dup } >        rank >     end >     def inspect >        [@ranking, @solution].inspect >     end >     def to\_s >        sum = @@equation.dup >        solution.each { |chr, num| sum.gsub!(chr, num.to\_s) } >        "#{@@equation}\n#{sum}" >     end > end > \ > > \ > # lib/solver.rb > # Quiz 128 > # > # Created by Morton Goldberg on 2007-06-18. > # > # Attempts to a solve cryptarithm puzzle by applying a Darwinian search > # (aka genetic algorithm). It can thought of as a stochastic breadth-first > # search. Although this method doesn't guarantee a solution will be > # found, it often finds one quite quickly. > > MUTATION = 0.5 > SWAP = 1.0 > > class Solver >     attr\_reader :best, :population, :step >     def initialize(pop\_size, fecundity, steps) >        @pop\_size = pop\_size >        @fecundity = fecundity >        @steps = steps >        @mid\_step = steps / 2 >        @step = 1 >        @population = [] >        @pop\_size.times { @population \<\< Cryptarithm.new } >        select >     end >     def run >        @steps.times do >           replicate >           select >           break if @best.ranking.zero? >           @step += 1 >        end >        @best >     end >     def replicate >        @pop\_size.times do |n| >           crypt = @population[n] >           @fecundity.times do >              child = crypt.dup >              child.mutate if crypt.solution.size \< 10 && rand \<= MUTATION >              child.swap if rand \<= SWAP >              @population \<\< child >           end >        end >     end >     def select >        @population = @population.sort\_by { |crypt| crypt.rank } >        @population = @population[0, @pop\_size] >        @best = @population.first >     end >     def show >        if @step \> @steps >           "No solution found after #{step} steps" >        else >           "Solution found after #{step} steps\n" + @best.to\_s >        end >     end > end > \ > > Regards, Morton ---
**Author:** ![Andreas\_Launila](https://avatars.discourse-cdn.com/v4/letter/a/dbc845/32.png) [@Andreas\_Launila](https://rubytalk.org/u/Andreas_Launila)\ **Post date:** [19 June 2007 18:47 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/13 "2007-06-19T18:47:18Z")
Ruby Quiz wrote: > 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. This solution requires Gecode/R[1] 0.2.0 (need to install Gecode[3,4] followed by Gecode/R[2]). Gecode does the actual search, so we just specify the constraints. Two important aspects that are used to make the solution quick to compute are: == Propagation rather than branching (deduction rather than exploration) Branching (i.e. testing a guess, i.e. exploring the search space) costs since we have to save the old state and start a new one. Rather Gecode tries to prune as much of the search space as it can before resorting to exploration. In the case of linear constraints (e.g. a + 10\*b + c= 10\*d + e, which corresponds to the problem    a + bc > **路路路** > > ---- >   de > > ) it takes each variable and considers the smallest and largest values > it can possibly take. E.g. if we consider a in the above example we can > rewrite the linear equation to > > a = 10\*(d - b) + e - c > > From that equation we can check how large and small the right hand side > can be and then remove all other possibilities from the domain of a. We > can end up pruning quite a lot if we do this for each variable until > there are no more possibilities left to remove (coupled with the > distinct constraint). > > In fact when we use this for send+more=money, without doing any sort of > exploration we can directly reduce the domains of the variables down to > > s=9, e=4..7, n=5..8, d=2..8, m=1, o=0, r=2..8, y=2..8 > > So without any guessing at all we already know the value of three > letters and have pruned the domains of the others (i.e. pruned the > number of possibilities left, i.e. reduced the search space). > > Since we now have to start exploring the search space we make a guess > that e=4. Propagating the constraints once again with e given the domain > 4 will directly result in a failure, so we backtrack and now know that > e!=4. With that information we redo the propagation and directly end up > at the solution with no need to explore any further. So in total we only > need to explore 4 out of 9^2\*10^6 nodes in the search space. > > == Branching with a good heuristic > > We don't randomly select where to go next in the search space, rather we > use a fail-first heuristic to try to cut down the search space faster. > The heuristic is to simply try to fixate a value for the variable with > the smallest domain. The reason that it works well is that we exhaust > domains quicker, hence forcing failures quicker (hence fail-first) > > == The code > > require 'rubygems' > require 'gecoder' > > # Solves verbal arithmetic problems > # ( [Verbal arithmetic - Wikipedia](http://en.wikipedia.org/wiki/Verbal_arithmetic) ). Only supports > # addition. > class VerbalArithmetic \< Gecode::Model >   # Creates a model for the problem where the left and right hand sides >   # are given as an array with one element per term. The terms are given >   # as strings >   def initialize(lhs\_terms, rhs\_terms) >     super() > >     # Set up the variables needed as a hash mapping the letter to its >     # variable. >     lhs\_terms.map!{ |term| term.split(//) } >     rhs\_terms.map!{ |term| term.split(//) } >     all\_terms = (lhs\_terms + rhs\_terms) >     unique\_letters = all\_terms.flatten.uniq >     letter\_vars = int\_var\_array(unique\_letters.size, 0..9) >     @letters = Hash[\*unique\_letters.zip(letter\_vars).flatten!] > >     # Must satisfy the equation. >     sum\_terms(lhs\_terms).must == sum\_terms(rhs\_terms) > >     # Must be distinct. >     letter\_vars.must\_be.distinct > >     # Must not begin with a 0. >     all\_terms.map{ |term| term.first }.uniq.each do |letter| >       @letters[letter].must\_not == 0 >     end > >     # Select a branching, we go for fail first. >     branch\_on letter\_vars, :variable =\> :smallest\_size, :value =\> :min >   end > >   def to\_s >     @letters.map{ |letter, var| "#{letter}: #{var.val}" }.join("\n") >   end > >   private > >   # A helper to make the linear equation a bit tidier. Takes an array of >   # variables and computes the linear combination as if the variable >   # were digits in a base 10 number. E.g. x,y,z becomes >   # 100\*x + 10\*y + z . >   def equation\_row(variables) >     variables.inject{ |result, variable| variable + result\*10 } >   end > >   # Computes the sum of the specified terms (given as an array of arrays >   # of characters). >   def sum\_terms(terms) >     rows = terms.map{ |term| equation\_row(@letters.values\_at(\*term)) } >     rows.inject{ |sum, term| sum + term } >   end > end > > if ARGV.empty? >   abort "Usage: #{$0} '\+\+...+\=\'" > end > lhs, rhs = ARGV[0].split('=').map{ |eq\_side| eq\_side.split('+') } > solution = VerbalArithmetic.new(lhs, rhs).solve! > if solution.nil? >   puts 'Failed' > else >   puts solution.to\_s > end > > [1] [http://gecoder.rubyforge.org/](http://gecoder.rubyforge.org/) > [2] [http://gecoder.rubyforge.org/installation.html](http://gecoder.rubyforge.org/installation.html) > [3] [GECODE download](http://www.gecode.org/download.html) > [4] [http://www.gecode.org/gecode-doc-latest/PageComp.html](http://www.gecode.org/gecode-doc-latest/PageComp.html) > > -- > Andreas Launila ---
**Author:** ![Bob\_Showalter1](https://avatars.discourse-cdn.com/v4/letter/b/7ab992/32.png) [@Bob\_Showalter1](https://rubytalk.org/u/Bob_Showalter1)\ **Post date:** [20 June 2007 13:13 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/14 "2007-06-20T13:13:44Z")
Here's my solution: [http://pastie.caboo.se/72030](http://pastie.caboo.se/72030) It's a brute-force search, but has reasonable speed. +, -, and \* operators are supported. > **路路路** > > On 6/15/07, Ruby Quiz \ wrote: > > > 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. ---
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [15 June 2007 12:57 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/15 "2007-06-15T12:57:34Z")
Well, a non-clever way is to try an exhaustive search of each digit for each letter. James Edward Gray II > **路路路** > > 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? ---
**Author:** ![darren\_kirby](https://avatars.discourse-cdn.com/v4/letter/d/ed8c4c/32.png) [@darren\_kirby](https://rubytalk.org/u/darren_kirby)\ **Post date:** [17 June 2007 00:08 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/16 "2007-06-17T00:08:41Z")
quoth the Aureliano Calvo: > When can I send my solution to be > reviewed? I think about 12 hours from now... -d > **路路路** > > -- > darren kirby :: Part of the problem since 1976 :: [http://badcomputer.org](http://badcomputer.org) > "...the number of UNIX installations has grown to 10, with more expected..." > - Dennis Ritchie and Ken Thompson, June 1972 ---
**Author:** ![Aureliano\_Calvo](https://avatars.discourse-cdn.com/v4/letter/a/f04885/32.png) [@Aureliano\_Calvo](https://rubytalk.org/u/Aureliano_Calvo)\ **Post date:** [17 June 2007 15:11 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/17 "2007-06-17T15:11:42Z")
Well, I think I can send it now. My implementation is on [http://pastie.caboo.se/71198\](http://pastie.caboo.se/71198%5C). > **路路路** > > On 6/16/07, Aureliano Calvo \ wrote: > > > Mi implementation is "working". For instance: > > > > ./quiz\_128.rb "a+b=c" > > a: 5 > > b: 1 > > c: 6 > > > > But > > ./quiz\_128.rb "send+more=money" is taking ages! > > > > time ./quiz\_128.rb "send+more=money" > > m: 1 > > y: 2 > > n: 6 > > o: 0 > > d: 7 > > e: 5 > > r: 8 > > s: 9 > > > > real 7m17.065s > > user 2m46.806s > > sys 0m6.676s > > > > Is there some trick to cut the solution space (I'm just scanning the > > solution space) ? I know I have a crappy PC but I have a feeling that > > this is not the real problem! When can I send my solution to be > > reviewed? > > > > \> 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/](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 > > \> > > > > -- > > "Es tambi茅n nuestra intenci贸n erradicar la corrupci贸n, ofreciendo como > > norma la honestidad, la idoneidad y la eficiencia. Con madurez y > > sentido de unidad es f谩cil pensar en la recomposici贸n del ser > > argentino. Ese ser argentino, basado en madurez y en sentido de > > unidad, permitir谩 inspirar para elevarnos por encima de la miseria que > > la antinomia nos ha planteado, para dejar, de una vez por todas, ese > > ser "anti" y ser, de una vez por todas, "pro": "Pro argentinos"" > > > > Jorge Rafael Videla para el 25 de mayo de 1976 > > -- > "Es tambi茅n nuestra intenci贸n erradicar la corrupci贸n, ofreciendo como > norma la honestidad, la idoneidad y la eficiencia. Con madurez y > sentido de unidad es f谩cil pensar en la recomposici贸n del ser > argentino. Ese ser argentino, basado en madurez y en sentido de > unidad, permitir谩 inspirar para elevarnos por encima de la miseria que > la antinomia nos ha planteado, para dejar, de una vez por todas, ese > ser "anti" y ser, de una vez por todas, "pro": "Pro argentinos"" > > Jorge Rafael Videla para el 25 de mayo de 1976 ---
**Author:** ![Holger](https://avatars.discourse-cdn.com/v4/letter/h/ed8c4c/32.png) [@Holger](https://rubytalk.org/u/Holger)\ **Post date:** [17 June 2007 17:17 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/18 "2007-06-17T17:17:45Z")
Hello, here is my solution for the arithmetic quiz. I am a ruby beginner and this is my first ruby program (ok, my second one, the first was "puts 'hello world'"). So please forgive me the dirty trick using eval (why build an own parser if ruby provides such a fine solution?). I build in a brute force search algorithm via an iterative method for permutations. Therefore, any valid ruby expression is allowed, e.g. verbal\_arithmetic.rb 'a+b==c && a+c==d-b && a\*c==d' solving a\*b\*c\*d!=0 && a+b==c && a+c==d-b && a\*c==d -- Solution --- b: 1 c: 3 d: 6 Please feel free to send any comments. Regards Holger #!/usr/bin/ruby -w > **路路路** > > a: 2 > > # > # Solution to ruby quiz #128 > # [http://www.rubyquiz.com/quiz128.html](http://www.rubyquiz.com/quiz128.html) > # by Holger > # > # Usage: > # verbal\_arithmetic.rb \ > # > # Examples: > # verbal\_arithmetic.rb 'send+more=money' > # verbal\_arithmetic.rb 'a+b==c && a+c==d-b && a\*c==d' > # > > #\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* > # Permutator which gives all combinations of \ elements out of > # array \ > # > # usage: > # perms(m, n) { |x| ... } > # > #\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* > > def perms(m, n) >   p = [nil] \* m >   t = [-1] \* m >   k = 0 >   while k \>= 0 >     if k==m >       yield p >       k = k-1 >     end >     n[t[k]] = p[k] if t[k]\>=0 >     while(t[k]\       t[k] = t[k]+1 >       if n[t[k]] >         p[k] = n[t[k]] >         n[t[k]] = nil >         k = k+1 >         t[k] = -1 >         break >       end >     end >     k = k-1 if t[k]==n.length() >   end > end > > # Read from command line and make valid ruby expression (= -\> == if not > already present) > puzzle = ARGV[0].gsub(/=+/,"==") > > # Extract all letters and all first letters > digits = puzzle.gsub(/\W/,"").split(//).uniq > starts = puzzle.gsub(/(\w)\w\*|\W/,"\\1").split(//).uniq > > if digits.length()\>= 10 >   puts "oops, too much letters" > else >   # String containing all digits >   digitss = digits.join > >   # Build "first digit must not be zero" condition >   cond0 = starts.join("\*") + "!=0" > >   # And now perform an exhaustive search >   puts "solving #{cond0} && #{puzzle}" > >   perms(digits.length(), (0...10).to\_a) { |v| >     p0 = [cond0.tr](http://cond0.tr)(digitss, v.join) >     p1 = [puzzle.tr](http://puzzle.tr)(digitss, v.join) >     if eval(p0) && eval(p1) # Hint: first evaluate p0 as p1 may not be a > valid expression >       puts '-- Solution ---' >       [digits, v].transpose.each do |x,y| puts "#{x}: #{y}" end >     end >   } > end ---
**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\ **Post date:** [18 June 2007 23:59 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/19 "2007-06-18T23:59:49Z")
Mine was too: #!/usr/bin/env ruby -wKU EQUATION = ARGV.shift.to\_s.downcase.sub("=", "==") LETTERS = EQUATION.scan(/[a-z]/).uniq CHOICES = LETTERS.inject(Hash.new) do |all, letter|    all.merge(letter =\> EQUATION =~ /\b#{letter}/ ? 1..9 : 0..9) end def search(choices, mapping = Hash.new)    if choices.empty?      letters, digits = mapping.to\_a.flatten.partition { |e| e.is\_a? String }      return mapping if eval(EQUATION.tr(letters.join, digits.join))    else      new\_choices = choices.dup      letter = new\_choices.keys.first      digits = new\_choices.delete(letter).to\_a - mapping.values      digits.each do |choice|        if result = search(new\_choices, mapping.merge(letter =\> choice))          return result        end      end      return nil    end end if solution = search(CHOICES)    LETTERS.each { |letter| puts "#{letter}: #{solution[letter]}" } else    puts "No solution found." end \_\_END\_\_ James Edward Gray II > **路路路** > > On Jun 17, 2007, at 9:03 AM, Raf Coremans wrote: > > > Here's my solution: [http://pastie.caboo.se/71188](http://pastie.caboo.se/71188) > > > > It's of the dumb-brute-force-slow-as-hell variety: ---
**Author:** ![Andreas\_Launila](https://avatars.discourse-cdn.com/v4/letter/a/dbc845/32.png) [@Andreas\_Launila](https://rubytalk.org/u/Andreas_Launila)\ **Post date:** [19 June 2007 22:33 UTC](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379/20 "2007-06-19T22:33:39Z")
Andreas Launila wrote: > Since we now have to start exploring the search space we make a guess > that e=4. Propagating the constraints once again with e given the domain > 4 will directly result in a failure, so we backtrack and now know that > e!=4. With that information we redo the propagation and directly end up > at the solution with no need to explore any further. So in total we only > need to explore 4 out of 9^2\*10^6 nodes in the search space. The last part is probably a bit misleading/incorrect. We are not directly exploring the space of all possible assignments when we branch, so saying that we have explored 4 nodes in that space is incorrect (i.e. we have not just explored 4 possible assignments, but we have visited just 4 nodes in our search space). > **路路路** > > -- > Andreas Launila [Next page](https://rubytalk.org/t/quiz-verbal-arithmetic-128/38379.md?page=2)