R

#### Ruby Quiz

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

# 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 Neukirchen 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...