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

<result>
Solution found after 15 steps
SEND+MORE=MONEY
9567+1085=10652

Solution found after 27 steps
FORTY+TEN+TEN=SIXTY
29786+850+850=31486
</result>

And here is the corrected code:

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

And here are the library classes:

<code>
#  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
</code>

<code>
#  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
</code>

Regards, Morton

```