From: Matt Hulse <matt.hulse@...>
Date: 2007-04-09T12:10:05+09:00
Subject: Re: Getting to 100 (#119)

My first quiz attempt ever so go easy on me :)

>From looking at the submissions so far it seems like my solution is
quite verbose but I am proud to have a solution that works! (Extra
Credit Too)


#file permutate.rb
module Permutate

	def Permutate.generate(n)
		permutations = Array.new
		perm = Array.new

		#first permutation
		(1..n).each{|i|
			perm << i
		}

	#	print "#{perm}\n"
		permutations << perm.to_s

		(2..(fact(n))).each do |i|
			m = n - 2

			while (perm[m] > perm[m+1])
				m = m - 1
			end
			k = n - 1

			while perm[m] > perm[k]
				k = k - 1
			end
			swap(perm,m,k)
			p = m + 1
			q = n - 1
			while p < q
				swap(perm,p,q)
				p = p + 1
				q = q - 1
			end
	#		print "#{perm}\n"
			permutations << perm.to_s
		end
		permutations
	end

	def Permutate.swap(array, a, b)
		temp = array[a]
		array[a] = array[b]
		array[b] = temp
	end

	def Permutate.fact(n)
		return 1 if n == 0
		result = 1
		(2..n).each do |i|
			result *= i
		end
		result
	end

end


#file equation.rb
class Equation

	attr_reader :digits, :rhs, :overlay, :valid

	#digits contains an array of digits in the problem
	#rhs is the right hand side of the equation
	#overlay is a string representation of operators
	# and their position in available positions between
	# digits

	def initialize(digits, rhs, overlay)
		@digits = digits
		@rhs = rhs
		@overlay = overlay
		@eqn = buildEquation

		@valid = isValid?
	end

	def buildEquation
		equation = @digits.to_s

		#overlay permutation string over digits
		#put a space before and after all operators
		(0..@overlay.size).each{|i|
			equation.insert((4*i + 1)," #{@overlay[i,1]} ")
		}

		#take _ placeholders out
		equation.gsub!(" _ ","")

		return equation
	end

	def isValid?
		(eval(@eqn) == @rhs)
	end

	def to_s
		#output the equation in standard format
		result = "#{@eqn} = #{eval(@eqn)}".squeeze(" ")

		if @valid
			marker = "*" * result.size
			return "#{marker}\n#{result}\n#{marker}"
		else
			return result
		end
	end

end



#file equationlist.rb
require 'permutate'
require 'equation'

class EquationList

	attr_reader :digits, :rhs, :operators, :list

	def initialize(digits, operators, rhs)
		@digits = digits
		@operators = operators
		@rhs = rhs
		@list = Array.new
	end

	def build
		#get permutations for location of operators
		perms = Permutate.generate(@digits.size - 1)

		#now assign each operator to a number in the perms list
		operators.each_with_index{|operator,i|
			perms.each{|perm|
				perm.sub!(Regexp.new((i+1).to_s),operator)
			}
		}

		#now replace each number left with _
		#to denote that field is unused
		perms.each{|perm|
			perm.gsub!(/\d/,"_")
		}

		#now we need to get rid of nonunique equations
		perms.uniq!

		#now build a list of equation objects with this information
		perms.each{|perm|
			#puts perm
			@list << Equation.new(@digits,@rhs,perm)
		}
	end

	def display
		puts @list
		puts "#{@list.size} possible equations tested"
	end
end




#file getTo100.rb
require 'equationlist'

digits = %w[1 2 3 4 5 6 7 8 9]
operators = %w[+ - -]
rhs = 100

equations = EquationList.new(digits, ops, rhs)
equations.build
equations.display




Comments are welcome, I'm here to learn!



Matt Hulse
matt.hulse@gmail.com