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

- Choose a digit for “d”.
- Choose a digit for “e”.
- Sum the column using letters “d”, “e” (and include carry).
- Set the digit for “y” based on last column summed.
- Choose a digit for “n”.
- Choose a digit for “r”.
- Sum the column using letters “n”, “r” (and include carry).
- Verify that last column summed matches current digit for “e”.
- Choose a digit for “o”.
- Sum the column using letters “e”, “o” (and include carry).
- Verify that last column summed matches current digit for “n”.
- Choose a digit for “s”.
- Verify that “s” has not been assigned to zero.
- Choose a digit for “m”.
- Verify that “m” has not been assigned to zero.
- Sum the column using letters “s”, “m” (and include carry).
- Verify that last column summed matches current digit for “o”.
- Sum the column using letters (and include carry).
- Verify that last column summed matches current digit for “m”.
- 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

====

# This is a solution to Ruby Q. #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

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