On Fri, 06 Apr 2007 21:55:37 +0900, Ruby Quiz wrote:

> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this quiz
> until 48 hours have passed from the time on this message.
> 
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.rubyquiz.com/
> 
> 3.  Enjoy!
> 
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> everyone on Ruby Talk follow the discussion.  Please reply to the
> original quiz message, if you can.
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
> 
> by Gavin Kistner
> 
> The NPR show "Car Talk" has regular quizzes that they call
> "Puzzlers"[1]. The one listed on their web site for March 12th[2] is
> titled "Getting to 100". In the quiz, you are supposed to write down the
> digits 1-9 in order, followed by " = 100", and then insert between them
> two minus symbols and one plus symbol (in any order) to make the formula
> correct. You aren't allowed to re-arrange digits, or do some toothpick
> math like combine two minus signs to make a plus. You must use every
> digit, and all three operators. For example, here's one incorrect
> solution:
> 
> 	123 + 45 - 67 - 89 = 100  (This is an incorrect formula; it 
totals 12)
> 
> The quiz, then, is to solve this problem without thinking, instead
> letting the computer think for you. Your program should output every
> possible equation that can be formed, and the actual result of that
> equation. The equation that results in 100 should have stars around it.
> At the end, you should print out the number of formulae that were
> possible. Here's an excerpt of some example output:
> 
> 	...
> 	12 - 34 - 567 + 89 = -500
> 	12 - 34 + 567 - 89 = 456
> 	12 + 34 - 567 - 89 = -610
> 	************************
> 	123 - 45 - 67 + 89 = 100
> 	************************
> 	123456 - 7 - 8 + 9 = 123450
> 	123456 - 7 + 8 - 9 = 123448
> 	123456 + 7 - 8 - 9 = 123446
> 	...
> 	168 possible equations tested
> 
> You should not print the same equation more than once. ("1 - 2 - 3 +
> 456789" is the same as "1 - 2 - 3 + 456789", even if the computer thinks
> that the two minus symbols come in a different order.)
> 
> Extra Credit: Write your program to accept an arbitrary number and
> ordering of digits, an arbitrary set of operators (but allowing the same
> operator more than once), and an arbitrary target number that the
> equation is supposed to evaluate to.
> 
> 	[1] 2007 Puzzler Index:
> 	http://www.cartalk.com/content/puzzler/2007.html [2]
> 	http://www.cartalk.com/content/puzzler/transcripts/200711/
index.html

#!/usr/bin/env ruby

#requires are only necessary to construct the
#operator permutation table from the list of operators
#if you want to hard code that (and not do the extra credit)
#then no extra libraries are necessary
require 'rubygems'
require_gem 'facets'
require 'facets/core/enumerable/permutation'
require 'enumerator'

Digits= (ARGV.shift || "123456789").split(//)
RequestedResult=(ARGV.shift || 100).to_i
rawoperators=(ARGV.shift || "+--")

#construct the operator permutation table from the list of operators
Operators=rawoperators.split(//).map{|x| " #{x} "}
OperatorPerms=Enumerable::Enumerator.new(Operators,:each_permutation).
   map{|p| p}.uniq

class Array
   
   #Yields all partitionings of the array which have +num+ partitions
   #and retain the order of the elements
   #
   #To relax the ordering constraint, use this in combination
   #with Enumerable#each_permutation
   def each_partition num
      if num==1
	 yield [self]
	 return self
      end
      (0..length-num).each do |x|
	 firstset=self[0..x]
	 self[(x+1)..-1].each_partition(num-1) do |y|
	    yield [firstset,*y]
	 end
      end
      return self
   end
end

#The actual solution to the problem
counter=0
found=0
Digits.each_partition(Operators.length+1) do |digitspart|
   OperatorPerms.each do |operatorsperm|
      counter+=1
      expression=digitspart.zip(operatorsperm).flatten.join
      result=eval(expression)
      puts "************************" if RequestedResult==result
      puts "#{expression} = #{result}"
      puts "************************" if RequestedResult==result
      found+=1 if RequestedResult==result
   end
end
puts "#{counter} possible equations tested"
puts "#{found} equation(s) equaled #{RequestedResult}"

-- 
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/