Forum: Ruby Getting to 100 (#119)

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-04-12 15:01
(Received via mailing list)
This was a popular problem and we saw many different ways to go about
it.  The discussion on the mailing list was also very good, with many
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
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"
  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

  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
they can come up in and Dennis chose to just hardcode those in the OPS

The other problem is about partitioning.  You need to divide the digits
four groupings that you can insert the three operators between.  Again,
pretty much hardcoded the logic for this using three nested iterators.
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
From there, the expression is constructed, eval()ed to get an answer,
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
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
      # which says it was inspired by a RubyQuiz! :)
      return [self] if self.length < 2
      perms =

      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


  digits = ARGV[0]
  ops = ARGV[1]
  target = ARGV[2].to_i

  # pad ops list with spaces to match the number of slots between the
  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
  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
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

The next two lines are the interesting part.  Paul counts the number of
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
the position count.  Then the digit list is transformed into a printf()
pattern that will insert an operator, or extra space, between each

From there it just takes one call to the unique_permutations() method to
the choices.  Paul's output code is very similar to the code we saw from

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
counting.  You see, counting from 00000000 (a pretty way to show 0 with
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
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
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...
This topic is locked and can not be replied to.