# \[SUMMARY\] Verbal Arithmetic (#128)

**URL:** <https://rubytalk.org/t/summary-verbal-arithmetic-128/38508>\
**Category:** ruby-talk\
**Created:** [21 June 2007 12:49 UTC](https://rubytalk.org/t/summary-verbal-arithmetic-128/38508 "2007-06-21T12:49:55Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**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:** [21 June 2007 12:49 UTC](https://rubytalk.org/t/summary-verbal-arithmetic-128/38508/1 "2007-06-21T12:49:55Z")

</div>

I'm always impressed by the creativity of the solutions, but I think this week  
stands out even more than usual. I literally spent hours going through the  
solutions and learned some really great tricks from them. I wish I could take  
you on the same tour of the code, but that would take this summary into the  
range of a full text book in length.

Because I'm going to miss all of the following, let me point out some highlights  
for your own explorations:

&nbsp;&nbsp;\* Though the brute-force solutions are slow, most of them handle any  
&nbsp;&nbsp;&nbsp;&nbsp;math equations Ruby can. That is an interesting advantage.  
&nbsp;&nbsp;\* Andreas Launila sent in a fun preview of his Google Summer of Code  
&nbsp;&nbsp;&nbsp;&nbsp;project that looks to simplify many of these search problems we  
&nbsp;&nbsp;&nbsp;&nbsp;commonly use as quizzes.  
&nbsp;&nbsp;\* Glen's solution is a nifty metaprogramming solution that customizes  
&nbsp;&nbsp;&nbsp;&nbsp;itself to the equation entered. It's lightning quick too.  
&nbsp;&nbsp;\* Morton Goldberg solved the quiz with some genetic programming and  
&nbsp;&nbsp;&nbsp;&nbsp;that code is still quite a bit zippier than a brute-force search.

The solution I will show is from Eric I. It has an interesting state machine  
design that tries to fail fast in an attempt to aggressively prune the search  
space. It too finds solutions quite rapidly, though it only works for addition  
problems.

Eric's code breaks the equation down into a small series of steps. Instead of  
searching for a match for all numbers and then checking the result, this  
solution checks as many little sub-criteria as possible. Does just this column  
add up correctly, given what we know at this point? Is this digit a zero,  
because it starts a term somewhere else?

These smaller tests lead to failures that allow the search to skip large groups  
in the set of possible solutions. For example, if S can't be seven in just one  
column, it's impossible to have any scenario where S is seven and all such  
attempts can be safely skipped. That allows the code to zoom in on a correct  
answer faster.

Now that we understand the logic, let's start tackling the code:

&nbsp;&nbsp;require 'set'  
&nbsp;&nbsp;  
&nbsp;&nbsp;# State represents the stage of a partially solved word equation. It  
&nbsp;&nbsp;# keeps track of what digits letters map to, which digits have not yet  
&nbsp;&nbsp;# been assigned to letters, and the results of the last summed column,  
&nbsp;&nbsp;# including the resulting digit and any carry if there is one.  
&nbsp;&nbsp;class State  
&nbsp;&nbsp;&nbsp;&nbsp;attr\_accessor :sum, :carry  
&nbsp;&nbsp;&nbsp;&nbsp;attr\_reader :letters  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize()  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits = Set.new(0..9)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters = Hash.new  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@sum, @carry = 0, 0  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# Return digit for letter.  
&nbsp;&nbsp;&nbsp;&nbsp;def [](letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters[letter]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# The the digit for a letter.  
&nbsp;&nbsp;&nbsp;&nbsp;def []=(letter, digit)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# if the letter is currently assigned, return its digit to the  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# available set  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits.add @letters[letter] if @letters[letter]  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters[letter] = digit  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits.delete digit  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# Clear the digit for a letter.  
&nbsp;&nbsp;&nbsp;&nbsp;def clear(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits.add @letters[letter]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters[letter] = nil  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# Return the available digits as an array copied from the set.  
&nbsp;&nbsp;&nbsp;&nbsp;def available\_digits  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits.to\_a  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# Tests whether a given digit is still available.  
&nbsp;&nbsp;&nbsp;&nbsp;def available?(digit)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@available\_digits.member? digit  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# Receives the total for a column and keeps track of it as the  
&nbsp;&nbsp;&nbsp;&nbsp;# summed-to digit and any carry.  
&nbsp;&nbsp;&nbsp;&nbsp;def column\_total=(total)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@sum = total % 10  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@carry = total / 10  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This State object tracks progress through the equation, which will be solved  
column by column. It has operations to track what each letter is currently  
assigned to, assign letters as they are determined, examine which digits have  
and have not been used, and track the sum of the last column plus any value  
carried over to the next column. There's nothing too tricky in this data  
structure code.

What we need to go with this, is an algorithm that drives this State object to a  
solution. That code begins here:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# Step is an "abstract" base level class from which all the "concrete"  
&nbsp;&nbsp;# steps can be derived. It simply handles the storage of the next  
&nbsp;&nbsp;# step in the sequence. Subclasses should provide 1) a to\_s method to  
&nbsp;&nbsp;# describe the step being performed and 2) a perform method to  
&nbsp;&nbsp;# actually perform the step.  
&nbsp;&nbsp;class Step  
&nbsp;&nbsp;&nbsp;&nbsp;attr\_writer :next\_step  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This base Step is about as simple as things get. I merely provides a means of  
storing the next step in the process.

Note that this class's abstract status and the required implementation for  
subclasses are all handled through the documentation. That's perfectly  
reasonable in a dynamic language like Ruby where we can count on duck typing to  
resolve to the proper methods when the search is actually being performed.

Let's advance to a concrete implementation of the Step class:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step tries assigning each available digit to a given letter and  
&nbsp;&nbsp;# continuing from there.  
&nbsp;&nbsp;class ChooseStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letter = letter  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Choose a digit for \"#{@letter}\"."  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.available\_digits.each do |v|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state[@letter] = v  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_step.perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.clear(@letter)  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This ChooseStep handles the digit guessing. It is created for some letter and  
when perform() is triggered, it will try each unused in turn digit in that  
position. After a new guess is set, the ChooseStep just hands off to a later  
step to verify that the current guess works.

Here's another Step subclass:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step sums up the given letters and changes to state to reflect  
&nbsp;&nbsp;# the sum. Because we may have to backtrack, it stores the previous  
&nbsp;&nbsp;# saved sum and carry for later restoration.  
&nbsp;&nbsp;class SumColumnStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(letters)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters = letters  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list = @letters.map { |l| "\"#{l}\"" }.join(', ')  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Sum the column using letters #{list} (and include carry)."  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# save sum and carry  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;saved\_sum, saved\_carry = state.sum, state.carry  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.column\_total =  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.carry +  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letters.inject(0) { |sum, letter| sum + state[letter] }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_step.perform(state)  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# restore sum and carry  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.sum, state.carry = saved\_sum, saved\_carry  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This SumColumnStep will be added whenever guesses had been made for an entire  
column. It's job is to add up that column and update the State with this new  
total. You can see that it must save old State values and restore them when  
backtracking.

Once we know a column total, we can use that to set a letter from the solution  
side of the equation:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step determines the digit for a letter given the last column  
&nbsp;&nbsp;# summed. If the digit is not available, then we cannot continue.  
&nbsp;&nbsp;class AssignOnSumStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letter = letter  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Set the digit for \"#{@letter}\" based on last column summed."  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if state.available? state.sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state[@letter] = state.sum  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_step.perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.clear(@letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This AssignOnSumStep is added for letters in the solution of the equation. It  
will set the value of that letter to the calculated sum of the column, provided  
that is a legal non-duplicate digit choice.

When we have assigned that letter, we need to verify that the whole column makes  
sense mathematically:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step will occur after a column is summed, and the result must  
&nbsp;&nbsp;# match a letter that's already been assigned.  
&nbsp;&nbsp;class CheckOnSumStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letter = letter  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Verify that last column summed matches current " +  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"digit for \"#{@letter}\"."  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_step.perform(state) if state[@letter] == state.sum  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

Now, if we did all the guessing, summing, and assigning everything probably adds  
up. But as we continue through the equation, some numbers will already be  
filled in. Sums created using those may not balance with the total digit. This  
CheckOnSumStep watches for such a case.

If the sum doesn't check out, this class causes backtracking. Note that all it  
has to do is not forward to the following steps which will cause recursion to  
unwind the stack until it has another option.

One last check can trim the search space further:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step will occur after a letter is assigned to a digit if the  
&nbsp;&nbsp;# letter is not allowed to be a zero, because one or more terms begins  
&nbsp;&nbsp;# with that letter.  
&nbsp;&nbsp;class CheckNotZeroStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@letter = letter  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Verify that \"#{@letter}\" has not been assigned to zero."  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_step.perform(state) unless state[@letter] == 0  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This CheckNotZeroStep is used to ensure that a leading letter in a term is  
non-zero. Again, it fails to forward calls when this is not the case.

One more step is needed to catch correct solutions:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# This step represents finishing the equation. The carry must be zero  
&nbsp;&nbsp;# for the perform to have found an actual result, so check that and  
&nbsp;&nbsp;# display a digit -\> letter conversion table and dispaly the equation  
&nbsp;&nbsp;# with the digits substituted in for the letters.  
&nbsp;&nbsp;class FinishStep \< Step  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(equation)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@equation = equation  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Display a solution (provided carry is zero)!"  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def perform(state)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# we're supposedly done, so there can't be anything left in carry  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return unless state.carry == 0  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# display a letter to digit table on a single line  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;table = state.letters.invert  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts table.keys.sort.map { |k| "#{table[k]}=#{k}" }.join(' ')  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# display the equation with digits substituted for the letters  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;equation = @equation.dup  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state.letters.each { |k, v| equation.gsub!(k, v.to\_s) }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts equation  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This method first ensures that we are successful by validating that we have no  
remaining carry value. If that's true, our equation balanced out.

The rest of the work here is just in printing the found result. Nothing tricky  
there.

We're now ready to get into the application code:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# Do a basic test for the command-line arguments validity.  
&nbsp;&nbsp;unless ARGV[0] =~ Regexp.new('^[a-z]+(\+[a-z]+)\*=[a-z]+$')  
&nbsp;&nbsp;&nbsp;&nbsp;STDERR.puts "invalid argument"  
&nbsp;&nbsp;&nbsp;&nbsp;exit 1  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# Split the command-line argument into terms and figure out how many  
&nbsp;&nbsp;# columns we're dealing with.  
&nbsp;&nbsp;terms = ARGV[0].split(/\+|=/)  
&nbsp;&nbsp;column\_count = terms.map { |e| e.size }.max  
&nbsp;&nbsp;  
&nbsp;&nbsp;# Build the display of the equation a line at a time. The line  
&nbsp;&nbsp;# containing the final term of the sum has to have room for the plus  
&nbsp;&nbsp;# sign.  
&nbsp;&nbsp;display\_columns = [column\_count, terms[-2].size + 1].max  
&nbsp;&nbsp;display = []  
&nbsp;&nbsp;terms[0..-3].each do |term|  
&nbsp;&nbsp;&nbsp;&nbsp;display \<\< term.rjust(display\_columns)  
&nbsp;&nbsp;end  
&nbsp;&nbsp;display \<\< "+" + terms[-2].rjust(display\_columns - 1)  
&nbsp;&nbsp;display \<\< "-" \* display\_columns  
&nbsp;&nbsp;display \<\< terms[-1].rjust(display\_columns)  
&nbsp;&nbsp;display = display.join("\n")  
&nbsp;&nbsp;puts display  
&nbsp;&nbsp;  
&nbsp;&nbsp;# AssignOnSumStep which letters cannot be zero since they're the first  
&nbsp;&nbsp;# letter of a term.  
&nbsp;&nbsp;nonzero\_letters = Set.new  
&nbsp;&nbsp;terms.each { |e| nonzero\_letters.add(e[0, 1]) }  
&nbsp;&nbsp;  
&nbsp;&nbsp;# A place to keep track of which letters have so-far been assigned.  
&nbsp;&nbsp;chosen\_letters = Set.new  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This code validates the input and breaks it into terms. After that, the big  
chunk of code here displays the equation in a pretty format, like the examples  
from the quiz description.

The rest of the code begins to divide up the input as needed to build the proper  
steps. The first tactic is to locate and letters that must be nonzero, because  
they start a term. A set is also prepared to hold letters that have be given  
values at any point in the process.

Here's the heart of the process code:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# Build up the steps needed to solve the equation.  
&nbsp;&nbsp;steps = []  
&nbsp;&nbsp;column\_count.times do |column|  
&nbsp;&nbsp;&nbsp;&nbsp;index = -column - 1  
&nbsp;&nbsp;&nbsp;&nbsp;letters = [] # letters for this column to be added  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;terms[0..-2].each do |term| # for each term that's being added...  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;letter = term[index, 1]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next if letter.nil? # skip term if no letter in column  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;letters \<\< letter # note that this letter is part of sum  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# if the letter does not have a digit, create a ChooseStep  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;unless chosen\_letters.member? letter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< ChooseStep.new(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chosen\_letters.add(letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< CheckNotZeroStep.new(letter) if  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nonzero\_letters.member? letter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# create a SumColumnStep for the column  
&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< SumColumnStep.new(letters)  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;summed\_letter = terms[-1][index, 1] # the letter being summed to  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# check whether the summed to letter should already have a digit  
&nbsp;&nbsp;&nbsp;&nbsp;if chosen\_letters.member? summed\_letter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# should already have a digit, check that summed digit matches it  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< CheckOnSumStep.new(summed\_letter)  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# doesn't already have digit, so create a AssignOnSumStep for  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# letter  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< AssignOnSumStep.new(summed\_letter)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;chosen\_letters.add(summed\_letter)  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# check whether this letter cannot be zero and if so add a  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# CheckNotZeroStep  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;steps \<\< CheckNotZeroStep.new(summed\_letter) if  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nonzero\_letters.member? summed\_letter  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;# ...

This code breaks down the provided equation into the steps we've seen defined up  
to this point. Though it's a fair bit of code, it's pretty straightforward and  
very well commented. In short:

&nbsp;&nbsp;1. Values are selected for the numbers in each column as needed.  
&nbsp;&nbsp;2. Columns are summed  
&nbsp;&nbsp;3. Sums are assigned and or validated as needed.

With the setup complete, here's the code that kicks the solver into action:

&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;# should be done, so add a FinishStep  
&nbsp;&nbsp;steps \<\< FinishStep.new(display)  
&nbsp;&nbsp;  
&nbsp;&nbsp;# print out all the steps  
&nbsp;&nbsp;# steps.each\_with\_index { |step, i| puts "#{i + 1}. #{step}" }  
&nbsp;&nbsp;  
&nbsp;&nbsp;# let each step know about the one that follows it.  
&nbsp;&nbsp;steps.each\_with\_index { |step, i| step.next\_step = steps[i + 1] }  
&nbsp;&nbsp;  
&nbsp;&nbsp;# start performing with the first step.  
&nbsp;&nbsp;steps.first.perform(State.new)

Here the FinishStep is added, all steps are linked, and the perform() call is  
made to get the ball rolling. You can uncomment the second chunk of code to  
have a human-readable explanation of the steps added to the output.

My thanks to all the super clever solvers who tackled this problem. I was blown  
away with the creativity.

Tomorrow we will put Ruby Quiz to work helping some friends of ours...