send + most ------ money
Given the above equation, assign digits to each letter so that the equation holds when the letter are substituted with the assigned digits. No two letter may be assigned the same digit and the first letter of a word is not allowed to be assigned 0 (i.e. a number may not start with 0 in the equation). There are multiple valid assignments, the one which maximizes the value of “money” is sought.
1 require 'rubygems' 2 require 'gecoder' 3 4 # Solves the cryptarithmetic send+most=money problem while maximizing the value 5 # of "money". 6 class SendMostMoney 7 include Gecode::Mixin 8 9 attr :money 10 11 def initialize 12 # Set up the variables, 9 letters with domain 0..9. 13 s,e,n,d,m,o,s,t,y = letters_is_an int_var_array(9, 0..9) 14 # Express the quantity we are optimizing, in this case money. 15 # This utilises that any operand can be converted into a variable. 16 @money = equation_row(m,o,n,e,y).to_int_var 17 18 # Set up the constraints. 19 # The equation must hold. 20 (equation_row(s, e, n, d) + equation_row(m, o, s, t)).must == 21 equation_row(m, o, n, e, y) 22 23 # The initial letters may not be 0. 24 s.must_not == 0 25 m.must_not == 0 26 27 # All letters must be assigned different digits. 28 letters.must_be.distinct 29 30 # Set the branching. 31 branch_on letters, :variable => :smallest_size, :value => :min 32 end 33 34 private 35 36 # A helper to make the linear equation a bit tidier. Takes a number of 37 # variables and computes the linear combination as if the variable 38 # were digits in a base 10 number. E.g. x,y,z becomes 39 # 100*x + 10*y + z . 40 def equation_row(*variables) 41 variables.inject{ |result, variable| variable + result * 10 } 42 end 43 end 44 45 solution = SendMostMoney.new.maximize! :money 46 puts 's e n d m o s t y' 47 puts solution.letters.values.join(' ') 48 puts "money: #{solution.money.value}"
s e n d m o s t y
3 7 8 2 1 0 9 4 6
money: 10876