From c2cab3dd8e3023a524f6ad3262790bfce2fda2c0 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sun, 28 Aug 2016 01:11:56 +0200 Subject: Solve anagram --- go/anagram/README.md | 25 +++++++ go/anagram/anagram.go | 30 ++++++++ go/anagram/anagram_test.go | 172 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 227 insertions(+) create mode 100644 go/anagram/README.md create mode 100644 go/anagram/anagram.go create mode 100644 go/anagram/anagram_test.go 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() + } + +} -- cgit v1.2.3