Avatar of ignar

ignar's solution

to Custom Set in the Ruby Track

Published at Feb 28 2019 · 0 comments
Instructions
Test suite
Solution

Create a custom set type.

Sometimes it is necessary to define a custom data structure of some type, like a set. In this exercise you will define your own set. How it works internally doesn't matter, as long as it behaves like a set of unique elements.


For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby custom_set_test.rb

To include color from the command line:

ruby -r minitest/pride custom_set_test.rb

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

custom_set_test.rb

require 'minitest/autorun'
require_relative 'custom_set'

# Common test data version: 1.3.0 1ef368e
class CustomSetTest < Minitest::Test
  def test_sets_with_no_elements_are_empty
    # skip
    set = CustomSet.new []
    assert_empty set
  end

  def test_sets_with_elements_are_not_empty
    skip
    set = CustomSet.new [1]
    refute_empty set
  end

  def test_nothing_is_contained_in_an_empty_set
    skip
    set = CustomSet.new []
    element = 1
    refute set.member? element
  end

  def test_when_the_element_is_in_the_set
    skip
    set = CustomSet.new [1, 2, 3]
    element = 1
    assert set.member? element
  end

  def test_when_the_element_is_not_in_the_set
    skip
    set = CustomSet.new [1, 2, 3]
    element = 4
    refute set.member? element
  end

  def test_empty_set_is_a_subset_of_another_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    assert set1.subset? set2
  end

  def test_empty_set_is_a_subset_of_non_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [1]
    assert set1.subset? set2
  end

  def test_non_empty_set_is_not_a_subset_of_empty_set
    skip
    set1 = CustomSet.new [1]
    set2 = CustomSet.new []
    refute set1.subset? set2
  end

  def test_set_is_a_subset_of_set_with_exact_same_elements
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [1, 2, 3]
    assert set1.subset? set2
  end

  def test_set_is_a_subset_of_larger_set_with_same_elements
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [4, 1, 2, 3]
    assert set1.subset? set2
  end

  def test_set_is_not_a_subset_of_set_that_does_not_contain_its_elements
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [4, 1, 3]
    refute set1.subset? set2
  end

  def test_the_empty_set_is_disjoint_with_itself
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    assert set1.disjoint? set2
  end

  def test_empty_set_is_disjoint_with_non_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [1]
    assert set1.disjoint? set2
  end

  def test_non_empty_set_is_disjoint_with_empty_set
    skip
    set1 = CustomSet.new [1]
    set2 = CustomSet.new []
    assert set1.disjoint? set2
  end

  def test_sets_are_not_disjoint_if_they_share_an_element
    skip
    set1 = CustomSet.new [1, 2]
    set2 = CustomSet.new [2, 3]
    refute set1.disjoint? set2
  end

  def test_sets_are_disjoint_if_they_share_no_elements
    skip
    set1 = CustomSet.new [1, 2]
    set2 = CustomSet.new [3, 4]
    assert set1.disjoint? set2
  end

  def test_empty_sets_are_equal
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    assert_equal set1, set2
  end

  def test_empty_set_is_not_equal_to_non_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [1, 2, 3]
    refute_equal set1, set2
  end

  def test_non_empty_set_is_not_equal_to_empty_set
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new []
    refute_equal set1, set2
  end

  def test_sets_with_the_same_elements_are_equal
    skip
    set1 = CustomSet.new [1, 2]
    set2 = CustomSet.new [2, 1]
    assert_equal set1, set2
  end

  def test_sets_with_different_elements_are_not_equal
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [1, 2, 4]
    refute_equal set1, set2
  end

  def test_set_is_not_equal_to_larger_set_with_same_elements
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [1, 2, 3, 4]
    refute_equal set1, set2
  end

  def test_add_to_empty_set
    skip
    set = CustomSet.new []
    expected = CustomSet.new [3]
    assert_equal expected, set.add(3)
  end

  def test_add_to_non_empty_set
    skip
    set = CustomSet.new [1, 2, 4]
    expected = CustomSet.new [1, 2, 3, 4]
    assert_equal expected, set.add(3)
  end

  def test_adding_an_existing_element_does_not_change_the_set
    skip
    set = CustomSet.new [1, 2, 3]
    expected = CustomSet.new [1, 2, 3]
    assert_equal expected, set.add(3)
  end

  def test_intersection_of_two_empty_sets_is_an_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    expected = CustomSet.new []
    assert_equal expected, set2.intersection(set1)
  end

  def test_intersection_of_an_empty_set_and_non_empty_set_is_an_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [3, 2, 5]
    expected = CustomSet.new []
    assert_equal expected, set2.intersection(set1)
  end

  def test_intersection_of_a_non_empty_set_and_an_empty_set_is_an_empty_set
    skip
    set1 = CustomSet.new [1, 2, 3, 4]
    set2 = CustomSet.new []
    expected = CustomSet.new []
    assert_equal expected, set2.intersection(set1)
  end

  def test_intersection_of_two_sets_with_no_shared_elements_is_an_empty_set
    skip
    set1 = CustomSet.new [1, 2, 3]
    set2 = CustomSet.new [4, 5, 6]
    expected = CustomSet.new []
    assert_equal expected, set2.intersection(set1)
  end

  def test_intersection_of_two_sets_with_shared_elements_is_a_set_of_the_shared_elements
    skip
    set1 = CustomSet.new [1, 2, 3, 4]
    set2 = CustomSet.new [3, 2, 5]
    expected = CustomSet.new [2, 3]
    assert_equal expected, set2.intersection(set1)
  end

  def test_difference_of_two_empty_sets_is_an_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    expected = CustomSet.new []
    assert_equal expected, set1.difference(set2)
  end

  def test_difference_of_empty_set_and_non_empty_set_is_an_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [3, 2, 5]
    expected = CustomSet.new []
    assert_equal expected, set1.difference(set2)
  end

  def test_difference_of_a_non_empty_set_and_an_empty_set_is_the_non_empty_set
    skip
    set1 = CustomSet.new [1, 2, 3, 4]
    set2 = CustomSet.new []
    expected = CustomSet.new [1, 2, 3, 4]
    assert_equal expected, set1.difference(set2)
  end

  def test_difference_of_two_non_empty_sets_is_a_set_of_elements_that_are_only_in_the_first_set
    skip
    set1 = CustomSet.new [3, 2, 1]
    set2 = CustomSet.new [2, 4]
    expected = CustomSet.new [1, 3]
    assert_equal expected, set1.difference(set2)
  end

  def test_union_of_empty_sets_is_an_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new []
    expected = CustomSet.new []
    assert_equal expected, set1.union(set2)
  end

  def test_union_of_an_empty_set_and_non_empty_set_is_the_non_empty_set
    skip
    set1 = CustomSet.new []
    set2 = CustomSet.new [2]
    expected = CustomSet.new [2]
    assert_equal expected, set1.union(set2)
  end

  def test_union_of_a_non_empty_set_and_empty_set_is_the_non_empty_set
    skip
    set1 = CustomSet.new [1, 3]
    set2 = CustomSet.new []
    expected = CustomSet.new [1, 3]
    assert_equal expected, set1.union(set2)
  end

  def test_union_of_non_empty_sets_contains_all_unique_elements
    skip
    set1 = CustomSet.new [1, 3]
    set2 = CustomSet.new [2, 3]
    expected = CustomSet.new [3, 2, 1]
    assert_equal expected, set1.union(set2)
  end
end
# There are two ways to implement a SET, either using a hash table,
# or with a tree structure (like a red-black tree).
# In given examples a keys a always less then 10, so hash function
# is not the optimal implementation, and I choose a tree way.

require 'forwardable'

class CustomSet
  extend Forwardable

  attr_reader :data

  def_delegators :data, :each, :map, :empty?, :reduce, :count

  def initialize(collection)
    @data = Tree.new collection.shift
    collection.each { |element| @data.add(element) }
  end

  def member?(value)
    return false if data.empty?
    !!data.search(value)
  end

  def add(value)
    data.add(value)
    self
  end

  def subset?(set)
    return true if empty? && set.empty?
    return true if empty? && !set.empty?

    result = data.reduce([]) do |memo, value|
      memo << set.member?(value)
      memo
    end

    !result.empty? && result.all?
  end

  def disjoint?(set)
    return true if empty? || set.empty?

    result = data.reduce([]) do |memo, value|
      memo << set.member?(value)
      memo
    end

    result.empty? || result.none?
  end

  def intersection(set)
    return self.class.new([]) if set.empty? || data.empty?

    array1 = data.reduce([]) { |memo, value| memo << value }
    array2 = set.reduce([]) { |memo, value| memo << value }

    common_elements = array1 & array2
    self.class.new(common_elements)
  end

  def difference(set)
    return self.class.new([]) if data.empty?

    array1 = data.reduce([]) { |memo, value| memo << value }
    array2 = set.reduce([]) { |memo, value| memo << value }

    common_elements = array1 - array2
    self.class.new(common_elements)
  end

  def union(set)
    array1 = data.reduce([]) { |memo, value| memo << value }
    array2 = set.reduce([]) { |memo, value| memo << value }

    common_elements = array1 + array2
    common_elements.compact!
    self.class.new(common_elements)
  end

  def ==(set)
    return false if count != set.count

    array1 = data.reduce([]) { |memo, value| memo << value }
    array2 = set.reduce([]) { |memo, value| memo << value }

    return false if array1.size != array2.size

    array1 == array2
  end
end

class Tree
  include Enumerable

  attr_reader :data, :count
  attr_accessor :left, :right

  def initialize(data)
    @count = 0
    add(data) unless data.nil?
  end

  def empty?
    [data, left, right].all?(&:nil?)
  end

  def search(value)
    return if value.nil? || data.nil?
    if value == data
      value
    elsif value < data
      left.search(value) if left
    elsif value > data
      right.search(value) if right
    end
  end

  def add(value)
    return if search(value)

    @count += 1

    if data.nil?
      @data = value
    elsif value <= data
      left.add(value) if left
      self.left = Tree.new(value) unless left
    else
      right.add(value) if right
      self.right = Tree.new(value) unless right
    end
    self
  end

  def each(&block)
    return to_enum(:each) unless block_given?

    left.each(&block) if left
    block.call(data)
    right.each(&block) if right
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?