[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 '#<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
[e-mail]
http://www.jessemerriman.com/