···
------------------------
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 )
# ---------------------------------------------------------------------------
--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/
in accordance with this