From: John Browning <listguy@...>
Date: 2007-04-09T03:09:00+09:00
Subject: Re: [QUIZ] Getting to 100 (#119)

--Apple-Mail-3-180031051
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

This solution does the extra credit -- at least for binary operators  
that are meaningful to ruby eval. It seemed easier to do the extra  
credit than not.

The fact that the string of digits keeps its order makes this problem  
much simpler. You don't need to find all of the permutations of  
digits; you just need to iterate over the string to insert the  
operators at each legal position in each unique permutation. This  
solution does that recursively -- which is hopefully easier to  
understand from looking at insert_ops, which does most of the work,  
than by putting it into words.


#!/usr/bin/env ruby
#

require 'permutation'

class EqGenerator
   def initialize(digits, operators, result)
     @digits = digits
     @operators = operators
     @result = result
   end

   def solve
     # create array of possible solutions, then print, testing  
against desired result as we go
     correct = 0
     @eqs = permute_ops(@operators).collect { |o| insert_ops(@digits,  
o) }.flatten
     @eqs.each do |e|
       res = eval(e)
       if (res == @result)
         correct += 1
         puts "***#{e}=#{res}***"
       else
         puts "#{e}=#{res}"
       end
     end
     puts "A total of #{@eqs.length} equations were tested, of which # 
{correct} " + ((correct == 1)? "was": "were") + " correct"
   end

   private
   def permute_ops(ops)
     # use gem from <http://permutation.rubyforge.org/> to get unique  
permutations of operators and return as array
     perm = Permutation.new(ops.length)
     return perm.map { |p| p.project(ops) }.uniq
   end

   def insert_ops(digs, ops)
     res = Array.new
     # if only one op to insert, just put it in each available spot  
and return array of equations
     if ops.length == 1 then
       0.upto(digs.length-2) { |i| res << digs[0..i] + ops + digs[i 
+1..digs.length]}
     # if more than 1 op, for each legal placement of first op:  
recursively calculate placements for other ops and digits, then  
prepend first op
     else
       0.upto(digs.length - (ops.length+1)) { |i| res << insert_ops 
(digs[i+1..digs.length], ops[1..ops.length]).collect { |e| digs[0..i]  
+ ops[0..0] + e } }
     end
     return res.flatten
   end

end

eg = EqGenerator.new("123456789", "--+", 100)
eg.solve



........................................................................ 
............................
John Browning






--Apple-Mail-3-180031051--