Finding expression that evaluate to 100

hundred.rb

require 'pp'
require 'benchmark'

# compute all possible expressions to the given string of digits to a given set of operations.
# the digits are kept in order
#
# ex. 1234
# generates: 1234, 1+234, 1-234, 12+34, 123-4...
#
# but selects only expressions that evaluate to a given value
#

class StrategyA
  def compute(digits, operators, accumulator=[])
    if digits.empty?
      accumulator
    else
      compute(digits, operators, permutation(accumulator, operators, digits.shift))
    end
  end

  private

  def permutation(a, operators, b)
    if a.empty?
      [b]
    else
      a.map do |a1|
        operators.map { |op| [a1, op, b].join }
      end.flatten
    end
  end
end

class StrategyB
  def compute(digits, operators)
    operations = digits.size - 1

    expressions = operators.repeated_permutation(operations).map do |sequence|
      digits.zip(sequence).join
    end
  end
end

def run(string, operators, value, strategy)
  digits = string.split(//)
  expressions = strategy.compute(digits, operators)
  expressions.select { |expr| eval(expr) == value }
end

string = "1234567890"
operators = ["-", "+", ""]

Benchmark.bm do |x|
  x.report("A") { run(string, operators, 100, StrategyA.new) }
  x.report("B") { run(string, operators, 100, StrategyB.new) }
end

#        user     system      total        real
# A  0.220000   0.010000   0.230000 (  0.226515)
# B  0.300000   0.010000   0.310000 (  0.319602)