# Getting to 100 (#119)

**URL:** <https://www.ruby-forum.com/t/getting-to-100-119/91806>\
**Category:** Ruby\
**Created:** [April 12, 2007, 3:01pm UTC](https://www.ruby-forum.com/t/getting-to-100-119/91806 "2007-04-12T15:01:25Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [April 12, 2007, 3:01pm UTC](https://www.ruby-forum.com/t/getting-to-100-119/91806/1 "2007-04-12T15:01:25Z")

</div>

This was a popular problem and we saw many different ways to go about  
solving  
it. The discussion on the mailing list was also very good, with many  
ideas  
shared and explained.

I’m going to go through a few solutions today, because they are not  
overly long  
and I think we can learn something from each of them. Let’s begin with  
some  
code by Dennis Frommknecht. Here’s the entire solution:

#!/usr/bin/env ruby -W

# This solution uses 3 nested loops to divide the

# numbers into 4 groups (using regular expressions).

# Then the 3 allowed combinations of plus and minus

# are inserted between the groups.

# Finally the result is calculated using eval

NUMBERS = “123456789”  
CORRECT\_RES = 100  
OPS = [[‘+’, ‘-’, ‘-’],  
[‘-’, ‘+’, ‘-’],  
[‘-’, ‘-’, ‘+’]]

num\_of\_ops = OPS[0].length  
equ\_counter = 0

1.upto(NUMBERS.length - num\_of\_ops) do |i|  
1.upto(NUMBERS.length - num\_of\_ops - i + 1) do |j|  
1.upto(NUMBERS.length - num\_of\_ops - i + 1 - j + 1) do |k|  
if NUMBERS.match(/(\d{#{i}})(\d{#{j}})(\d{#{k}})(\d+)/) then  
OPS.each do |o|  
command = “#{$1} #{o[0]} #{$2} #{o[1]} #{$3} #{o[2]} #{$4}”  
res = eval command  
equ\_counter += 1  
puts “_" \* 15 if res == CORRECT\_RES  
puts “#{command} = #{res}”  
puts "_” \* 15 if res == CORRECT\_RES  
end  
end  
end  
end  
end

puts “#{equ\_counter} possible equations tested”

There are really two aspects to solving the base quiz. First, you need  
to find  
the possible permutation of the operators. There are really only three  
orders  
they can come up in and Dennis chose to just hardcode those in the OPS  
constant.

The other problem is about partitioning. You need to divide the digits  
into  
four groupings that you can insert the three operators between. Again,  
Dennis  
pretty much hardcoded the logic for this using three nested iterators.  
The  
interesting side of this solution though is how they work.

Basically, Dennis just counts off some number of digits from the front  
of the  
line. Then he counts of some number of digits after that. A third  
count is  
made for some number of digits after that, ensuring we leave at least  
one at the  
end. This gives us three lengths, which one Regexp turns into four  
groups.  
From there, the expression is constructed, eval()ed to get an answer,  
and  
finally printed.

This solution does a good job of showing the process, but there are some  
shortcuts to be found. For example, if you move from considering just  
the  
ordering of the three operators to the actual positioning of the three  
operators, you can drop the partitioning step altogether.

Let me use Paul’s code to show you what I mean:

class String  
def unique\_permutations  
# modified to get unique permutations from  
#  
[http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139858](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/139858)  
# which says it was inspired by a RubyQuiz! 🙂  
return [self] if self.length \< 2  
perms = Hash.new

```
  0.upto(self.length - 1) do |n|
    rest = self.split(//u) # for UTF-8 encoded strings
    picked = rest.delete_at(n)
    rest.join.unique_permutations.each { |x| perms[picked + x] = nil 

```

}  
end

```
  perms.keys
end

```

end

digits = ARGV[0]  
ops = ARGV[1]  
target = ARGV[2].to\_i

# pad ops list with spaces to match the number of slots between the

digits  
ops = ops + " " \* (digits.size - ops.size - 1)

# build a format string with slots between the digits

digits = digits.split(“”).join(“%s”)

operator\_perms = ops.unique\_permutations  
operator\_perms.each do |p|  
# build expression by inserting the ops into the format string,  
# after converting spaces to empty strings  
exp = digits % p.split(“”).map{|x|x.chomp(" ")}  
val = eval(exp)  
puts “_**" if val==target  
puts exp + " = " + val.to\_s  
puts "**_” if val==target  
end  
puts  
puts “%d possible equations tested” % operator\_perms.size

Paul’s permutation code is the first new element that jumps out at us  
here. It  
works by recursively combining smaller and smaller permutations until it  
has  
generated all possible combinations. The permutations are stored in  
Hash keys  
so duplicates will automatically be eliminated.

Next we see that Paul nails pretty much all of the extra credit by  
importing the  
digits, operators, and target from command-line parameters. This means  
that he  
can’t hardcode any logic, because he can’t count on what will be passed  
to his  
script.

The next two lines are the interesting part. Paul counts the number of  
spaces  
between all the digits. These are the positions in which operators need  
to be  
placed. Paul pads the operator list to include extra spaces, so it will  
match  
the position count. Then the digit list is transformed into a printf()  
style  
pattern that will insert an operator, or extra space, between each  
number.

From there it just takes one call to the unique\_permutations() method to  
walk  
the choices. Paul’s output code is very similar to the code we saw from  
Dennis  
earlier.

Going one step further, let’s examine how Christian N. walked  
the same  
position list:

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

This code does the same permutation of positions Paul’s code did, using  
simple  
counting. You see, counting from 00000000 (a pretty way to show 0 with  
eight  
positions) to whatever number ‘22222222’.to\_i(3) is, in base 3, will  
yield all  
possible combinations of 0s, 1s, and 2s. Christian then culls the list  
for the  
proper mixes of operators and transliterates those digits to operators  
or  
spaces. The rest of the code we have seen before.

Together these solutions show quite a few options for handling  
permutations in  
Ruby. Another common option from the submissions I didn’t show was to  
load an  
external library that handles permutations. This is a great option in  
practice,  
because you get road-tested code, but I wanted to show how you might  
handle such  
a thing for this summary.

My thanks to all the people who sent in permutations of Ruby code to  
solve this  
permutations problem. They are great stuff.

Tomorrow’s problem is something you can handle on your fingers…