From: Morton Goldberg <m_goldberg@...>
Date: 2007-06-18T23:55:32+09:00
Subject: Re: [QUIZ] Verbal Arithmetic (#128)

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:

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

Regards, Morton