From: Jesse Merriman Date: 2007-04-16T09:29:27+09:00 Subject: [QUIZ][SOLUTION] Getting to 100 (#119) 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 '#'. 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 ) # --------------------------------------------------------------------------- -- Jesse Merriman jessemerriman@warpmail.net http://www.jessemerriman.com/