summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-30 01:33:25 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-30 01:33:25 +0200
commitbfb81139b65cd99b4a231e42a810214388194ec7 (patch)
treefe4595faf9da496a420455c4f379d98b64a0403c
parentd7411d8e5a0a5f974c2a8a5fe52d4265c4b951b8 (diff)
Solve set
-rw-r--r--go/custom-set/README.md24
-rw-r--r--go/custom-set/cases_test.go368
-rw-r--r--go/custom-set/custom_set.go132
-rw-r--r--go/custom-set/custom_set_test.go268
4 files changed, 792 insertions, 0 deletions
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)
+ }
+}