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...

on 2007-04-06 14:57

on 2007-04-06 15:33

On 4/6/07, Ruby Quiz <james@grayproductions.net> wrote: > > the quiz, you are supposed to write down the digits 1-9 in order, followed by " > can be formed, and the actual result of that equation. The equation that results > 123456 - 7 - 8 + 9 = 123450 > digits, an arbitrary set of operators (but allowing the same operator more than > once) sorry for being picky but I guess it might be useful - an arbitrary set of operators + an array of operators that can come in any order hopefully somebody will find the correct formal expression to describe the beast ... , 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... > > For the rest sounds like fun. Cheers Robert

on 2007-04-06 15:47

On Apr 6, 2007, at 8:32 AM, Robert Dober wrote: > sorry for being picky but I guess it might be useful > - an arbitrary set of operators > + an array of operators that can come in any order > hopefully somebody will find the correct formal expression to describe > the beast ... > , and an arbitrary target number that the equation is supposed to > evaluate We had that quiz, though this one is definitely similar: http://www.rubyquiz.com/quiz7.html James Edward Gray II

on 2007-04-06 20:31

On Apr 6, 12:11 pm, "Kyle Schmitt" <kyleaschm...@gmail.com> wrote: > OK only 43 hours to go... > > Stupid non spoiler rule Did you get all the extra credit already?

on 2007-04-06 20:43

Everything but the arbitrary ordering and number of digits. And it can run in O(n) time ;)

on 2007-04-06 21:54

[Ruby Quiz <james@grayproductions.net>, 2007-04-06 14.55 CEST] [...] > 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. Can the plus and minus symbols be used as unary operators?

on 2007-04-06 23:01

On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote: > > Can the plus and minus symbols be used as unary operators? Not as described, in the original quiz, but I'd say...sure! :) It would require that it either be applied before the first digit: -12345 - 67 + 89 or after another operator: 123 + -45 -6789 but I don't see any reason to disallow that sort of extra logic if you want to do it.

on 2007-04-06 23:08

Phrogz wrote: > On Apr 6, 1:53 pm, Carlos <a...@quovadis.com.ar> wrote: > > Can the plus and minus symbols be used as unary operators? > [...] > but I don't see any reason to disallow that sort of extra logic if you > want to do it. Well, one reason would be that using a plus as a unary operator is the same as not using it at all, so that would allow you to circumvent the use-all-operators-rule.

on 2007-04-07 07:38

James Gray wrote: > The three rules of Ruby Quiz: > Yay. I remember doing this exercise in math class back there in secondary school. Not to be conceited, but I remember having so much fun with that I tried some variations on the exercise, finding around 200 solutions or so. But, of course, I', crazy :D I want to suggest some extra credits for all those crazy people put there ;D - You can use parenthesis to change precedence of operators (if you use ore than addition and subtraction) - You can use decimal dot in numbers. As for example: .1 - 2 + (3 * 4) + 5 + 6 + 78.9 = 100 - Given the set of numbers, rules and operations, say if it can yield all numbers on a given range, or try to find the largest range possible. Certainly I love these quizes. =D

on 2007-04-08 15:55

Here's my solution. It handles both extra credit suggestions, and adds control over the verbosity of the output, and some options for finding 'interesting' inputs. I found this quiz rather easy. I had a basic solution in about 15 minutes, and spent about another half hour or so generalizing it. The main problem was partitioning the string of digits in order to place the operators. I did this with a recursive method on String which iterates over the possible partitionings using block composition. In order to generalize the inputs I used Florian Frank's permutation gem to get the permutations of the operators. require 'rubygems' require 'permutation' class String # yield each partitioning of the receiver into count partitions # # This is a recursive implementation using composition of the block argument. # # The approach is to iteratively split the string into two parts, # an initial substring of increasing length, and the remainder. # For each initial substring we yield an array which is the concatenation # of the initial substring and the partitioning of the remainder of the string # into count-1 partitions. def each_partition(count, &b) # if the count is 1 then the only partition is the entire string. if count == 1 yield [self] else # Iterate over the initial substrings, the longest initial substring must leave # at least count-1 characters in the remaining string. (1..(size-(count-1))).each do |initial_size| self[initial_size..size].each_partition(count-1) {|remaining| b.call([self[0,initial_size]] + remaining)} end end end end # print combinations of digits and operators which evaluate to a goal # # Arguments are supplied by a hash the keys are: # # Main arguments # :goal - the number being sought, default is 100 # :digits - a string of digits, default is "123456789" # :ops - an array of strings representing the operators to be inserted into # digits, default is %w[- - +] # # Additional arguments # :verbose - unless false, print all attempts, default is false # :return_counts - unless false, return an array of value, count arrays for # values with multiple solutions, used to find interesting # inputs, default is false def get_to(options={}) options = { :goal => 100, :digits => '123456789', :ops => %w[- - +], :verbose => false, :return_counts => false } .merge(options) digits= options[:digits] goal, digits, ops, verbose, return_counts = *options.values_at(:goal, :digits, :ops, :verbose, :return_counts) operators = Permutation.for(ops).map{|perm| perm.project}.uniq puts "Looking for #{goal}, digits=#{digits}, operators=#{ops.inspect}" counts = Hash.new(0) found_in_a_row = 0 digits.each_partition(ops.size + 1) do |numbers| operators.each do |ops| op_index = -1 eqn = numbers.zip(ops).flatten.compact.join(' ') val = eval(eqn) counts[val] += 1 if return_counts found = val == goal puts "********************************" if found_in_a_row == 0 && found puts "********************************" unless found_in_a_row == 0 || found puts "#{eqn} = #{val}" if verbose || goal == val found_in_a_row = found ? found_in_a_row + 1 : 0 end end return_counts ? counts.select {|key,value| value > 1} : nil end get_to get_to(:verbose=> true) get_to(:goal => 357, :ops => %w[+ - +], :verbose=> true) get_to(:goal => 302, :digits => '987654321') get_to(:goal => 98, :verbose => true) p get_to(:goal => 336) get_to(:goal => -355) -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/

on 2007-04-08 16:18

My solution below uses simple recursion - hopefully it's easy to read and understand. It meets the extra credit criteria. Looking forward to seeing how some of the power of Ruby could be used by others to create a more elegant solution. (I admit my solution is a bit lacklustre!) Thanks to Gavin & James. # Marcel Ward <wardies ^a-t^ gmaildotcom> # Saturday, 2006-04-07 # Solution for Ruby Quiz #119 <http://www.rubyquiz.com/> # ################################################ # getting-to-x.rb class GettingToX def initialize(no_of_plusses, no_of_minusses, target_number) @plusses = no_of_plusses @minusses = no_of_minusses @target = target_number end # Recursively called whilst preparing the calculation string, # which is passed in calc_prefix def prepare_sum(rem_plus, rem_minus, cur_digit, calc_prefix) cur_digit += 1 # Do we have any remaining plus signs to use up? if rem_plus > 0 prepare_sum(rem_plus - 1, rem_minus, cur_digit, calc_prefix + " + %c" % (?0 + cur_digit)) end # Do we have any remaining minus signs to use up? if rem_minus > 0 prepare_sum(rem_plus, rem_minus - 1, cur_digit, "#{calc_prefix} - %c" % (?0 + cur_digit)) end digits_remaining = 10 - cur_digit if rem_plus + rem_minus < digits_remaining # We can use a digit here and we'll still have room to # fit in all our operators later prepare_sum(rem_plus, rem_minus, cur_digit, "#{calc_prefix}%c" % (?0 + cur_digit)) elsif rem_plus + rem_minus == 0 # We have run out of operators; use up all the digits cur_digit.upto(9) {|n| calc_prefix += "%c" % (?0 + n)} calc(calc_prefix) end end # Print out the sum (with highlights if the target value was hit). def calc(whole_sum) result = eval(whole_sum) target_hit = (result == @target) puts '*' * 30 if target_hit puts whole_sum + ' = ' + result.to_s puts '*' * 30 if target_hit @total_evals += 1 @target_matches += 1 if target_hit end def do_sums @total_evals = 0 @target_matches = 0 # We must always start with a string containing the first digit, # i.e. "1" because after this comes either the next digit or +/- prepare_sum(@plusses, @minusses, 1, '1') puts "#{@total_evals} possible equations tested" @target_matches end end # Show results for 1 plus, 2 minusses, target of 100 x = GettingToX.new(1, 2, 100) matches = x.do_sums # How did we do? puts "** #{matches} equation(s) matched target value **"

on 2007-04-08 16:26

My submission uses extreme (in)elegance ;) in accordance with this weeks quiz saying "don't think, let the computer think for you" I'm submitting several versions, one full version that includes the extra credit, and several "golf" versions Enjoy! --Kyle First we have this version #########begin########### 42 lines long elegance = nil ######################### to100 = Hash.new() @setlength=9#set, starting from 1 to use @maxops=@setlength-1#the maximum number of operators (including space) in any equation @operator = ["", "+", "-"] @oplength = @operator.length keylength = @oplength.power!(@maxops) def bogoGen() little=Array.new(@setlength+@maxops) do |i| if i.modulo(2)==0 then i=i/2 i+=1 else i=@operator[rand(@oplength)] end end return(little.join) end writingHamlet = Time.now() while to100.keys.length<keylength elegance = bogoGen() to100.store(elegance,eval(elegance)) #puts "Found #{to100.keys.length} formulas" if to100.keys.length%100==0 end millionMonkeys = Time.now() to100.sort.each do |answer| fortytwo=answer[1]==100?'*':' ' #display the answer! puts "#{fortytwo} #{answer[0]}=#{answer[1]} #{fortytwo}" end willFinish = Time.now() #puts "Total calculation time: #{millionMonkeys - writingHamlet} seconds" #puts "Total run time: #{willFinish - writingHamlet} seconds" #####end ###### #compact v1 t={} while t.length<(6561) e = Array.new(17){|i| i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join t.store(e,eval(e)) end t.sort.each {|a| f=a[1]==100?'*':' '; puts "#{f} #{a[0]}=#{a[1]} #{f}"} #compact v2 t={} while t.length<(6561) t.store(Array.new(17){|i| i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join,'') end t.sort.each {|a| f=eval(a[0])==100?'*':' '; puts "#{f} #{a[0]}=#{eval(a[0])} #{f}"} #compact v3 t=Array.new(6561){|i|i} t.each_index{|a| while t[a]=Array.new(17){|i| i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join and not t.length==t.uniq.length;end} t.sort.each {|a| f=eval(a)==100?'*':' '; puts "#{f} #{a}=#{eval(a)} #{f}"}

on 2007-04-08 16:27

Here is my solution. Again I've used Test::Unit to test my solution, as well as providing a fairly nice command-line operation. I too did the extra credit (I actually coded it that from the beginning, seemed easy enough.) I borrowed some code for the operator permutations, but after writing my own code to create the numerical groups for the equations I wondered if it might be possible to use one basic algorithm for both. But I don't have time to fix this up at the moment. I may submit another solution later this week. # Based on: # http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/... # Author: Endy Tjahjono class String def perm return [self] if self.length < 2 ret = [] 0.upto(self.length - 1) do |n| rest = self.split(//u) # for UTF-8 encoded strings picked = rest.delete_at(n) rest.join.perm.each { |x| ret << picked + x } end ret end end # All the rest is Ryan Leavengood code :) class EquationSolver attr_reader :num_seq, :operators, :result def initialize(num_seq = "123456789", operators = "--+", result_wanted = 100) @num_seq, @operators, @result_wanted = num_seq, operators, result_wanted end SEP = '*' * 24 def solve equations = 0 ops = op_combinations(@operators).map{|a| a.split('')} generate_groups(@num_seq).each do |group| ops.each do |op| eq = group.zip(op).join(' ') result = eval(eq) puts SEP if result == @result_wanted puts "#{eq}= #{result}" puts SEP if result == @result_wanted equations += 1 end end puts "#{equations} possible equations tested" end def op_combinations(operators) operators.perm.uniq end # Returns an array of numeric strings representing how the given # number can be split into the given number of groups def num_split(number, num_groups) return [number.to_s] if num_groups == 1 return ["1" * num_groups] if number == num_groups result = [] ((number + 1)-num_groups).times do |i| cur_num = i + 1 num_split(number - cur_num, num_groups - 1).each do |group| result << "#{cur_num}#{group}" end end result end def generate_groups(num_seq, num_groups = @operators.length+1) num_split(num_seq.length, num_groups).map do |split_on| # Turn the result from num_split into a regular expression, # with each number becoming grouped dots reg_exp = split_on.split('').map{|n| "(#{'.' * n.to_i})"}.join num_seq.scan(/#{reg_exp}/).first end end end require 'test/unit' class SolverTester < Test::Unit::TestCase def setup @es = EquationSolver.new end def test_string_perm assert_equal(["1"], "1".perm) assert_equal(["12","21"], "12".perm) assert_equal(["123", "132", "213", "231", "312", "321"], "123".perm) end def test_op_combinations assert_equal(["1"], @es.op_combinations("1")) assert_equal(["12","21"], @es.op_combinations("12")) assert_equal(["123", "132", "213", "231", "312", "321"], @es.op_combinations("123")) assert_equal(["223", "232", "322"], @es.op_combinations("223")) assert_equal(["--+", "-+-", "+--"], @es.op_combinations("--+")) end def test_num_split assert_equal(["11"], @es.num_split(2,2)) assert_equal(["111"], @es.num_split(3,3)) assert_equal(["12", "21"], @es.num_split(3,2)) assert_equal(["13", "22", "31"], @es.num_split(4,2)) assert_equal(["112", "121", "211"], @es.num_split(4,3)) end def test_generate_groups assert_equal([["1", "2", "34"], ["1", "23", "4"], ["12", "3", "4"]], @es.generate_groups("1234", 3)) end end if $0 == __FILE__ # By default do not run the test cases Test::Unit.run = true if ARGV.length > 0 if ARGV[0] == 'ut' # Run the test cases Test::Unit.run = false else begin if ARGV.length != 3 raise else if ARGV[0] =~ /^\d*$/ and ARGV[1] =~ /^[\+\-\*\/]*$/ and ARGV[2] =~ /^-?\d*$/ EquationSolver.new(ARGV[0], ARGV[1], ARGV[2].to_i).solve else raise end end rescue puts "Usage: #$0 <number sequence> <string of operators> <result wanted>" puts "\tOr just the single parameter 'ut' to run the test cases." exit(1) end end else # Solve the default case EquationSolver.new.solve end end __END__ Regards, Ryan

on 2007-04-08 16:47

Ohh yea, and despite the evilness of my implementation it does, in fact, run in a reasonable amount of time. I averaged 100 seconds for the full version and only 10 minutes for the last, most compact, golf version. --Kyle

on 2007-04-08 16:56

On 4/8/07, Kyle Schmitt <kyleaschmitt@gmail.com> wrote: > Ohh yea, and despite the evilness of my implementation it does, in > fact, run in a reasonable amount of time. I averaged 100 seconds for > the full version and only 10 minutes for the last, most compact, golf > version. Hahaha, yeah I tried running the last one and gave up. You might want to explain what these are doing, as it isn't exactly obvious. But in general I would think if it takes the computer 10 minutes to solve, you might as well do it yourself (or rewrite your algorithm :) Ryan

on 2007-04-08 17:04

It's using an algorithm based on a bogosort to generate the equation :) the hash based implementations run reasonably quick. The array based one has to check for uniqueness each time, so it's rather poor performance wise. Basically 123456789 is interspersed with " " + and - randomly, inserted into the hash and repeated until the size of the hash is 8^3 (which is the number of unique formulas) It's not written for speed, it's written for the computer to do all the work, and the programmer to be well.. lazy! --Kyle

on 2007-04-08 17:40

On Fri, 06 Apr 2007 21:55:37 +0900, Ruby Quiz wrote: > > 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. > > -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=-=-= > 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) > 12 - 34 + 567 - 89 = 456 > You should not print the same equation more than once. ("1 - 2 - 3 + > 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}"

on 2007-04-08 18:39

=begin > The quiz, then, is to solve this problem without thinking, instead > letting the computer think for you. I did not intent to seriously submit this solution, but it can be helpful as an example of how to use Ruby to solve a problem quickly without thinking too much or locating Knuth on the bookshelve. Writing this code took maybe ten minutes and happened step-by-step with checking the immediate results. Since there are only 168 solutions (254 if you allow a sign before the first digit), brute-forcing is the simplest thing one can do. Additional operations can be added by changing the base and mapping the digits onto further operations. (Different digit order is not that easy to implement and maybe be futile to do with brute-forcing.) =end (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0"). tr('012', '-+ ') }. find_all { |x| x.count("-") == 2 and x.count("+") == 1 }. map { |x| t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") [eval(t), t] }.sort.each { |s, x| puts "*****************" if s == 100 puts "#{x}: #{s}" puts "*****************" if s == 100 } __END__ 2#787<p4>lilith:~/mess/current$ ruby quiz119.rb |grep -C4 100$ 123-456-7+89: -251 123+45-67-89: 12 123-45+67-89: 56 ***************** 123-45-67+89: 100 ***************** 12+345-67-89: 201 1-234+567-89: 245 1-23-456+789: 311

on 2007-04-08 20:10

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

on 2007-04-08 20:25

Here goes my solution for another nice quiz, yes I know I repeat myself. It should get all the extras plus one extra from the last quiz, the fuzzy solutions. Cheers Robert Defaults = { :@fuzz => 0, :@target => 100, :@digits => [*1..9], :@ops => [ :-, :- , :+ ] } ### Override the default values if you want ;). Defaults.each do | key, value | instance_variable_set "#{key}", value end # Configurable.each do ### If you are really serious about overriding the default values do it ### again ;). @ops.map!{|o| " #{o} "} class Array def each_with_rest each_with_index do | ele, i | yield ele, self[0, i] + self[i+1..-1] end end # each_with_rest def runtempatios return [[]] if empty? remps = [] each_with_rest do | ele, rest | remps += rest.runtempatios.map{ | p | p.unshift(ele) } end # each_with_rest do remps.uniq end # def runtempatios end # My wife does not like it very much when I am slicing the bread, the slices are of # very variable thickness!!! # A long earned skill that I can eventually put to work now :) def _slices outer, inner ## In order to be able to slice we have to assure that outer.size > inner.size return [ outer ] if inner.empty? r = [] (outer.size-inner.size+1).times do |i| _slices( outer[i+1..-1], inner[1..-1] ).each do | slice | r << outer[0,i.succ] + inner[0..0] + slice end # slices( outer[i+2..-1], rest ).each do end # (outer.size-inner.size).times do r end def slices outer, inner _slices( outer, inner ).reject{|s| inner.include? s.last } end @count = 0 @total = 0 @target = (@target-@fuzz .. @target+@fuzz) @ops.runtempatios.each do | ops | slices( @digits, ops ).each do | expression | e = expression.join value = eval e e << " = #{value}" if @target === value then @count += 1 puts e.gsub(/./,"*") puts e puts e.gsub(/./,"*") else puts e end @total += 1 end # slices( @digits, ops ).each do end # @ops.runtempatios.each do puts "="*72 puts "There were #{@count} solutions of a total of #{@total} tested"

on 2007-04-08 20:41

On Mon, 09 Apr 2007 01:39:19 +0900, Christian Neukirchen wrote: > Since there are only 168 solutions (254 if you allow a sign before the > first digit), brute-forcing is the simplest thing one can do. Additional > operations can be added by changing the base and mapping the digits onto > further operations. (Different digit order is not that easy to > implement and maybe be futile to do with brute-forcing.) =end > > (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0"). > tr('012', '-+ ') }. > find_all { |x| x.count("-") == 2 and x.count("+") == 1 }. A less ram-intensive version of this would swap the map and find_all calls as follows: (00000000..'22222222'.to_i(3)). find_all { |x| x.to_s(3).count("0") == 2 and x.to_s(3).count("1") == 1 }. map { |x| x.to_s(3).tr('012', '-+ ').rjust(8," ")}. (It doesn't keep maintain references to the bad combinations of operators, allowing the GC to reclaim them earlier.) > 2#787<p4>lilith:~/mess/current$ ruby quiz119.rb |grep -C4 100$ > 123-456-7+89: -251 > 123+45-67-89: 12 > 123-45+67-89: 56 > ***************** > 123-45-67+89: 100 > ***************** > 12+345-67-89: 201 > 1-234+567-89: 245 > 1-23-456+789: 311 > I like this answer a lot. Think you could generalize it to the extra credit?

on 2007-04-08 22:10

On Sun, 08 Apr 2007 23:25:14 +0900, Kyle Schmitt wrote: > First we have this version > > little=Array.new(@setlength+@maxops) do > > > > > end > > t.store(e,eval(e)) > t.store(Array.new(17){|i| > t.each_index{|a| while t[a]=Array.new(17){|i| > i=i%2==0?i/2+1:["","+","-"][rand(3)]}.join and not > t.length==t.uniq.length;end} > > t.sort.each {|a| f=eval(a)==100?'*':' '; puts "#{f} #{a}=#{eval(a)} > #{f}"} For those reading along, the magic number 6560=='22222222'.to_i(3) His goal is to just generate 6560 different combinations of the operators using a random generator. One should note that this technically violates the rules of code golf which require the solution to terminate within a short period of time (I believe 4 seconds), so that its correctness can be verified automatically without having to worry about DOS attacks.

on 2007-04-08 22:20

On 4/8/07, Christian Neukirchen <chneukirchen@gmail.com> wrote: > puts "*****************" if s == 100 > } That's brilliant. It took me a minute to figure out how it worked, but I like. I started working on a generalized solution using this algorithm, but it gets tricky. It isn't too hard to generalize the number sequence, but generalizing the operators really makes it messy. Ryan

on 2007-04-08 22:49

On 4/8/07, Ryan Leavengood <leavengood@gmail.com> wrote: > > I started working on a generalized solution using this algorithm, but > it gets tricky. It isn't too hard to generalize the number sequence, > but generalizing the operators really makes it messy. OK, I figured out the generalized solution based on Christian's submission: seq = ARGV[0] ops = ARGV[1] res = ARGV[2].to_i uops = ops.split('').uniq print (0..(uops.length.to_s * (seq.length-1)).to_i(uops.length+1)). map { |x| x.to_s(uops.length+1).rjust((seq.length-1), '0'). tr('012345', uops.join.ljust(6, ' ')) }. find_all { |x| uops.inject(true){|b, op| b and (x.count(op) == ops.count(op))} }. map { |x| t = seq[0,1] + x.split('').zip(seq[1..-1].split('')).join.delete(' ') [eval(t), t] }.each { |s, x| puts "*****************" if s == res puts "#{x}: #{s}" puts "*****************" if s == res }.size puts " possible equations tested" This supports any arbitrary sequence of numbers, up to 5 different operators in whatever combination, and whatever result. It gets slower as you add operators though. This was fun, but I can just see how slow it is, especially with the inject I added. As you can see I also added printing how many equations were tested. Ryan

on 2007-04-09 00:00

here is my first pass: class Array def combinations(n) case n when 0: [] when 1: self.map { |e| [e] } when size: [self] else (0..(size - n)).to_a.inject([]) do |mem,i| mem += self[(i+1)..size].combinations(n-1).map do |rest| [self[i],*rest] end end end end end equations = 0 separator = "************************" (1..8).to_a.combinations(3).each do |partitions| 3.times do |n| equation = "123456789" partitions.reverse.each_with_index do |partition,index| equation = equation.insert(partition, (index == n ? ' + ' : ' - ')) end result = eval(equation) equation << " = #{result}" if result == 100 equation = "#{separator}\n#{equation}\n#{separator}" end puts equation equations += 1 end end puts "#{equations} possible equations tested"

on 2007-04-09 00:13

After going back and reading the current solutions, I like Ken Bloom's each_partition method. It's much cleaner than my combinations method.

on 2007-04-09 04:15

```
#!/usr/bin/ruby
#
# Q119 Solution by Sergey Volkov
# Accept
# - an arbitrary number and ordering of digits,
# - an arbitrary set of operators (but allowing
# the same operator more than once),
# - an arbitrary target number
# Output every possible equation that can be formed,
# and the actual result of that equation.
# The equation that results in target number have
# stars around it.
# At the end, print out the number of formulae
# that were possible.
#
require 'rubygems'
require 'facets/core/enumerable/permutation'
# all possible unique permutations
def op_seqs a
res = Hash.new
a.each_permutation{ |pe|
res[pe] = true
}
res.keys
end
# generate all expressions without reordering,
# recursive implementation;
# I could have implemented Array#each_incut( arr )
# to get more generic solution, but I'm too lazy..
# Will it be better to avoid recursion?
# Not required for this quiz, but must for generic method.
# Does anybody knows elegant nonrecursive implementation? Please show
me.
def incut_all digs, opcs, scurr='', &block
if digs.empty? || opcs.empty?
# result string
block[ %/#{scurr}#{digs}#{opcs.pack('C*')}/ ]
return
end
# extend with digit
incut_all digs[1..-1], opcs, scurr+digs[0].to_s, &block
# extend with operator
incut_all digs, opcs[1..-1], scurr+opcs[0].chr, &block
end
# output all possible equations
def show_all digits, opers, target
# validate arguments
a_digs = digits.scan(/./).map{ |d| Integer( d ) }
fail "invalid operator, only [-, +, *, /] allowed" unless %r|^[-
+*/]+| =~ opers
a_ops = opers.unpack('C*')
n_targ = Integer( target )
count = 0 # equation counter
# operators char set
op_cs = %/[#{ Regexp.quote a_ops.uniq.pack('C*') }]/
# Regexp for 'incorrect' expression
bad_exp_rx = %r/^#{op_cs}|#{op_cs}{2}|#{op_cs}$/o
for op_seq in op_seqs( a_ops )
incut_all( a_digs, op_seq ){ |exp|
next if bad_exp_rx =~ exp
# beautify expression
exp.gsub!( %r/#{op_cs}/, %q/ \0 / )
# evaluate expression
next unless val = eval( exp ) rescue nil
s = %/#{exp} = #{val}/
sep = (val == n_targ) && '*'*s.size
puts sep if sep
puts s
puts sep if sep
count += 1
}
end
puts %/#{count} possible equations tested/
end
# Arguments accepted:
# an arbitrary number and ordering of digits
digits = ARGV[0] || '123456789'
# an arbitrary set of operators (but allowing the same operator more
than once)
opers = ARGV[1] || '+--'
# an arbitrary target number
target = ARGV[2] || 100
# Output all possible equations
show_all( digits, opers, target )
exit
#=================================================
> L:\Ruby\bin\ruby.exe -w L:\rb\Quiz\Q119.rb
...
123-456-7+89 = -251
123-45-678+9 = -591
******************
123-45-67+89 = 100
******************
123-45-6+789 = 861
123-4-5678+9 = -5550
...
168 possible equations tested
```

on 2007-04-09 05:10

```
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
```

on 2007-04-09 05:21

On 08/04/07, Carl Porth <badcarl@gmail.com> wrote: > After going back and reading the current solutions, I like Ken Bloom's > each_partition method. It's much cleaner than my combinations method. I agree, very clean and efficient. The three lines that put it all together using #zip are what makes this work for me: Digits.each_partition(Operators.length+1) do |digitspart| OperatorPerms.each do |operatorsperm| expression=digitspart.zip(operatorsperm).flatten.join ... I think I would be feeling very happy if I'd submitted this solution :)

on 2007-04-09 05:30

require 'rubygems' require 'test/unit' # http://permutation.rubyforge.org/ require 'permutation' # # Partitions collections into all possible in-order subsets # # module Enumerable # # Generate the partion sizes for a collection of a given # length and a specific number of partitions. # def Enumerable.partition_sizes( collection_length, partition_count, &proc ) Enumerable.generate_partition_sizes( [], collection_length, partition_count, proc ) end # # Create all in-order partitions of the given collection. Each # partition should have partition_count elements. # # For example partitions( [1,2,3], 2 ) would yield # [1],[2,3] # and [1,2],[3] # # and partitions( [1,2,3,4], 2 ) would yield # [1],[2,3,4] # and [1,2],[3,4] # and [1,2,3],[4] # def partitions( partition_count, &proc ) Enumerable.partition_sizes( self.size, partition_count ) do | partition| partitioned_collection = [] consumed_so_far = 0 partition.each do |partition_size| partitioned_collection << self[ consumed_so_far, partition_size ] consumed_so_far += partition_size end yield partitioned_collection end end private def Enumerable.generate_partition_sizes( so_far, length, partition_count, proc ) raise "Invalid parameter" if( ( partition_count < 1 ) || ( partition_count > length ) ) partition_size_sum_so_far = so_far.inject(0) { |total,item| total+item } if so_far.length == partition_count -1 working = so_far.dup working << length - partition_size_sum_so_far proc.call( working ) else up_to = length - partition_size_sum_so_far - (partition_count - so_far.length ) + 1 for size in 1..( up_to ) working = so_far.dup working << size generate_partition_sizes( working, length, partition_count, proc ) end end end end class PartitionTest < Test::Unit::TestCase def test_partition_size_4_count_2 expected = [] [1,2,3,4].partitions( 2 ) do |partition| expected << partition end assert_equal expected, [ [ [1], [2, 3, 4] ], [ [1, 2], [3, 4] ], [ [1, 2, 3], [4] ] ] end def test_partition_size_4_count_3 expected = [] [1,2,3,4].partitions( 3 ) do |partition| expected << partition end assert_equal expected, [ [ [1], [2], [3, 4] ], [ [1], [2, 3], [4] ], [ [1, 2], [3], [4] ] ] end def test_partition_size_5_count_1 expected = [] [1,2,3,4,5].partitions( 1 ) do |partition| expected << partition end assert_equal expected, [ [ [ 1, 2, 3,4, 5 ] ], ] end def test_partition_size_5_count_5 expected = [] [1,2,3,4,5].partitions( 5 ) do |partition| expected << partition end assert_equal expected, [ [ [1], [2], [3], [4], [5] ], ] end end def find( digits, operators, magic_number ) # Generate all possible permutation of operations. Make sure that each operator set # begins with an "+" since we are actually creating an equation of # "+{term1} {op1}{term2} {op2}{term3}" as it is easier to compute operator_permutations = Permutation.for( operators ).map { |p| ( "+" + p.project).split(//) }.uniq separator_string = "*" * 20 total_equations_evaluated = 0 # Partition the digits into groups of length one more than the number of operators digits.partitions( operators.length + 1 ) do |digit_partition| # For each operator permutation we'll compute the result of mixing the operators # between the current partition operator_permutations.each do |operator_permutation| # Match up the digit partition and the operators equation = digit_partition.zip( operator_permutation ) # Create the string representation, joining operators # and operands into a resulting equation. equation_string = equation.inject("") do |result,term| # Only add the operator if we have something in the string # this strips out the initial dummy "+" operator from our # equation. result = result + " " + term[1] + " " unless result.empty? result = result + term[0].join end # Evaluate the equation equation_value = eval( equation_string ) total_equations_evaluated += 1 # Output as required with stars surrounding any # equation that yielded the value we wanted puts separator_string if equation_value == magic_number puts "#{equation_string} = #{equation_value}" puts separator_string if equation_value == magic_number end end puts "#{total_equations_evaluated} possible equations tested" end digits = [1,2,3,4,5,6,7,8,9] operators = "--+" find( digits, operators, 100 )

on 2007-04-09 06:47

Wow, this is pretty freaky. My solution is eerily similar to Ken's (albeit less concise), and I hadn't seen his code until now. Look: On Apr 8, 9:21 pm, "Marcel Ward" <ward...@gmail.com> wrote: > On 08/04/07, Carl Porth <badc...@gmail.com> wrote: > > > After going back and reading the current solutions, I like Ken Bloom's > > each_partition method. It's much cleaner than my combinations method. I wrote an Array#each_partition too, and my first implementation of it looked almost just like his: def each_partition(n = length) if n < 1 yield [] else (0..length-n).each do |x| section=self[x, length] self[0, x].each_partition(n-1) do |part| yield part << section end end end self end I rewrote this when I found an iterative algorithm for it, but I hadn't realized that that seemingly extraneous argument could be used to limit the number of partitions, which is clever. Still, this is a fundamental algorithm in combinatorics, so I'm not too surprised that he chose to put in Array. This is where it gets eerie: > I agree, very clean and efficient. The three lines that put it all > together using #zip are what makes this work for me: > > Digits.each_partition(Operators.length+1) do |digitspart| > OperatorPerms.each do |operatorsperm| > expression=digitspart.zip(operatorsperm).flatten.join > ... my version of the above: digits.send(digits_message) do |part| ... operators.send(*ops_send_args) do |tuple| expr = part.zip(tuple).join(' ') ... And then I go on to eval(expr), as Ken did. Take it for granted that my uses of send() do essentially the same thing. Weird, no? > > I think I would be feeling very happy if I'd submitted this solution :) > > -- > Marcel I was, too, before I saw Ken's. Harrison

on 2007-04-09 10:33

Christian Neukirchen wrote: > with checking the immediate results. > find_all { |x| x.count("-") == 2 and x.count("+") == 1 }. > > > I'm sorry to be a noob on this, but can someone please explain to me what this is doing. If it works, it must be genius, and I can't figure it out. Raj Sahae

on 2007-04-09 11:36

On 4/9/07, Raj Sahae <rajsahae@gmail.com> wrote: > > Writing this code took maybe ten minutes and happened step-by-step > > tr('012', '-+ ') }. > > __END__ > > 1-23-456+789: 311 > > > > > I'm sorry to be a noob on this, but can someone please explain to me > what this is doing. If it works, it must be genius, and I can't figure > it out. > > Raj Sahae > > Actually I have no idea whatsoever, this is normally a good starting point ;) irb is our friend of course, so let us hack away: irb(main):003:0> (000..'222'.to_i(3)).map{|x|x.to_s(3).rjust(3, "0").tr('012', '-+ ')} => ["---", "--+", "-- ", "-+-", "-++", "-+ ", "- -", "- +", "- ", "+--", "+-+", "+- ", "++-", "+++", "++ ", "+ -", "+ +", "+ ", " --", " -+", " - ", " +-", " ++", " + ", " -", " +", " "] Aha the ternary array is used to create all kind of operator combinations including " ". I do not know exactly what this is good for right now, but I guess we will learn. As a next step I increase 3 to 8 as I think we can understand that now and I will add the next method (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0").tr('012', '-+ ') }.find_all { |x| x.count("-") == 2 and x.count("+") == 1 } => ["--+ ", "-- + ", "-- + ", "-- + ", "-- + ", "-- +", "-+- ", "-+ - ", "-+ - ", "-+ - ", "-+ - ", "-+ -", "- -+ ", "- - + ", "- - + ", "- - + ", "- - +", "- +- ", "- + - ", "- + - ", "- + - ", "- + -", "- -+ ", "- - + ", "- - + ", "- - +", "- +- ", "- + - ", "- + - ", "- + -", "- -+ ", "- - + ", "- - +", "- +- ", "- + - ", "- + -", "- -+ ", "- - +", "- +- ", "- + -", "- -+", "- +-", "+-- ", "+- - ", "+- - ", "+- - ", "+- - ", "+- -", "+ -- ", "+ - - ", "+ - - ", "+ - - ", "+ - -", "+ -- ", "+ - - ", "+ - - ", "+ - -", "+ -- ", "+ - - ", "+ - -", "+ -- ", "+ - -", "+ --", " --+ ", " -- + ", " -- + ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ - ", " -+ - ", " -+ -", " - -+ ", " - - + ", " - - + ", " - - +", " - +- ", " - + - ", " - + - ", " - + -", " - -+ ", " - - + ", " - - +", " - +- ", " - + - ", " - + -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- - ", " +- - ", " +- -", " + -- ", " + - - ", " + - - ", " + - -", " + -- ", " + - - ", " + - -", " + -- ", " + - -", " + --", " --+ ", " -- + ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ - ", " -+ -", " - -+ ", " - - + ", " - - +", " - +- ", " - + - ", " - + -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- - ", " +- -", " + -- ", " + - - ", " + - -", " + -- ", " + - -", " + --", " --+ ", " -- + ", " -- +", " -+- ", " -+ - ", " -+ -", " - -+ ", " - - +", " - +- ", " - + -", " - -+", " - +-", " +-- ", " +- - ", " +- -", " + -- ", " + - -", " + --", " --+ ", " -- +", " -+- ", " -+ -", " - -+", " - +-", " +-- ", " +- -", " + --", " --+", " -+-", " +--"] It is a little longer but we see already that only 2 minuses and 1 plus is allowed... By storing this into a variable tmp we can continue easily to explore what is happening tmp.map{|x| t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ; [eval(t),t]} => [[456785, "1-2-3+456789"], [56754, "1-2-34+56789"], [6443, "1-2-345+6789"], [-2668, "1-2-3456+789"], [-34479, "1-2-34567+89"], [-345670, "1-2-345678+9"], [-456787, "1-2+3-456789"], [-56756, "1-2+34-56789"], [-6445, "1-2+345-6789"], [2666, "1-2+3456-789"], [34477, "1-2+34567-89"], [345668, "1-2+345678-9"], [56763, "1-23-4+56789"], [6722, "1-23-45+6789"], [311, "1-23-456+789"], [-4500, "1-23-4567+89"], [-45691, "1-23-45678+9"], [-56807, "1-23+4-56789"], [-6766, "1-23+45-6789"], [-355, "1-23+456-789"], [4456, "1-23+4567-89"], [45647, "1-23+45678-9"], [6551, "1-234-5+6789"], [500, "1-234-56+789"], [-711, "1-234-567+89"], [-5902, "1-234-5678+9"], [-7017, "1-234+5-6789"], [-966, "1-234+56-789"], [245, "1-234+567-89"], [5436, "1-234+5678-9"], [-1561, "1-2345-6+789"], [-2322, "1-2345-67+89"], [-3013, "1-2345-678+9"], [-3127, "1-2345+6-789"], [-2366, "1-2345+67-89"], [-1675, "1-2345+678-9"], [-23373, "1-23456-7+89"], [-23524, "1-23456-78+9"], [-23537, "1-23456+7-89"], [-23386, "1-23456+78-9"], [-234565, "1-234567-8+9"], [-234567, "1-234567+8-9"], [-456789, "1+2-3-456789"], [-56820, "1+2-34-56789"], [-7131, "1+2-345-6789"], [-4242, "1+2-3456-789"], [-34653, "1+2-34567-89"], [-345684, "1+2-345678-9"], [-56769, "1+23-4-56789"], [-6810, "1+23-45-6789"], [-1221, "1+23-456-789"], [-4632, "1+23-4567-89"], [-45663, "1+23-45678-9"], [-6559, "1+234-5-6789"], [-610, "1+234-56-789"], [-421, "1+234-567-89"], [-5452, "1+234-5678-9"], [1551, "1+2345-6-789"], [2190, "1+2345-67-89"], [1659, "1+2345-678-9"], [23361, "1+23456-7-89"], [23370, "1+23456-78-9"], [234551, "1+234567-8-9"], [56794, "12-3-4+56789"], [6753, "12-3-45+6789"], [342, "12-3-456+789"], [-4469, "12-3-4567+89"], [-45660, "12-3-45678+9"], [-56776, "12-3+4-56789"], [-6735, "12-3+45-6789"], [-324, "12-3+456-789"], [4487, "12-3+4567-89"], [45678, "12-3+45678-9"], [6762, "12-34-5+6789"], [711, "12-34-56+789"], [-500, "12-34-567+89"], [-5691, "12-34-5678+9"], [-6806, "12-34+5-6789"], [-755, "12-34+56-789"], [456, "12-34+567-89"], [5647, "12-34+5678-9"], [450, "12-345-6+789"], [-311, "12-345-67+89"], [-1002, "12-345-678+9"], [-1116, "12-345+6-789"], [-355, "12-345+67-89"], [336, "12-345+678-9"], [-3362, "12-3456-7+89"], [-3513, "12-3456-78+9"], [-3526, "12-3456+7-89"], [-3375, "12-3456+78-9"], [-34554, "12-34567-8+9"], [-34556, "12-34567+8-9"], [-56778, "12+3-4-56789"], [-6819, "12+3-45-6789"], [-1230, "12+3-456-789"], [-4641, "12+3-4567-89"], [-45672, "12+3-45678-9"], [-6748, "12+34-5-6789"], [-799, "12+34-56-789"], [-610, "12+34-567-89"], [-5641, "12+34-5678-9"], [-438, "12+345-6-789"], [201, "12+345-67-89"], [-330, "12+345-678-9"], [3372, "12+3456-7-89"], [3381, "12+3456-78-9"], [34562, "12+34567-8-9"], [6903, "123-4-5+6789"], [852, "123-4-56+789"], [-359, "123-4-567+89"], [-5550, "123-4-5678+9"], [-6665, "123-4+5-6789"], [-614, "123-4+56-789"], [597, "123-4+567-89"], [5788, "123-4+5678-9"], [861, "123-45-6+789"], [100, "123-45-67+89"], [-591, "123-45-678+9"], [-705, "123-45+6-789"], [56, "123-45+67-89"], [747, "123-45+678-9"], [-251, "123-456-7+89"], [-402, "123-456-78+9"], [-415, "123-456+7-89"], [-264, "123-456+78-9"], [-4443, "123-4567-8+9"], [-4445, "123-4567+8-9"], [-6667, "123+4-5-6789"], [-718, "123+4-56-789"], [-529, "123+4-567-89"], [-5560, "123+4-5678-9"], [-627, "123+45-6-789"], [12, "123+45-67-89"], [-519, "123+45-678-9"], [483, "123+456-7-89"], [492, "123+456-78-9"], [4673, "123+4567-8-9"], [2012, "1234-5-6+789"], [1251, "1234-5-67+89"], [560, "1234-5-678+9"], [446, "1234-5+6-789"], [1207, "1234-5+67-89"], [1898, "1234-5+678-9"], [1260, "1234-56-7+89"], [1109, "1234-56-78+9"], [1096, "1234-56+7-89"], [1247, "1234-56+78-9"], [668, "1234-567-8+9"], [666, "1234-567+8-9"], [444, "1234+5-6-789"], [1083, "1234+5-67-89"], [552, "1234+5-678-9"], [1194, "1234+56-7-89"], [1203, "1234+56-78-9"], [1784, "1234+567-8-9"], [12421, "12345-6-7+89"], [12270, "12345-6-78+9"], [12257, "12345-6+7-89"], [12408, "12345-6+78-9"], [12279, "12345-67-8+9"], [12277, "12345-67+8-9"], [12255, "12345+6-7-89"], [12264, "12345+6-78-9"], [12395, "12345+67-8-9"], [123450, "123456-7-8+9"], [123448, "123456-7+8-9"], [123446, "123456+7-8-9"]] Well this is very impressive as it solves the quiz but I lost him there, I guess we have to look into the block applied to tmp.map {|x| t = "1" + x.split(//).zip((2..9).to_a).join.delete(" ") ; [eval(t),t]} okay let us take just one x, e.g. x= tmp[32] => "- - +" ## To my great despair tmp[42] is not a very good example :( Now we split x into single characters and zip the digits 2 to 9 into them x.split(//).zip([*2..9]) => [["-", 2], [" ", 3], [" ", 4], [" ", 5], ["-", 6], [" ", 7], [" ", 8], ["+", 9]] and I think I understand what happened now, the rest is basic, add a 1 in the front flatten the array and delete all spaces, and you get the expressions needed for the quiz. I guess that the final sort.each is quite straight forward. HTH BTW I want to have my ball back James, or adjust my handicap please ;). Cheers Robert

on 2007-04-09 14:19

On 4/8/07, Marcel Ward <wardies@gmail.com> wrote: > ... > > I think I would be feeling very happy if I'd submitted this solution :) May I have the temerity to point out that I posted basically the same solution, which I posted two hours before Ken's. -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/

on 2007-04-09 14:48

Ken Bloom <kbloom@gmail.com> writes: >> the immediate results. > > A less ram-intensive version of this would swap the map and find_all > calls as follows: > > (00000000..'22222222'.to_i(3)). > find_all { |x| x.to_s(3).count("0") == 2 and > x.to_s(3).count("1") == 1 }. > map { |x| x.to_s(3).tr('012', '-+ ').rjust(8," ")}. > > (It doesn't keep maintain references to the bad combinations of > operators, allowing the GC to reclaim them earlier.) Yes, but that confuses the application logic. I don't think it will save memory compared to yours, you are #to_s'ing a lot more than me!

on 2007-04-09 14:52

"Ryan Leavengood" <leavengood@gmail.com> writes: >> puts "#{x}: #{s}" >> puts "*****************" if s == 100 >> } > > That's brilliant. It took me a minute to figure out how it worked, but I like. > > I started working on a generalized solution using this algorithm, but > it gets tricky. It isn't too hard to generalize the number sequence, > but generalizing the operators really makes it messy. The number sequence is easy, and the operators are easy too (just change the base), as you have shown. The real problem is to allow the numbers in any order. > Ryan P.S: The code was not written deliberately in a cryptic style (but admittedly unfactored). This is how I code one-shot things.

on 2007-04-09 16:09

On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote: > > expression=digitspart.zip(operatorsperm).flatten.join > > ... > > > > I think I would be feeling very happy if I'd submitted this solution :) > > May I have the temerity to point out that I posted basically the same > solution, which I posted two hours before Ken's. Indeed you may -- apologies, I thought I had been back through all the posts but didn't go back as far as yours. So I think you should also be feeling very happy :) I do have one small piece of constructive criticism (if I may) since you brought attention to your code: found = val == goal puts "*****************" if found_in_a_row == 0 && found puts "*****************" unless found_in_a_row == 0 || found puts "#{eqn} = #{val}" if verbose || goal == val found_in_a_row = found ? found_in_a_row + 1 : 0 Could also have been written: found = val == goal puts "*****************" if found puts "#{eqn} = #{val}" if verbose || goal == val puts "*****************" if found found_in_a_row = found ? found_in_a_row + 1 : 0 For the same number of lines, I find the second much easier to follow without having to remember any state for the second time around. There does not seem to be any advantage in placing the asterisk lines together. (?) As another aside, I'm in two minds as to whether it's necessary to provide such a complete set of parameters (and comments) for these solutions. On the one hand it sets a good example to newcomers (and it satisfies our quest for perfection) but on the other it does tend to obscure some of the more interesting details. It's like you're damned if you do and damned if you don't - the difficulty is finding the right balance. I think there's room for both kinds of posts but certainly the shorter ones seem more appealing even if longer ones do use the same underlying methods. I also like to work at making a solution more generic for future purposes but I've come to the conclusion that (unless the extra credits mention it) there's no point because I'm only going to prejudice my solution. In the real world I would go for the more generic code and proper comments any day but for the purposes of the quiz I like to see solutions that do just as much as is asked of them and ideally fit on one page of my screen. -- Marcel

on 2007-04-09 16:25

On Apr 9, 6:18 am, "Rick DeNatale" <rick.denat...@gmail.com> wrote: > > OperatorPerms.each do |operatorsperm| > > expression=digitspart.zip(operatorsperm).flatten.join > > ... > > > I think I would be feeling very happy if I'd submitted this solution :) > > May I have the temerity to point out that I posted basically the same > solution, which I posted two hours before Ken's. > Indeed! Well, isn't too coincidental after all for me to have used the same mechanism. Great minds must think alike, no? Harrison Reiser

on 2007-04-09 16:28

Thanks for another fun Ruby Quiz. Here is my take on it, I did not see other solutions that used String formatting to generate the expressions. class String def unique_permutations # modified to get unique permutations # from http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/... # which says it was inspired by a RubyQuiz! :) return [self] if self.length < 2 perms = Hash.new 0.upto(self.length - 1) do |n| #rest = self.split('') rest = self.split(//u) # for UTF-8 encoded strings picked = rest.delete_at(n) rest.join.unique_permutations.each { |x| perms[picked + x] = nil } end perms.keys end end digits = ARGV[0] ops = ARGV[1] target = ARGV[2].to_i # pad ops list with spaces to match the number of slots between the digits ops = ops + " " * (digits.size - ops.size - 1) # build a format string with slots between the digits digits = digits.split("").join("%s") operator_perms = ops.unique_permutations operator_perms.each do |p| # build expression by inserting the ops into the format string, # after converting spaces to empty strings exp = digits % p.split("").map{|x|x.chomp(" ")} val = eval(exp) puts "*******************" if val==target puts exp + " = " + val.to_s puts "*******************" if val==target end puts puts "%d possible equations tested" % operator_perms.size Regards, Paul

on 2007-04-09 16:31

On Apr 9, 2007, at 4:35 AM, Robert Dober wrote: > BTW I want to have my ball back James, or adjust my handicap > please ;). I'm just glad you broke that code down for us. Now maybe I can read it to look smart when I write up the summary. ;) James Edward Gray II

on 2007-04-09 16:39

```
On 4/9/07, James Edward Gray II <james@grayproductions.net> wrote:
>
;)
```

on 2007-04-09 16:51

```
On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:
> My first quiz attempt ever so go easy on me :)
Welcome to Ruby Quiz.
James Edward Gray II
```

on 2007-04-09 17:05

On Apr 9, 8:25 am, "paul" <nova...@gmail.com> wrote: > perms = Hash.new > end > end > Clever use of hashes. I wrote a String#each_unique_permutation, but didn't think that it could be used like this. > # after converting spaces to empty strings > exp = digits % p.split("").map{|x|x.chomp(" ")} I like that you permute the ops string with extra spaces. Much simpler than something like digits.each_ordered_partition. Harrison Reiser

on 2007-04-09 17:07

```
On Apr 8, 2007, at 10:10 PM, Matt Hulse wrote:
> Comments are welcome, I'm here to learn!
Some things I saw while reading through your code:
* print "...\n" is just puts "..." in Ruby.
* Ruby has a command-line switch to enable a debuggin mode: -d.
Among other things, this sets $DEBUG to true. So instead of
commenting out print statements, just do something like:
puts ... if $DEBUG
You can then run with ruby -d ... when you want the output.
* You can swap values without a temporary variable in Ruby: array
[a], array[b] = array[b], array[a].
* When you set something and then go into an iterator to modify it,
you probably want inject() instead: (2..n).inject { |fac, n| fac * n }.
* The Ruby naming convention is to use snake_case for variables and
methods.
The above are just some suggestions. The code seems to work, which
is the most important part. Nice work.
James Edward Gray II
```

on 2007-04-09 17:15

On 4/9/07, Marcel Ward <wardies@gmail.com> wrote: > On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote: > > found = val == goal > puts "*****************" if found > puts "#{eqn} = #{val}" if verbose || goal == val > puts "*****************" if found > found_in_a_row = found ? found_in_a_row + 1 : 0 > > For the same number of lines, I find the second much easier to follow > without having to remember any state for the second time around. > There does not seem to be any advantage in placing the asterisk lines > together. (?) Not quite the same I think. I wrote it the way I did to cover the (admittedly probably rare case where two solutions occur one after the other. That's why the variable found_in_a_row is there. I wanted to see: ******** xxxxxx = 100 yyyyyy = 100 ******** instead of ******** xxxxxx = 100 ******** ******** yyyyyy = 100 ******** > underlying methods. I also like to work at making a solution more > generic for future purposes but I've come to the conclusion that > (unless the extra credits mention it) there's no point because I'm > only going to prejudice my solution. > > In the real world I would go for the more generic code and proper > comments any day but for the purposes of the quiz I like to see > solutions that do just as much as is asked of them and ideally fit on > one page of my screen. I see it as an opportunity to document my thoughts in solving the quiz, and thereby teach myself and others. The best way to learn is to teach. And, Frankly, I'm kind of an anti-golf advocate, except when I have a club in my hands instead of a keyboard at my finger-tips. Finally I figure that it's JEG II's choice as to how to summarize the solutions. Chacun a son goût! -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/

on 2007-04-09 19:02

On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote: > > ******** > xxxxxx = 100 > ******** > ******** > yyyyyy = 100 > ******** Aha, thanks for clarifying. I think this would be a prime candidate for a comment. Before someone else gets their mits on the code and starts refactoring inappropriately (like me). > > underlying methods. I also like to work at making a solution more > quiz, and thereby teach myself and others. The best way to learn is > to teach. I can't disagree with that - it's been my theory up until now but I have no idea how useful it's been to others. If I'm just turning people away with long posts then I'd prefer to shorten them down to meet the audience's expectations better. > And, Frankly, I'm kind of an anti-golf advocate, except when I have a > club in my hands instead of a keyboard at my finger-tips. > > Finally I figure that it's JEG II's choice as to how to summarize the solutions. > > Chacun a son goût! I'm definitely in favour of comments and readability. I guess I was just verbalising some inner thoughts and wondering how others try to find the right balance. -- Marcel

on 2007-04-09 19:12

On Apr 9, 2007, at 12:00 PM, Marcel Ward wrote: > On 09/04/07, Rick DeNatale <rick.denatale@gmail.com> wrote: > >> Finally I figure that it's JEG II's choice as to how to summarize >> the solutions. >> >> Chacun a son goût! > > I'm definitely in favour of comments and readability. I guess I was > just verbalising some inner thoughts and wondering how others try to > find the right balance. It can be tricky to know when to use them. A good comment can ease you right into some code. A bad comment can do the opposite and I even find that a good comment sometimes hurts completely obvious code. In general though, I like seeing them in Ruby Quiz solutions for two reasons: * It helps me understand the code. That's how I know if I want to write about it and it helps me know what to say if I do. * It helps others understand all the solutions I don't cover. Always a big win, I think. There's my two cents worth. James Edward Gray II

on 2007-04-09 19:21

Marcel Ward wrote: >> I see it as an opportunity to document my thoughts in solving the >> quiz, and thereby teach myself and others. The best way to learn is >> to teach. > > I can't disagree with that - it's been my theory up until now but I > have no idea how useful it's been to others. If I'm just turning > people away with long posts then I'd prefer to shorten them down to > meet the audience's expectations better. I say: go for long emails if you have to, but try to be as precise as you can. This has the "learning through teaching" effect, and helps to keep your emails at a manageable length. It is my opinion, that those, who can't be bothered to read a long explanation, won't read the documentation either, which results in somebody who can't be educated in the first place. Rest assured, if the topic interests me, I'll read a long email, too. > I'm definitely in favour of comments and readability. I guess I was > just verbalising some inner thoughts and wondering how others try to > find the right balance. Well, if the code is readable and speaks for itself, comments can be omitted. Otherwise, the comments should explain what the code does, not what it should do. I.e.: #Opening a file f = File.open("foo") ^ | is superfluous. #This does stuff to the passed argument bar def do_stuff(bar) #doing stuff to bar end ^ | Isn't superfluous, and aids debugging if the thing doesn't do what it should. And you know that it doesn't do what it is supposed to do, because your tests tell you that it doesn't. But such a thing merits it's own thread, I'd say. -- Phillip "CynicalRyan" Gawlowski http://cynicalryan.110mb.com/ Rule of Open-Source Programming #8: Open-Source is not a panacea.

on 2007-04-09 19:39

Weighing in about the comments and explanations of the quiz answers: the comments are good, and important especially when using tricks. Especially considering that I'm not alone in suggesting that ruby-newbies I meet read old quizzes and the solutions that were posted to learn more about Ruby. The thing is, simple, or not so simple, code is sometimes best left uncommented so that the reader is forced to parse it and figure out exactly what's going on. It aides in their understanding. And yes I know I'm horribly guilty of not entering enough comments in myself, especially in some of the ugly code. :) --Kyle

on 2007-04-09 19:56

Robert Dober wrote: > point ;) > irb is our friend of course, so let us hack away: Thanks for the explanation Robert. After reading over your email, I also went into irb and stepped through the process even more thoroughly. I'm amazed at how changing the base and then using string translation makes the problem so simple.

on 2007-04-10 06:17

James Gray wrote: > The three rules of Ruby Quiz: =] Here is my solution. You will forgive the extension of the file, but this quiz was an excuse for me to learn and play with new things, like OptParse. I rather uploaded it in a pastie. My solution handles extra credits, and my own suggestions except parenthesis precedence. With full options, it runs very slow, because the number of permutations and combinations grows n! As an example, a run with these options $ ruby quiz119.rb --o +,-,*,/ --f --m --v --d 1234567 produces 123+4+5*0.67 = 130.35 123+4+5*6.7 = 160.50 0.123+4+5*67 = 339.12 ..... 17 times target reached, out of 217224 equations tested: 123*4-56*7 = 100.00 1+23+4+5+67 = 100.00 1+2+34+56+7 = 100.00 1+23-4+56/0.7 = 100.00 12+0.3*45*6+7 = 100.00 12+3*4.5*6+7 = 100.00 12+3*45*0.6+7 = 100.00 -1-234+5*67 = 100.00 1*23*4+56/7 = 100.00 -1/2+34-0.5+67 = 100.00 -1+0.2*34*5+67 = 100.00 -1+2*3.4*5+67 = 100.00 -1+2*34*0.5+67 = 100.00 1*23*4-5+6+7 = 100.00 -1-2+34*5-67 = 100.00 -1/2+3/0.4/5*67 = 100.00 -1/2+3/4/0.5*67 = 100.00 Total run time: 50.844356 seconds Trying to do that for digits 1 to 9 is a craziness @.@ Here is the file: http://pastie.caboo.se/52702

on 2007-04-10 23:55

My first posted solution - hope it's ok! ## Start target.rb class TargetFinder attr_reader :inputs, :operators def initialize(inputs, operators) self.inputs = inputs self.operators = operators reset end # Clear out cached, calculated data def reset @equations = nil @results = nil end # Only allow digits as input def inputs= new_inputs @inputs = new_inputs.gsub /\D/, '' reset end # Only the +, - and * operators are really safe to use with this approach def operators= new_ops @operators = new_ops.gsub(/[^+*-]/, '').split(//) reset end # Loop through our results putting the required stars around the correct lines def get_to target calculate if @results.nil? @results.each do |eq, result| puts "*" * 30 if result == target.to_i puts "#{eq} = #{result}" puts "*" * 30 if result == target.to_i end puts "%d equations tested" % @equations.length end # Calculate all of the possible equations given a set of inputs def calculate @equations = self.class.permutate(@inputs, @operators) @results = {} @equations.each do |eq| @results[eq] = eval(eq) end end # Here's the workhorse, recursively calculates all possible equations from an input string and operators def self.permutate(inputs, operators) return [inputs] if operators.empty? arr = [] # Loop through all the possible 'first' value/operator pairs operators.uniq.each do |op| other_operators = operators.without(op) (1..inputs.length-operators.length).each do |i| # Find all possible endings from the remaining inputs and operators, and prepend this beginning to all of them permutate(inputs[i..-1], other_operators).each do |permutation| arr << "#{inputs[0...i]} #{op} #{permutation}" end end end arr end end # A long-winded way of removing a single item from an array which may have duplicates # Almost certainly not the best way of doing this but good enough class Array def without item new_array = [] found = false each do |x| if x == item new_array << x if found found = true next end new_array << x end new_array end end if $0 == __FILE__ inputs = ARGV.shift || "123456789" target = ARGV.shift || "100" operators = ARGV.shift || "+--" finder = TargetFinder.new(inputs, operators) finder.get_to target end

on 2007-04-11 05:10

On Mon, 09 Apr 2007 21:47:43 +0900, Christian Neukirchen wrote: >>> without thinking too much or locating Knuth on the bookshelve. Writing >>> (00000000..'22222222'.to_i(3)).map { |x| x.to_s(3).rjust(8, "0"). >> >> (It doesn't keep maintain references to the bad combinations of >> operators, allowing the GC to reclaim them earlier.) > > Yes, but that confuses the application logic. I don't think it will > save memory compared to yours, you are #to_s'ing a lot more than me! I didn't claim that it saves memory by allocating less. It saves memory by retaining less references, so it can GC earlier. --Ken

on 2007-04-11 05:40

On Mon, 09 Apr 2007 21:18:16 +0900, Rick DeNatale wrote: >> OperatorPerms.each do |operatorsperm| >> expression=digitspart.zip(operatorsperm).flatten.join >> ... >> >> I think I would be feeling very happy if I'd submitted this solution :) > > May I have the temerity to point out that I posted basically the same > solution, which I posted two hours before Ken's. I typically compose my solution on Friday afternoon, and sit on it for two days before posting to ruby-talk. When I post on Sunday, I do so before reading any other solutions out there. After posting, I browse the solutions, marvel at the clever ones, and usually notice that a bunch of people have come up with the same idiomatic solution as me, thereby suggesting that: 1) those people are also interested in clear idiomatic code 2) I'm unlikely to be the one summarized. --Ken

on 2007-04-11 09:59

On 4/11/07, Ken Bloom <kbloom@gmail.com> wrote: > >> > I typically compose my solution on Friday afternoon, and sit on it for > two days before posting to ruby-talk. When I post on Sunday, I do so > before reading any other solutions out there. After posting, I browse the > solutions, marvel at the clever ones, and usually notice that a bunch of > people have come up with the same idiomatic solution as me, thereby > suggesting that: > 1) those people are also interested in clear idiomatic code > 2) I'm unlikely to be the one summarized. Cheer up Ken;) http://www.rubyquiz.com/quiz110.html

on 2007-04-16 02:30

Note: Like I said in my submission to #120, this seems not to have gotten through when I sent it last week, and I just noticed. So here it is again (though I have changed it a bit since then - originally I had an Operation called Cat that concatenated adjacent numbers; now that's done separately). ------------------------ Like my submission for last week's quiz, this one grew too long. But there's some things I like about it, so here it is. First I wrote an algorithm to generate all permutations of an Array, but excluding those that are the same as others ('--+' and '--+' won't both be generated). To do this, for each unique element of the Array, I append it to all results of running it recursively on the rest (if that's worded confusingly, look at the code at the top of array_stuff.rb). I then build an Operator class, which is just a Proc with a name so to_s can be, say, '+' instead of '#<Proc:0xb7acef88...>'. All Operators sit inside an Array, and take two arguments: the Array they're in, and their index within that Array. When called, they modify the Array. For example: a = [1, Add, 2] The Add Operator can then be called by either of these: Add[a, 1] a.exec_op_at!(1) and afterwards a == [3]. First I build an Array containing all the initial Operators (Sub, Sub, Add). This Array is what I call each_uniq_permutation on. Each perm then gets mixed in to the data by the each_mix method in array_stuff. Example: nums = [1, 2, 3] ops = [Add, Sub] ops.each_uniq_permutation will yield [Add, Sub] and [Sub, Add]. Then calling: nums.each_mix(ops) will yield each of: 1 2 Add Sub 3 1 Add 2 Sub 3 1 Add Sub 2 3 ... etc etc Some will be valid expressions, many won't. Each Operator also has a precedence. For each Operator in the Array from highest to lowest precedence, we let it modify the Array. [1, Add, 2, Mult, 2, 3] -> [1, Add, 2, Mult, 23] # concat adjacent numbers -> [1, Add, 46] # Mult has higher precedence than Add -> [47] One thing I don't like about my code is that I scan through the expression Arrays a lot, like for finding the next adjacent numbers to concatenate or the next Operator to apply. Ops can have arbitrary effects on the Array, so we need to watch everything. Maybe an Op expands to other Ops or something. I thought of implementing this in different ways, like specifically keeping an ordered-by-precedence list of all Ops in the expression, but didn't get to it. Oh, and I've implemented Ops for addition, subtraction, multiplication, division, and parenthesis. Here's the code: # --------------------------------------------------------------------------- # array_stuff.rb # Ruby Quiz 119: Getting to 100 class Array # Yield once for each unique element of this Array. def each_uniq_element self.uniq.each { |e| yield e } end # Like Array delete(), but only delete a single occurrence of e instead of # all of them. Also unlike delete(), it returns a new Array instead of # modifying this one (why isn't delete() named delete!() ?) def delete_one(e) arr = self.clone i = arr.index(e) arr.delete_at(i) if not i.nil? arr end # Generates all unique permutations of this Array, yielding each one. # By 'unique' I mean both permutations [...,x,...,y,...] and [...,y,...,x,...] # will not be generated if x == y. # (wonder if there's a non-recursive way to do this?) def each_uniq_permutation if self.size.zero? yield [] else self.each_uniq_element do |e| self.delete_one(e).each_uniq_permutation do |perm_part| yield([e] + perm_part) end end end end # Find the lowest index of val, starting from index start. def index_past(val, start) (start...self.size).each { |i| return i if self[i] == val } nil end # Replace all values from indices i through j (inclusive) with the single # value val. def replace_at!(i, j, val) raise 'Bad indices given' if i < 0 or j < i or j >= self.size self.slice!(i, j-i+1) self.insert(i, val) end # "Mix together" self and arr in all possible ways that preserve the order of # each, yielding the results. def each_mix(arr) if self.empty? then yield arr.clone elsif arr.empty? then yield self.clone else self.slice(1, self.length).each_mix(arr) do |mix| yield [self.first] + mix end self.each_mix(arr.slice(1, arr.length)) do |mix| yield [arr.first] + mix end end end end # --------------------------------------------------------------------------- # ops.rb # Ruby Quiz 119: Getting to 100 require 'array_stuff' require 'enumerator' class Symbol # This nice ol' trick. def to_proc proc { |obj, *args| obj.send(self, *args) } end end class Array # Return the index of the next-highest-precendence operator within this Array. def next_op_index # Yuck... a linear search. op_i = nil self.each_index do |i| if self[i].is_a?(Proc) and (op_i.nil? or Ops.precedence_of(self[i]) > Ops.precedence_of(self[op_i])) op_i = i end end op_i end # Execute the operation that is at the given index on self. def exec_op_at!(index) raise 'Not a Proc' if not self[index].is_a? Proc self[index][self, index] # I like this line.. end # Concatenate any adjacent numbers. Repeat until none are left. def concat_nums!(base = 10) # There's gotta be a much, much better way to do this... i = 0 while i < self.size-1 while self[i].is_a? Numeric and self[i+1].is_a? Numeric # Would logs & exponents be better than strings for this? self[i] = (self[i].to_s(base) + self[i+1].to_s(base)).to_i(base) self.delete_at(i+1) end i += 1 end end # Process all operators in self, from highest-precedence to lowest. Along the # way, adjacent numbers will be concatenated (which always has higher # precedence than any operators). def process_ops! concat_nums! op_i = self.next_op_index while not op_i.nil? self.exec_op_at! op_i concat_nums! op_i = self.next_op_index end self end # Just like process_ops!, but return a new Array instead of working on self. def process_ops arr = self.clone arr.process_ops! arr end end module Ops # Here lie blocks of incense, burning for the Proc God. # Inhale. # Proc with a name for prettier to_s. class Operator < Proc def initialize(name) super() { yield } @name = name.to_s end def to_s; @name; end end # Produces an Operator that sits between two numbers and replaces them. # For example, [1,Add,2] => [3] # Its name will be op.to_s. BinaryOp = lambda do |op| Operator.new(op.to_s) do |list, index| num_left, num_right = list[index-1], list[index+1] raise 'Not numeric.' if not num_left.is_a? Numeric or not num_right.is_a? Numeric list.replace_at!(index-1, index+1, op.to_proc[num_left, num_right]) end end # Operators that sit between two numbers and perform arithmetic on them. Mult = BinaryOp[:*] Div = BinaryOp[:/] Add = BinaryOp[:+] Sub = BinaryOp[:-] # Operator to group things. LeftParen = Operator.new('(') do |list, left_paren_index| right_paren_index = list.index_past(RightParen, left_paren_index+1) raise 'No right paren' if right_paren_index.nil? contained = list.slice!(left_paren_index, right_paren_index - left_paren_index + 1) contained.shift; contained.pop # Remove parens on ends contained.process_ops! list.insert(left_paren_index, *contained) end # Does nothing; LeftParen takes care of everything. RightParen = Operator.new(')') { |list, index| } # Precedence of operators. Precedence = { LeftParen => 3, RightParen => 2, Mult => 1, Div => 1, Add => 0, Sub => 0 } # Get the precedence of the given Operation. Higher is more important. def Ops.precedence_of(op) Precedence[op] end end # --------------------------------------------------------------------------- # getting_to_100.rb # Ruby Quiz 119: Getting to 100 require 'array_stuff' require 'ops' # Main method for this Quiz. Print out one line for each valid way of arranging # nums and ops into an expression. The marker will appear around results # matching target. # # Arguments: # nums: Something that, when to_a is called on it, returns an Array of # numbers. # ops: An Array of Operators. # target: Target number. # marker: String to print above & below target hits. def get_to(nums, ops, target = 100, marker = '************************') nums = nums.to_a num_tested = num_valid = num_found = 0 # Permute the ops in all uniq ways, and mix them with nums to generate # expressions. ops.each_uniq_permutation do |op_perm| nums.each_mix(op_perm) do |expr| num_tested += 1 begin result = expr.process_ops num_valid += 1 if result.size == 1 if result.first == target num_found += 1 puts marker puts "#{num_valid}: #{expr.join} = #{result.join(',')}" puts marker else puts "#{num_valid}: #{expr.join} = #{result.join(',')}" end else # The list didn't collapse all the way to a single element. #$stderr.puts 'Warning: operation did not collapse:' #$stderr.puts "#{num_tested}: #{expr.join} = #{result.join(',')}" end rescue Object => ex # Some operation didn't work. Perhaps non-matching parens. Maybe this # should be handled another way.. #$stderr.puts 'Warning: operation failed.' #$stderr.puts ex end end end puts '----------------' puts "#{num_tested} possible expression were generated." puts " Of those, #{num_valid} were valid." puts " Of those, #{num_found} matched the target." end # Example from the Quiz. #get_to( (1..9), [Ops::Sub, Ops::Sub, Ops::Add] ) # Example showing off parenthesis. #get_to( (1..3), [Ops::Add, Ops::Mult, Ops::LeftParen, Ops::RightParen], 9 ) # ---------------------------------------------------------------------------