Re: [QUIZ][SUMMARY] Distinct Sets (#225)

Daniel,
=A0
I would like to know how to install ruby and rails on my computer.
but the trouble that I am having is that all the files are zipped up
and can use them. if you have a sloution for this email me back.
[e-mail]
=A0
James=A0

--- On Thu, 4/8/10, Daniel Moore <[e-mail]> wrote:


From: Daniel Moore <[e-mail]>
Subject: [QUIZ][SUMMARY] Distinct Sets (#225)
To: "ruby-talk ML" <[e-mail]>
Date: Thursday, April 8, 2010, 3:16 PM


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 define=
d
> 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) =3D=3D block.call(o2).
> e.g:
>
>=A0 =A0=A0=A0require 'set'
>=A0 =A0=A0=A0numbers =3D Set[1, 3, 4, 6, 9, 10, 11]
>=A0 =A0=A0=A0set =3D numbers.divide { |i,j| (i - j).abs =3D=3D 1 }
>=A0 =A0=A0=A0p set=A0=A0=A0# =3D> #<Set: {#<Set: {1}>,
>=A0 =A0 =A0 =A0 =A0 =A0=A0=A0#=A0 =A0 =A0 =A0 =A0 =A0 #<Set: {11, 9, 10}>,
>=A0 =A0 =A0 =A0 =A0 =A0=A0=A0#=A0 =A0 =A0 =A0 =A0 =A0 #<Set: {3, 4}>,
>=A0 =A0 =A0 =A0 =A0 =A0=A0=A0#=A0 =A0 =A0 =A0 =A0 =A0 #<Set: {6}>}>

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

=A0 =A0 set =3D numbers.divide { |i,j| (i - j).abs =3D=3D 2 }
=A0 =A0 =3D> #<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:

=A0 =A0 set =3D numbers.divide { |i| i%2 }
=A0 =A0 =3D> #<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.

=A0 =A0 require 'set'

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

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

=A0 =A0 =A0 set_of_sets.divide{|i, j|
=A0 =A0 =A0 =A0 i.intersect?(j)
=A0 =A0 =A0 }.map{|s|
=A0 =A0 =A0 =A0 s.flatten.to_a
=A0 =A0 =A0 }
=A0 =A0 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 o=
f
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 error=
s
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 insid=
e
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
=0A=0A=0A