From bfb81139b65cd99b4a231e42a810214388194ec7 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Tue, 30 Aug 2016 01:33:25 +0200 Subject: Solve set --- go/custom-set/README.md | 24 +++ go/custom-set/cases_test.go | 368 +++++++++++++++++++++++++++++++++++++++ go/custom-set/custom_set.go | 132 ++++++++++++++ go/custom-set/custom_set_test.go | 268 ++++++++++++++++++++++++++++ 4 files changed, 792 insertions(+) create mode 100644 go/custom-set/README.md create mode 100644 go/custom-set/cases_test.go create mode 100644 go/custom-set/custom_set.go create mode 100644 go/custom-set/custom_set_test.go diff --git a/go/custom-set/README.md b/go/custom-set/README.md new file mode 100644 index 0000000..85f2cb3 --- /dev/null +++ b/go/custom-set/README.md @@ -0,0 +1,24 @@ +# Custom Set + +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. + +To run the tests simply run the command `go test` in the exercise directory. + +If the test suite contains benchmarks, you can run these with the `-bench` +flag: + + go test -bench . + +For more detailed info about the Go track see the [help +page](http://exercism.io/languages/go). + + + +## Submitting Incomplete Problems +It's possible to submit an incomplete solution so you can see how others have completed the exercise. + diff --git a/go/custom-set/cases_test.go b/go/custom-set/cases_test.go new file mode 100644 index 0000000..90523b8 --- /dev/null +++ b/go/custom-set/cases_test.go @@ -0,0 +1,368 @@ +package stringset + +// Source: exercism/x-common +// Commit: 269f498 Merge pull request #48 from soniakeys/custom-set-json + +// Test two sets for equality. +var eqCases = []binBoolCase{ + { // order doesn't matter + []string{"a", "c"}, + []string{"c", "a"}, + true, + }, + { // dupicates don't matter + []string{"a", "a"}, + []string{"a"}, + true, + }, + { // empty sets are equal + []string{}, + []string{}, + true, + }, + { // set with single element is equal to itself + []string{"a"}, + []string{"a"}, + true, + }, + { // different sets are not equal + []string{"a", "b", "c"}, + []string{"c", "d", "e"}, + false, + }, + { // empty set is not equal to non-empty set + []string{}, + []string{"a", "b", "c"}, + false, + }, + { // non-empty set is not equal to empty set + []string{"a", "b", "c"}, + []string{}, + false, + }, + { // having most in common is not good enough + []string{"a", "b", "c", "d"}, + []string{"b", "c", "d", "e"}, + false, + }, +} + +// Add an element to a set. +var addCases = []eleOpCase{ + { // add to empty set + []string{}, + "c", + []string{"c"}, + }, + { // add to non-empty set + []string{"a", "b", "d"}, + "c", + []string{"a", "b", "c", "d"}, + }, + { // add existing element + []string{"a", "b", "c"}, + "c", + []string{"a", "b", "c"}, + }, +} + +// Delete an element from a set. +var delCases = []eleOpCase{ + { // delete an element + []string{"c", "b", "a"}, + "b", + []string{"a", "c"}, + }, + { // delete an element not in set + []string{"c", "b", "a"}, + "d", + []string{"a", "b", "c"}, + }, +} + +// Test if is a set is empty. +var emptyCases = []unaryBoolCase{ + { // empty + []string{}, + true, + }, + { // single element + []string{"a"}, + false, + }, + { // a few elements + []string{"a", "b", "c", "b"}, + false, + }, +} + +// Return the cardinality of a set. +var lenCases = []unaryIntCase{ + { // empty set + []string{}, + 0, + }, + { // non-empty set + []string{"a", "b", "c"}, + 3, + }, + { // duplicate element + []string{"a", "b", "c", "b"}, + 3, + }, +} + +// Test if a value is an element of a set. +var hasCases = []eleBoolCase{ + { // nothing is an element of the empty set + []string{}, + "a", + false, + }, + { // 1 is in the set + []string{"a", "b", "c", "b"}, + "a", + true, + }, + { // 2 is in the set + []string{"a", "b", "c", "b"}, + "b", + true, + }, + { // 3 is in the set + []string{"a", "b", "c", "b"}, + "c", + true, + }, + { // 4 not in the set + []string{"a", "b", "c", "b"}, + "d", + false, + }, +} + +// Test if set1 is a subset of set2. +var subsetCases = []binBoolCase{ + { // empty set is subset of itself + []string{}, + []string{}, + true, + }, + { // empty set is subset of non-empty set + []string{}, + []string{"a"}, + true, + }, + { // non-empty set is not subset of empty set + []string{"a"}, + []string{}, + false, + }, + { // non-empty set is subset of itself + []string{"a", "b", "c"}, + []string{"a", "b", "c"}, + true, + }, + { // proper subset + []string{"a", "b", "c"}, + []string{"d", "a", "b", "c"}, + true, + }, + { // same number of elements + []string{"a", "b", "c"}, + []string{"d", "a", "c"}, + false, + }, + { // superset + []string{"a", "b", "c", "d", "e"}, + []string{"b", "c", "d"}, + false, + }, + { // fewer elements but not a subset + []string{"a", "b", "c", "k"}, + []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}, + false, + }, +} + +// Test if two sets are disjoint. +var disjointCases = []binBoolCase{ + { // the empty set is disjoint with itself + []string{}, + []string{}, + true, + }, + { // empty set disjoint with non-empty set + []string{}, + []string{"a"}, + true, + }, + { // non-empty set disjoint with empty set + []string{"a"}, + []string{}, + true, + }, + { // one element in common + []string{"a", "b"}, + []string{"b", "c"}, + false, + }, + { // no elements in common + []string{"a", "b"}, + []string{"c", "d"}, + true, + }, +} + +// Produce the union of two sets. +var unionCases = []binOpCase{ + { // union of empty sets + []string{}, + []string{}, + []string{}, + }, + { // union of empty set with set of one element + []string{}, + []string{"b"}, + []string{"b"}, + }, + { // union of empty set with non-empty set + []string{}, + []string{"c", "b", "e"}, + []string{"b", "c", "e"}, + }, + { // union of non-empty set with empty set + []string{"a", "c"}, + []string{}, + []string{"a", "c"}, + }, + { // union of a set with itself + []string{"a", "c"}, + []string{"c", "a"}, + []string{"a", "c"}, + }, + { // union with one element + []string{"a", "c"}, + []string{"b"}, + []string{"a", "b", "c"}, + }, + { // one element in common, one different + []string{"a", "c"}, + []string{"b", "c"}, + []string{"c", "b", "a"}, + }, + { // two elements in common + []string{"a", "b", "c", "d"}, + []string{"c", "b", "e"}, + []string{"a", "b", "c", "d", "e"}, + }, +} + +// Intersect two sets. +var intersectionCases = []binOpCase{ + { // intersect empty sets + []string{}, + []string{}, + []string{}, + }, + { // intersect empty set with non-empty set + []string{}, + []string{"c", "b", "e"}, + []string{}, + }, + { // intersect non-empty set with empty set + []string{"a", "b", "c", "d"}, + []string{}, + []string{}, + }, + { // intersect one element with itself + []string{"c"}, + []string{"c"}, + []string{"c"}, + }, + { // one element in common, extra elements in both sets + []string{"a", "b", "c"}, + []string{"c", "e", "d"}, + []string{"c"}, + }, + { // two elements in common, extras in both sets + []string{"a", "b", "c", "d"}, + []string{"c", "b", "e"}, + []string{"b", "c"}, + }, + { // intersect with subset + []string{"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}, + []string{"e", "f", "g", "h", "i", "j"}, + []string{"e", "f", "g", "h", "i", "j"}, + }, + { // nothing in common + []string{"a", "b", "c"}, + []string{"d", "e", "f"}, + []string{}, + }, +} + +// Produce the set difference (set1 - set2) +// or more specifically, (set1 ∖ set2) +var differenceCases = []binOpCase{ + { // difference of two empty sets + []string{}, + []string{}, + []string{}, + }, + { // difference of empty set and non-empty set + []string{}, + []string{"c", "b", "e"}, + []string{}, + }, + { // difference of non-empty set and empty set + []string{"a", "b", "c", "d"}, + []string{}, + []string{"a", "b", "c", "d"}, + }, + { // no elements in common + []string{"a", "b", "c"}, + []string{"d"}, + []string{"a", "b", "c"}, + }, + { // one element in common, one extra + []string{"c", "b", "a"}, + []string{"b", "d"}, + []string{"a", "c"}, + }, + { // two elements in common, one extra + []string{"a", "b", "c", "d"}, + []string{"c", "b", "e"}, + []string{"a", "d"}, + }, +} + +// Produce the symmetric difference of two sets. The symmetric +// difference consists of elements in one or the other but not both. +var symmetricDifferenceCases = []binOpCase{ + { // two empty sets + []string{}, + []string{}, + []string{}, + }, + { // empty set and non-empty set + []string{}, + []string{"c", "b", "e"}, + []string{"c", "b", "e"}, + }, + { // non-empty set and empty set + []string{"a", "b", "c", "d"}, + []string{}, + []string{"a", "b", "c", "d"}, + }, + { // no elements in common + []string{"a", "b", "c"}, + []string{"d"}, + []string{"a", "b", "c", "d"}, + }, + { // one element in common + []string{"c", "b", "a"}, + []string{"b", "d"}, + []string{"a", "c", "d"}, + }, +} diff --git a/go/custom-set/custom_set.go b/go/custom-set/custom_set.go new file mode 100644 index 0000000..1994dc5 --- /dev/null +++ b/go/custom-set/custom_set.go @@ -0,0 +1,132 @@ +package stringset + +import "strings" + +const testVersion = 3 + +type Set map[string]struct{} + +func New() Set { + return make(Set) +} + +func NewFromSlice(s []string) Set { + set := make(Set) + for _, v := range s { + set[v] = struct{}{} + } + return set +} + +func (set Set) Add(s string) { + set[s] = struct{}{} +} + +func (set Set) Delete(s string) { + delete(set, s) +} + +func (set Set) Has(s string) bool { + _, ok := set[s] + return ok +} + +func (set Set) IsEmpty() bool { + return len(set) == 0 +} + +func (set Set) Len() int { + return len(set) +} + +func (set Set) Slice() []string { + tmp := make([]string, 0, len(set)) + for v := range set { + tmp = append(tmp, v) + } + return tmp +} + +func (set Set) String() string { + tmp := make([]string, 0, len(set)) + for v := range set { + tmp = append(tmp, `"`+v+`"`) + } + return `{` + strings.Join(tmp, `, `) + `}` +} + +func Equal(s1, s2 Set) bool { + if len(s1) != len(s2) { + return false + } + for v := range s1 { + if _, ok := s2[v]; !ok { + return false + } + } + return true +} + +func Subset(s1, s2 Set) bool { + for v := range s1 { + if _, ok := s2[v]; !ok { + return false + } + } + return true +} + +func Disjoint(s1, s2 Set) bool { + for v := range s1 { + if _, ok := s2[v]; ok { + return false + } + } + return true +} + +func Intersection(s1, s2 Set) Set { + set := make(Set) + for v := range s1 { + if _, ok := s2[v]; ok { + set[v] = struct{}{} + } + } + return set +} + +func Union(s1, s2 Set) Set { + set := make(Set) + for v := range s1 { + set[v] = struct{}{} + } + for v := range s2 { + set[v] = struct{}{} + } + return set +} + +func Difference(s1, s2 Set) Set { + set := make(Set) + for v := range s1 { + if _, ok := s2[v]; !ok { + set[v] = struct{}{} + } + } + return set +} + +func SymmetricDifference(s1, s2 Set) Set { + set := make(Set) + for v := range s1 { + if _, ok := s2[v]; !ok { + set[v] = struct{}{} + } + } + for v := range s2 { + if _, ok := s1[v]; !ok { + set[v] = struct{}{} + } + } + return set +} diff --git a/go/custom-set/custom_set_test.go b/go/custom-set/custom_set_test.go new file mode 100644 index 0000000..7b8d0ba --- /dev/null +++ b/go/custom-set/custom_set_test.go @@ -0,0 +1,268 @@ +package stringset + +// Implement Set as a collection of unique string values. +// +// API: +// +// New() Set +// NewFromSlice([]string) Set +// (s Set) Add(string) // modify s +// (s Set) Delete(string) // modify s +// (s Set) Has(string) bool +// (s Set) IsEmpty() bool +// (s Set) Len() int +// (s Set) Slice() []string +// (s Set) String() string +// Equal(s1, s2 Set) bool +// Subset(s1, s2 Set) bool // return s1 ⊆ s2 +// Disjoint(s1, s2 Set) bool +// Intersection(s1, s2 Set) Set +// Union(s1, s2 Set) Set +// Difference(s1, s2 Set) Set // return s1 ∖ s2 +// SymmetricDifference(s1, s2 Set) Set +// +// For Set.String, use '{' and '}', output elements as double-quoted strings +// safely escaped with Go syntax, and use a comma and a single space between +// elements. For example {"a", "b"}. +// Format the empty set as {}. + +import ( + "math/rand" + "reflect" + "strconv" + "testing" +) + +const targetTestVersion = 3 + +func TestTestVersion(t *testing.T) { + if testVersion != targetTestVersion { + t.Fatalf("Found testVersion = %v, want %v", testVersion, targetTestVersion) + } +} + +// A first set of tests uses Set.String() to judge correctness. + +func TestNew(t *testing.T) { + // New must return an empty set. + want := "{}" + if got := New().String(); got != want { + t.Fatalf(`New().String() = %s, want %s.`, got, want) + } +} + +func TestNewFromSlice(t *testing.T) { + // nil slice should give empty set + want := "{}" + if got := NewFromSlice(nil).String(); got != want { + t.Fatalf(`NewFromSlice(nil) = %s, want %s.`, got, want) + } + + // slice with one element: + want = `{"a"}` + if got := NewFromSlice([]string{"a"}).String(); got != want { + t.Fatalf(`NewFromSlice([]string{"a"}) = %s, want %s.`, got, want) + } + + // slice with repeated element: + if got := NewFromSlice([]string{"a", "a"}).String(); got != want { + t.Fatalf(`NewFromSlice([]string{"a", "a"}) = %s, want %s.`, got, want) + } + + // slice with two elements: + got := NewFromSlice([]string{"a", "b"}).String() + want1 := `{"a", "b"}` + want2 := `{"b", "a"}` + if got != want1 && got != want2 { // order undefined + t.Fatalf(`NewFromSlice([]string{"a", "b"}) = %s, want %s or (%s).`, + got, want1, want2) + } +} + +func TestSlice(t *testing.T) { + // empty set should produce empty slice + s := New() + if l := s.Slice(); len(l) != 0 { + t.Fatalf(`s.Slice() = %q, want []`, l) + } + + // one element: + want := []string{"a"} + s = NewFromSlice(want) + got := s.Slice() + if !reflect.DeepEqual(got, want) { + t.Fatalf(`%v Slice = %q, want %q`, s, got, want) + } + + // two elements: + w1 := []string{"a", "b"} + w2 := []string{"b", "a"} + s = NewFromSlice(w1) + got = s.Slice() + if !reflect.DeepEqual(got, w1) && !reflect.DeepEqual(got, w2) { + t.Fatalf(`%v Slice = %q, want %q`, s, got, w1) + } +} + +// Trusting NewFromSlice now, remaining tests are table driven, taking data +// from cases_test.go and building sets with NewFromSlice. + +// test case types used in cases_test.go +type ( + // binary function, bool result (Equal, Subset, Disjoint) + binBoolCase struct { + set1 []string + set2 []string + want bool + } + // unary function, bool result (IsEmpty) + unaryBoolCase struct { + set []string + want bool + } + // unary function, int result (Len) + unaryIntCase struct { + set []string + want int + } + // set-element function, bool result (Has) + eleBoolCase struct { + set []string + ele string + want bool + } + // set-element operator (Add, Delete) + eleOpCase struct { + set []string + ele string + want []string + } + // set-set operator (Union, Intersection, Difference, Symmetric-Difference) + binOpCase struct { + set1 []string + set2 []string + want []string + } +) + +// helper for testing Equal, Subset, Disjoint +func testBinBool(name string, f func(Set, Set) bool, cases []binBoolCase, t *testing.T) { + for _, tc := range cases { + s1 := NewFromSlice(tc.set1) + s2 := NewFromSlice(tc.set2) + got := f(s1, s2) + if got != tc.want { + t.Fatalf("%s(%v, %v) = %t, want %t", name, s1, s2, got, tc.want) + } + } +} + +func TestEqual(t *testing.T) { + testBinBool("Equal", Equal, eqCases, t) +} + +// With Equal tested, remaining tests use it to judge correctness. + +// helper for testing Add, Delete +func testEleOp(name string, op func(Set, string), cases []eleOpCase, t *testing.T) { + for _, tc := range cases { + s := NewFromSlice(tc.set) + op(s, tc.ele) + want := NewFromSlice(tc.want) + if !Equal(s, want) { + t.Fatalf("%v %s %q = %v, want %v", + NewFromSlice(tc.set), name, tc.ele, s, want) + } + } +} + +func TestAdd(t *testing.T) { + testEleOp("Add", Set.Add, addCases, t) +} + +func TestDelete(t *testing.T) { + testEleOp("Delete", Set.Delete, delCases, t) +} + +func TestHas(t *testing.T) { + for _, tc := range hasCases { + s := NewFromSlice(tc.set) + got := s.Has(tc.ele) + if got != tc.want { + t.Fatalf("%v Has %q = %t, want %t", s, tc.ele, got, tc.want) + } + } +} + +func TestIsEmpty(t *testing.T) { + for _, tc := range emptyCases { + s := NewFromSlice(tc.set) + got := s.IsEmpty() + if got != tc.want { + t.Fatalf("%v IsEmpty = %t, want %t", s, got, tc.want) + } + } +} + +func TestLen(t *testing.T) { + for _, tc := range lenCases { + s := NewFromSlice(tc.set) + got := s.Len() + if got != tc.want { + t.Fatalf("%v Len = %d, want %d", s, got, tc.want) + } + } +} + +func TestSubset(t *testing.T) { + testBinBool("Subset", Subset, subsetCases, t) +} + +func TestDisjoint(t *testing.T) { + testBinBool("Disjoint", Disjoint, disjointCases, t) +} + +// helper for testing Union, Intersection, Difference, SymmetricDifference +func testBinOp(name string, f func(Set, Set) Set, cases []binOpCase, t *testing.T) { + for _, tc := range cases { + s1 := NewFromSlice(tc.set1) + s2 := NewFromSlice(tc.set2) + want := NewFromSlice(tc.want) + got := f(s1, s2) + if !Equal(got, want) { + t.Fatalf("%s(%v, %v) = %v, want %v", name, s1, s2, got, want) + } + } +} + +func TestUnion(t *testing.T) { + testBinOp("Union", Union, unionCases, t) +} + +func TestIntersection(t *testing.T) { + testBinOp("Intersection", Intersection, intersectionCases, t) +} + +func TestDifference(t *testing.T) { + testBinOp("Difference", Difference, differenceCases, t) +} + +func TestSymmetricDifference(t *testing.T) { + testBinOp("SymmetricDifference", SymmetricDifference, symmetricDifferenceCases, t) +} + +func BenchmarkNewFromSlice1e1(b *testing.B) { bench(1e1, b) } +func BenchmarkNewFromSlice1e2(b *testing.B) { bench(1e2, b) } +func BenchmarkNewFromSlice1e3(b *testing.B) { bench(1e3, b) } +func BenchmarkNewFromSlice1e4(b *testing.B) { bench(1e4, b) } + +func bench(nAdd int, b *testing.B) { + s := make([]string, nAdd) + for i := range s { + s[i] = strconv.Itoa(rand.Intn(len(s))) + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + NewFromSlice(s) + } +} -- cgit v1.2.3