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
# ( 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} '<word_1>+<word_2>+...+<word_n>=<word_res>'"
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/
[2] http://gecoder.rubyforge.org/installation.html
[3] http://www.gecode.org/download.html
[4] http://www.gecode.org/gecode-doc-latest/PageComp.html

-- 
Andreas Launila