Prev: any way to use RSA1 for ssh in ruby?
Next: importing config files
From: Daniel Moore on 8 Apr 2010 17:16
[Note: parts of this message were removed to make it a legal post.]

Many members of the Ruby Community contributed solutions to this quiz. Some
long time veterans as well as first time contributors. Thanks everyone for
the great turnout!

`Set#divide` is an interesting method that came up during the discussion. I
was not previously familiar with it, time to learn.

> From Ruby-Doc[2]:
> Divides the set into a set of subsets according to the commonality defined
> by the given block.
>
> If the arity of the block is 2, elements o1 and o2 are in common if
> block.call(o1, o2) is true. Otherwise, elements o1 and o2 are in common
> if block.call(o1) == block.call(o2).
> e.g:
>
> require 'set'
> numbers = Set[1, 3, 4, 6, 9, 10, 11]
> set = numbers.divide { |i,j| (i - j).abs == 1 }
> p set # => #<Set: {#<Set: {1}>,
> # #<Set: {11, 9, 10}>,
> # #<Set: {3, 4}>,
> # #<Set: {6}>}>

I didn't quite get it at first so I went to the console and tried some other
examples.

set = numbers.divide { |i,j| (i - j).abs == 2 }
=> #<Set: {#<Set: {10}>, #<Set: {1, 3}>, #<Set: {6, 4}>, #<Set: {11,
9}>}>

Ok, so the first example gets contiguous runs (numbers that are 1 apart),
and the second example gets contiguous skip runs (runs of numbers that are 2
apart).

Now to test out the single argument version:

set = numbers.divide { |i| i%2 }
=> #<Set: {#<Set: {11, 1, 3, 9}>, #<Set: {6, 4, 10}>}>

Dividing a set into odds and evens. A core component of this quiz is
grouping sets; this may come in handy.

brabuhr's first solution uses this method and is a good illustration of the
principle behind the problem.

require 'set'

class Set
def intersect?(other)
other.each { |o| return true if include?(o) }
false
end
end

def distinct_sets(array_of_arrays)
set_of_sets = array_of_arrays.map{|a|
a.to_set
}.to_set

set_of_sets.divide{|i, j|
i.intersect?(j)
}.map{|s|
s.flatten.to_a
}
end

In this solution an instance method `intersect?` is added to `Set`. This
allows us to `divide` all the sets that share an element into groups. Then
all that is left is to merge the groups of sets (`Set#flatten` takes care of
that) and to present the result as an array of arrays to match how the
output was specified in the quiz.

During the quiz discussion a full set of test cases was developed. This
enabled everyone to check and verify the accuracy of their solutions. The
test suite was provided by Rob Biedenharn and uses Shoulda[1], a testing
framework that provides additional helpers, macros, and assertions to the
Test::Unit framework.

Another benefit the testing provided was the ability to focus on the speed
at which the solutions run. When you have a full test suite you can modify
code without fear of breaking things in order to optimize and squeeze out
that last bit of speed, or conversely, to clean things up to improve code
readability, knowing that you have a safety net of tests to catch any errors
introduced.

There were many, many more solutions to this week's quiz. The principle of
grouping and merging the sets is followed by all solutions, with varying
tradeoffs between execution speed and readability. brabuhr had two more,
Benoit Daloze had two, lith had two, Rob Biedenharn had one, and first time
correspondent Johnathon Wright had one. Please be sure to take a look inside
the archived files, there are lots of good solutions in there.

Special thanks to everyone who participated in the quiz!

Distinct Sets (#225) - Solutions[3]

[1]: http://github.com/thoughtbot/shoulda
[2]: http://ruby-doc.org/core/classes/Set.html#M001626
[3]: http://rubyquiz.strd6.com/quizzes/225.tar.gz

 | 
Pages: 1
Prev: any way to use RSA1 for ssh in ruby?
Next: importing config files