Exercism v3 launches on Sept 1st 2021. Learn more! ๐Ÿš€๐Ÿš€๐Ÿš€
Avatar of the-red-paintings

the-red-paintings's solution

to Custom Set in the Elixir Track

Published at Jul 13 2018 · 0 comments
Instructions
Test suite
Solution

Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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.

Running tests

Execute the tests with:

$ elixir custom_set_test.exs

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

For more detailed information about the Elixir track, please see the help page.

Submitting Incomplete Solutions

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

custom_set_test.exs

if !System.get_env("EXERCISM_TEST_EXAMPLES") do
  Code.load_file("custom_set.exs", __DIR__)
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

defmodule CustomSetTest do
  use ExUnit.Case

  # @tag :pending
  describe "new" do
    test "returns a CustomSet struct" do
      assert CustomSet.new([]) == %CustomSet{}
    end

    test "removes duplicates in the given enumerable" do
      actual = CustomSet.new([1, 1, 2, 3])
      expected = CustomSet.new([1, 2, 3])
      assert actual == expected
    end
  end

  @tag :pending
  describe "empty?" do
    test "sets with no elements are empty" do
      custom_set = CustomSet.new([])
      assert CustomSet.empty?(custom_set) == true
    end

    test "sets with elements are not empty" do
      custom_set = CustomSet.new([1])
      assert CustomSet.empty?(custom_set) == false
    end
  end

  @tag :pending
  describe "contains?" do
    test "nothing is contained in an empty set" do
      custom_set = CustomSet.new([])
      assert CustomSet.contains?(custom_set, 1) == false
    end

    test "when the element is in the set" do
      custom_set = CustomSet.new([1, 2, 3])
      assert CustomSet.contains?(custom_set, 1) == true
    end

    test "when the element is not in the set" do
      custom_set = CustomSet.new([1, 2, 3])
      assert CustomSet.contains?(custom_set, 4) == false
    end
  end

  @tag :pending
  describe "subset?" do
    test "empty set is a subset of another empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == true
    end

    test "empty set is a subset of non-empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([1])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == true
    end

    test "non-empty set is not a subset of empty set" do
      custom_set_1 = CustomSet.new([1])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == false
    end

    test "set is a subset of set with exact same elements" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([1, 2, 3])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == true
    end

    test "set is a subset of larger set with same elements" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([4, 1, 2, 3])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == true
    end

    test "set is not a subset of set that does not contain its elements" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([4, 1, 3])
      assert CustomSet.subset?(custom_set_1, custom_set_2) == false
    end
  end

  @tag :pending
  describe "disjoint?" do
    test "the empty set is disjoint with itself" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.disjoint?(custom_set_1, custom_set_2) == true
    end

    test "empty set is disjoint with non-empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([1])
      assert CustomSet.disjoint?(custom_set_1, custom_set_2) == true
    end

    test "non-empty set is disjoint with empty set" do
      custom_set_1 = CustomSet.new([1])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.disjoint?(custom_set_1, custom_set_2) == true
    end

    test "sets are not disjoint if they share an element" do
      custom_set_1 = CustomSet.new([1, 2])
      custom_set_2 = CustomSet.new([2, 3])
      assert CustomSet.disjoint?(custom_set_1, custom_set_2) == false
    end

    test "sets are disjoint if they share no elements" do
      custom_set_1 = CustomSet.new([1, 2])
      custom_set_2 = CustomSet.new([3, 4])
      assert CustomSet.disjoint?(custom_set_1, custom_set_2) == true
    end
  end

  @tag :pending
  describe "equal?" do
    test "empty sets are equal" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.equal?(custom_set_1, custom_set_2) == true
    end

    test "empty set is not equal to non-empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([1, 2, 3])
      assert CustomSet.equal?(custom_set_1, custom_set_2) == false
    end

    test "non-empty set is not equal to empty set" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([])
      assert CustomSet.equal?(custom_set_1, custom_set_2) == false
    end

    test "sets with the same elements are equal" do
      custom_set_1 = CustomSet.new([1, 2])
      custom_set_2 = CustomSet.new([2, 1])
      assert CustomSet.equal?(custom_set_1, custom_set_2) == true
    end

    test "sets with different elements are not equal" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([1, 2, 4])
      assert CustomSet.equal?(custom_set_1, custom_set_2) == false
    end
  end

  @tag :pending
  describe "add" do
    test "add to empty set" do
      custom_set = CustomSet.new([])
      actual = CustomSet.add(custom_set, 3)
      expected = CustomSet.new([3])
      assert CustomSet.equal?(actual, expected)
    end

    test "add to non-empty set" do
      custom_set = CustomSet.new([1, 2, 4])
      actual = CustomSet.add(custom_set, 3)
      expected = CustomSet.new([1, 2, 3, 4])
      assert CustomSet.equal?(actual, expected)
    end

    test "adding an existing element does not change the set" do
      expected = CustomSet.new([1, 2, 3])
      actual = CustomSet.add(expected, 3)
      assert CustomSet.equal?(expected, actual)
    end
  end

  @tag :pending
  describe "intersection" do
    test "intersection of two empty sets is an empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.intersection(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "intersection of an empty set and non-empty set is an empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([3, 2, 5])
      actual = CustomSet.intersection(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "intersection of a non-empty set and an empty set is an empty set" do
      custom_set_1 = CustomSet.new([1, 2, 3, 4])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.intersection(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "intersection of two sets with no shared elements is an empty set" do
      custom_set_1 = CustomSet.new([1, 2, 3])
      custom_set_2 = CustomSet.new([4, 5, 6])
      actual = CustomSet.intersection(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "intersection of two sets with shared elements is a set of the shared elements" do
      custom_set_1 = CustomSet.new([1, 2, 3, 4])
      custom_set_2 = CustomSet.new([3, 2, 5])
      actual = CustomSet.intersection(custom_set_1, custom_set_2)
      expected = CustomSet.new([2, 3])
      assert CustomSet.equal?(actual, expected)
    end
  end

  @tag :pending
  describe "difference" do
    test "difference of two empty sets is an empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.difference(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "difference of empty set and non-empty set is an empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([3, 2, 5])
      actual = CustomSet.difference(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "difference of a non-empty set and an empty set is the non-empty set" do
      custom_set_1 = CustomSet.new([1, 2, 3, 4])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.difference(custom_set_1, custom_set_2)
      expected = CustomSet.new([1, 2, 3, 4])
      assert CustomSet.equal?(actual, expected)
    end

    test "difference of two non-empty sets is a set of elements that are only in the first set" do
      custom_set_1 = CustomSet.new([3, 2, 1])
      custom_set_2 = CustomSet.new([2, 4])
      actual = CustomSet.difference(custom_set_1, custom_set_2)
      expected = CustomSet.new([1, 3])
      assert CustomSet.equal?(actual, expected)
    end
  end

  @tag :pending
  describe "union" do
    test "union of empty sets is an empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.union(custom_set_1, custom_set_2)
      expected = CustomSet.new([])
      assert CustomSet.equal?(actual, expected)
    end

    test "union of an empty set and non-empty set is the non-empty set" do
      custom_set_1 = CustomSet.new([])
      custom_set_2 = CustomSet.new([2])
      actual = CustomSet.union(custom_set_1, custom_set_2)
      expected = CustomSet.new([2])
      assert CustomSet.equal?(actual, expected)
    end

    test "union of a non-empty set and empty set is the non-empty set" do
      custom_set_1 = CustomSet.new([1, 3])
      custom_set_2 = CustomSet.new([])
      actual = CustomSet.union(custom_set_1, custom_set_2)
      expected = CustomSet.new([1, 3])
      assert CustomSet.equal?(actual, expected)
    end

    test "union of non-empty sets contains all unique elements" do
      custom_set_1 = CustomSet.new([1, 3])
      custom_set_2 = CustomSet.new([2, 3])
      actual = CustomSet.union(custom_set_1, custom_set_2)
      expected = CustomSet.new([1, 2, 3])
      assert CustomSet.equal?(actual, expected)
    end
  end
end
defmodule CustomSet do

  defstruct map: Map.new

  @opaque t :: %__MODULE__{map: map}

  #@spec new(Enum.t) :: t
  def new(enumerable) do
    %CustomSet{map: Enum.reduce(enumerable, %{}, fn(item,acc) -> Map.put(acc, item, :empty) end)}
  end

  #@spec empty?(t) :: boolean
  # custom_set |>
  #       Map.values |>
  #       length
  def empty?(%CustomSet{map: custom_set}) do
    Enum.empty?(custom_set)
  end

  #@spec contains?(t, any) :: boolean
  def contains?(%CustomSet{map: custom_set}, element) do
    Map.has_key?(custom_set, element)
  end

  #@spec subset?(t, t) :: boolean
  def subset?(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    Enum.all?(custom_set_1, fn(key) -> Map.has_key?(custom_set_2, elem(key, 0)) end)
  end

  #@spec disjoint?(t, t) :: boolean
  def disjoint?(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    res = [Enum.any?(custom_set_1, fn(key) -> Map.has_key?(custom_set_2, elem(key, 0)) end) | []]
    res = [Enum.any?(custom_set_2, fn(key) -> Map.has_key?(custom_set_1, elem(key, 0)) end) | res]
    Enum.any?(res, fn x -> x == false end)
  end

  #@spec equal?(t, t) :: boolean
  def equal?(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    custom_set_1 == custom_set_2
  end

  #@spec add(t, any) :: t
  def add(%CustomSet{map: custom_set}, element) do
    %CustomSet{map: Map.put(custom_set, element, :empty)}
  end

  #@spec intersection(t, t) :: t
  def intersection(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    %CustomSet{map: Enum.filter(custom_set_1, fn(item) -> Map.has_key?(custom_set_2, elem(item, 0)) end) |>
    Enum.into(%{})}
  end

  #@spec difference(t, t) :: t
  def difference(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    %CustomSet{map: Enum.reject(custom_set_1, fn(item) -> Map.has_key?(custom_set_2, elem(item, 0)) end) |>
    Enum.into(%{})}
  end

  #@spec union(t, t) :: t
  def union(%CustomSet{map: custom_set_1}, %CustomSet{map: custom_set_2}) do
    %CustomSet{map: Enum.into(custom_set_1, custom_set_2)}
  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?