Getting to 100 (#119)

[bbazzarrakk]

The three rules of Ruby Q.:

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 Q. 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 T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Gavin K.

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/200711/index.html

[bbazzarrakk]

On 4/6/07, Ruby Q. [email protected] 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/200711/index.html

For the rest sounds like fun.

Cheers
Robert

[bbazzarrakk]

On Apr 6, 2007, at 8:32 AM, Robert D. 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 G. II

[bbazzarrakk]

On Apr 6, 12:11 pm, “Kyle S.” [email protected] wrote:

OK only 43 hours to go…

Stupid non spoiler rule

Did you get all the extra credit already?

[bbazzarrakk]

Everything but the arbitrary ordering and number of digits.

And it can run in O(n) time

[bbazzarrakk]

[Ruby Q. [email protected], 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?

[bbazzarrakk]

On Apr 6, 1:53 pm, Carlos [email protected] 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.

[bbazzarrakk]

OK only 43 hours to go…

Stupid non spoiler rule

[bbazzarrakk]

James G. wrote:

The three rules of Ruby Q.:

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

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

[bbazzarrakk]

Phrogz wrote:

On Apr 6, 1:53 pm, Carlos [email protected] 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.

[bbazzarrakk]

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 F.'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/

[bbazzarrakk]

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 W. <wardies ^a-t^ gmaildotcom>

Saturday, 2006-04-07

Solution for Ruby Q. #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 **”

[bbazzarrakk]

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}”}

[bbazzarrakk]

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/ruby-talk/139290

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

"
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

[bbazzarrakk]

On 4/8/07, Kyle S. [email protected] 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

[bbazzarrakk]

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

[bbazzarrakk]

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

[bbazzarrakk]

On Fri, 06 Apr 2007 21:55:37 +0900, Ruby Q. wrote:

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone on Ruby T. 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}”

[bbazzarrakk]

=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#787lilith:~/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

[bbazzarrakk]

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