From: Daniel Moore <yahivin@...>
Date: 2009-11-21T11:23:39+09:00
Subject: [QUIZ] Distinct Sets (#225)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have elapsed from the time this message was
sent.

2.  Support Ruby Quiz by submitting ideas and responses
as often as you can.

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby Talk follow the discussion.  Please reply to
the original quiz message, if you can.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

Suggestions?: http://rubyquiz.strd6.com/suggestions

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Distinct Sets (#225)

Aloha Rubyists,

This week's quiz comes from Ruby Quiz Suggestions MVP Martin DeMello[1].

[based on a surprisingly tricky stackoverflow problem]

You have an list of sets, which you want to transform by the following
method: if any two sets have a common element, merge them into a
single set. You will be left with a reduced list partitioning all the
elements into sets where every set is disjoint from every other.

For example:

Start: 0:[D E G]
       1:[C J K M]
       2:[K M]
       3:[H]
       4:[D H L R]
       5:[G L]

merging 1 and 2 since they have K and M in common:
=> [D E G] [C J K M] [H] [D H L R] [G L]

merging 2 and 3 since they have H in common:
=> [D E G] [C J K M] [D H L R] [G L]

merging 0 and 2 (D)
=> [D E G H L R] [C J K M] [G L]

merging 0 and 2 (G, L)
=> [D E G H L R] [C J K M]

Which is our answer.

The tricky bit is to do it as efficiently as possible (in an
algorithmic sense; in actual ruby code the efficiency depends a lot on
which methods run in ruby and which in C), but even without that it's
a fun problem to solve.

Here are a few input/output pairs to help test your program:

[["G", "J", "N"], ["D", "F", "G", "K"], ["E", "H"], ["B", "C", "J",
"L", "Q"], ["C", "M"]]
=> [["B", "C", "D", "F", "G", "J", "K", "L", "M", "N", "Q"], ["E", "H"]]

[["A", "C", "E", "G", "H"], ["B", "I", "M"], ["E", "M", "O"]]
=> [["A", "B", "C", "E", "G", "H", "I", "M", "O"]]

[["D", "E", "J", "L"], ["F", "K"], ["L", "M"], ["I", "K"], ["I", "K"]]
=> [["D", "E", "J", "L", "M"], ["F", "I", "K"]]

[["B", "E", "L", "M"], ["B", "I", "L", "O", "P"], ["A", "J", "O",
"P"], ["A", "D", "F", "L"]]
=> [["A", "B", "D", "E", "F", "I", "J", "L", "M", "O", "P"]]

[["E", "G", "K"], ["A", "C", "I", "J", "N"], ["C", "J", "M", "N"]]
=> [["E", "G", "K"], ["A", "C", "I", "J", "M", "N"]]

[["A", "D", "E", "H"], ["D", "N", "P"], ["D", "I", "L", "P"]]
=> [["A", "D", "E", "H", "I", "L", "N", "P"]]

[["E", "F", "K", "N", "O"], ["A", "B", "C", "J", "P"]]
=> [["E", "F", "K", "N", "O"], ["A", "B", "C", "J", "P"]]

[["C", "H", "M"], ["D", "F", "L"], ["A", "E", "J", "O"], ["C", "H"],
["J", "K", "M"], ["A", "N", "Q", "T"]]
=> [["A", "C", "E", "H", "J", "K", "M", "N", "O", "Q", "T"], ["D", "F", "L"]]

Have fun!

[1]: http://zem.novylen.net


P.S. I'm pretty swamped right now which is causing delay on
summarizing the recent quizzes. If anyone would like to write a guest
summary I would much appreciate it! Sometimes you never know where
help will come from until you ask for it. Also, special thanks to
Martin and everyone else who helps by submitting ideas and quizzes!

-- 
-Daniel
http://rubyquiz.strd6.com