From: brabuhr@...
Date: 2009-11-22T01:50:35+09:00
Subject: Re: [QUIZ] Distinct Sets (#225)

On Fri, Nov 20, 2009 at 9:23 PM, Daniel Moore <yahivin@gmail.com> wrote:
>
> ## 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.

$ ruby -v 225.rb
ruby 1.8.2 (2004-12-25) [powerpc-darwin8.0]
Loaded suite 225
Started
.
Finished in 0.059557 seconds.

1 tests, 10 assertions, 0 failures, 0 errors

But, I cheated a bit in my assertions; sorting the expected and actual
values before asserting them equal:

class TestCase225 < Test::Unit::TestCase
  def tests
    assert_equal(
      [
        %w{ D E G H L R },
        %w{ C J K M }
      ].sort,
      distinct_sets(
        [
          %w{ D E G },
          %w{ C J K M },
          %w{ K M },
          %w{ H },
          %w{ D H L R },
          %w{ G L }
        ]
      ).sort
    )

    assert_equal(
      [
        ["B", "C", "D", "F", "G", "J", "K", "L", "M", "N", "Q"],
        ["E", "H"]
      ].sort,
      distinct_sets(
        [
          ["G", "J", "N"],
          ["D", "F", "G", "K"],
          ["E", "H"],
          ["B", "C", "J", "L", "Q"],
          ["C", "M"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["A", "B", "C", "E", "G", "H", "I", "M", "O"]
      ].sort,
      distinct_sets(
        [
          ["A", "C", "E", "G", "H"],
          ["B", "I", "M"],
          ["E", "M", "O"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["D", "E", "J", "L", "M"],
        ["F", "I", "K"]
      ].sort,
      distinct_sets(
        [
          ["D", "E", "J", "L"],
          ["F", "K"],
          ["L", "M"],
          ["I", "K"],
          ["I", "K"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["A", "B", "D", "E", "F", "I", "J", "L", "M", "O", "P"]
      ].sort,
      distinct_sets(
        [
          ["B", "E", "L", "M"],
          ["B", "I", "L", "O", "P"],
          ["A", "J", "O", "P"],
          ["A", "D", "F", "L"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["E", "G", "K"],
        ["A", "C", "I", "J", "M", "N"]
      ].sort,
      distinct_sets(
        [
          ["E", "G", "K"],
          ["A", "C", "I", "J", "N"],
          ["C", "J", "M", "N"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["A", "D", "E", "H", "I", "L", "N", "P"]
      ].sort,
      distinct_sets(
        [
          ["A", "D", "E", "H"],
          ["D", "N", "P"],
          ["D", "I", "L", "P"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["E", "F", "K", "N", "O"],
        ["A", "B", "C", "J", "P"]
      ].sort,
      distinct_sets(
        [
          ["E", "F", "K", "N", "O"],
          ["A", "B", "C", "J", "P"]
        ]
      ).sort
    )

    assert_equal(
      [
        ["A", "C", "E", "H", "J", "K", "M", "N", "O", "Q", "T"],
        ["D", "F", "L"]
      ].sort,
      distinct_sets(
        [
          ["C", "H", "M"],
          ["D", "F", "L"],
          ["A", "E", "J", "O"],
          ["C", "H"],
          ["J", "K", "M"],
          ["A", "N", "Q", "T"]
        ]
      ).sort
    )

    assert_equal(
      [
      ].sort,
      distinct_sets(
        [
        ]
      ).sort
    )
  end
end

Without the forced sorting:

$ ruby -v 225-nocheat.rb
ruby 1.8.2 (2004-12-25) [powerpc-darwin8.0]
Loaded suite 225-nocheat
Started
F
Finished in 0.095481 seconds.

  1) Failure:
tests(TestCase225) [225-nocheat.rb:21]:
<[["D", "E", "G", "H", "L", "R"], ["C", "J", "K", "M"]]> expected but was
<[["C", "J", "K", "M"], ["D", "E", "G", "H", "L", "R"]]>.

1 tests, 1 assertions, 1 failures, 0 errors

So, I changed my method to reverse sort by set size:

$ ruby -v 225-nocheat.rb
ruby 1.8.2 (2004-12-25) [powerpc-darwin8.0]
Loaded suite 225-nocheat
Started
F
Finished in 0.098535 seconds.

  1) Failure:
tests(TestCase225) [225-nocheat.rb:97]:
<[["E", "G", "K"], ["A", "C", "I", "J", "M", "N"]]> expected but was
<[["A", "C", "I", "J", "M", "N"], ["E", "G", "K"]]>.

1 tests, 6 assertions, 1 failures, 0 errors

But, that doesn't exactly match all of the sample input/output.  So,
then I "cheated" and sorted both before asserting.

:-)