summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2016-08-28 01:11:56 +0200
committerDimitri Sokolyuk <demon@dim13.org>2016-08-28 01:11:56 +0200
commitc2cab3dd8e3023a524f6ad3262790bfce2fda2c0 (patch)
tree681300e28dec009bf9c71bbfbb761e8d6c5ead0c
parent28978858033244093191c763dd7b8597faedae35 (diff)
Solve anagram
-rw-r--r--go/anagram/README.md25
-rw-r--r--go/anagram/anagram.go30
-rw-r--r--go/anagram/anagram_test.go172
3 files changed, 227 insertions, 0 deletions
diff --git a/go/anagram/README.md b/go/anagram/README.md
new file mode 100644
index 0000000..5a05f3c
--- /dev/null
+++ b/go/anagram/README.md
@@ -0,0 +1,25 @@
+# Anagram
+
+Write a program that, given a word and a list of possible anagrams, selects the correct sublist.
+
+Given `"listen"` and a list of candidates like `"enlists" "google"
+"inlets" "banana"` the program should return a list containing
+`"inlets"`.
+
+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).
+
+## Source
+
+Inspired by the Extreme Startup game [https://github.com/rchatley/extreme_startup](https://github.com/rchatley/extreme_startup)
+
+## 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/anagram/anagram.go b/go/anagram/anagram.go
new file mode 100644
index 0000000..e7bf2f9
--- /dev/null
+++ b/go/anagram/anagram.go
@@ -0,0 +1,30 @@
+package anagram
+
+import (
+ "sort"
+ "strings"
+)
+
+type byByte []byte
+
+func (b byByte) Len() int { return len(b) }
+func (b byByte) Less(i, j int) bool { return b[i] < b[j] }
+func (b byByte) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
+
+func Detect(s string, cand []string) []string {
+ var ret []string
+ s = strings.ToLower(s)
+ b := byByte(s)
+ sort.Sort(b)
+ for _, v := range cand {
+ v = strings.ToLower(v)
+ if len(v) == len(s) && v != s {
+ c := byByte(v)
+ sort.Sort(c)
+ if string(c) == string(b) {
+ ret = append(ret, v)
+ }
+ }
+ }
+ return ret
+}
diff --git a/go/anagram/anagram_test.go b/go/anagram/anagram_test.go
new file mode 100644
index 0000000..3a8c0fc
--- /dev/null
+++ b/go/anagram/anagram_test.go
@@ -0,0 +1,172 @@
+package anagram
+
+import (
+ "fmt"
+ "sort"
+ "testing"
+)
+
+var testCases = []struct {
+ subject string
+ candidates []string
+ expected []string
+ description string
+}{
+ {
+ subject: "diaper",
+ candidates: []string{
+ "hello",
+ "world",
+ "zombies",
+ "pants",
+ },
+ expected: []string{},
+ description: "no matches",
+ },
+ {
+ subject: "ant",
+ candidates: []string{
+ "tan",
+ "stand",
+ "at",
+ },
+ expected: []string{"tan"},
+ description: "simple anagram",
+ },
+ {
+ subject: "listen",
+ candidates: []string{
+ "enlists",
+ "google",
+ "inlets",
+ "banana",
+ },
+ expected: []string{"inlets"},
+ description: "another simple anagram",
+ },
+ {
+ subject: "master",
+ candidates: []string{
+ "stream",
+ "pigeon",
+ "maters",
+ },
+ expected: []string{"maters", "stream"},
+ description: "multiple anagrams",
+ },
+ {
+ subject: "allergy",
+ candidates: []string{
+ "gallery",
+ "ballerina",
+ "regally",
+ "clergy",
+ "largely",
+ "leading",
+ },
+ expected: []string{"gallery", "largely", "regally"},
+ description: "multiple anagrams (again)",
+ },
+ {
+ subject: "galea",
+ candidates: []string{
+ "eagle",
+ },
+ expected: []string{},
+ description: "does not confuse different duplicates",
+ },
+ {
+ subject: "corn",
+ candidates: []string{
+ "corn",
+ "dark",
+ "Corn",
+ "rank",
+ "CORN",
+ "cron",
+ "park",
+ },
+ expected: []string{"cron"},
+ description: "identical word is not anagram",
+ },
+ {
+ subject: "mass",
+ candidates: []string{
+ "last",
+ },
+ expected: []string{},
+ description: "eliminate anagrams with same checksum",
+ },
+ {
+ subject: "good",
+ candidates: []string{
+ "dog",
+ "goody",
+ },
+ expected: []string{},
+ description: "eliminate anagram subsets",
+ },
+ {
+ subject: "Orchestra",
+ candidates: []string{
+ "cashregiser",
+ "carthorse",
+ "radishes",
+ },
+ expected: []string{"carthorse"},
+ description: "subjects are case insensitive",
+ },
+ {
+ subject: "orchestra",
+ candidates: []string{
+ "cashregiser",
+ "Carthorse",
+ "radishes",
+ },
+ expected: []string{"carthorse"},
+ description: "candidates are case insensitive",
+ },
+}
+
+func equal(a []string, b []string) bool {
+ if len(b) != len(a) {
+ return false
+ }
+
+ sort.Strings(a)
+ sort.Strings(b)
+ return fmt.Sprintf("%v", a) == fmt.Sprintf("%v", b)
+}
+
+func TestDetectAnagrams(t *testing.T) {
+ for _, tt := range testCases {
+ actual := Detect(tt.subject, tt.candidates)
+ if !equal(tt.expected, actual) {
+ msg := `FAIL: %s
+ Subject %s
+ Candidates %v
+ Expected %v
+ Got %v
+ `
+ t.Fatalf(msg, tt.description, tt.subject, tt.candidates, tt.expected, actual)
+ } else {
+ t.Logf("PASS: %s", tt.description)
+ }
+ }
+}
+
+func BenchmarkDetectAnagrams(b *testing.B) {
+
+ b.StopTimer()
+
+ for _, tt := range testCases {
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ Detect(tt.subject, tt.candidates)
+ }
+
+ b.StopTimer()
+ }
+
+}