225 Distinct Sets

Description

Aloha Rubyists,

This week’s quiz comes from Ruby Quiz Suggestions MVP Martin DeMello.

(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!

Summary

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-Doc2: 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 Shoulda1, 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 attached files, there are lots of good solutions in there.

Special thanks to everyone who participated in the quiz!

Distinct Sets (#225) - Solutions


Friday, December 04, 2009