Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 246
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Given a list of words, determine whether the words can be chained to form a circle. A word X can be placed in front of another word Y in a circle if the last character of X is same as the first character of Y.

For example, the words `['chair', 'height', 'racket', touch', 'tunic']` can form the following circle: `chair --> racket --> touch --> height --> tunic --> chair`.

Pull request:
Day246
Resolves #508.

Patch:
diff --git a/README.md b/README.md
index 5e736ac..137e627 100644
--- a/README.md
+++ b/README.md
@@ -257,3 +257,4 @@ problems from
 * [Day 243](https://github.com/vaskoz/dailycodingproblem-go/issues/502)
 * [Day 244](https://github.com/vaskoz/dailycodingproblem-go/issues/503)
 * [Day 245](https://github.com/vaskoz/dailycodingproblem-go/issues/506)
+* [Day 246](https://github.com/vaskoz/dailycodingproblem-go/issues/508)
diff --git a/day246/problem.go b/day246/problem.go
new file mode 100644
index 0000000..10d6202
--- /dev/null
+++ b/day246/problem.go
@@ -0,0 +1,43 @@
+package day246
+
+// CircleWords returns a circle formation for these words.
+// If a circle isn't possible, then returns nil.
+func CircleWords(words []string) []string {
+	if len(words) < 2 {
+		return words
+	}
+	answer := make([]string, 0, len(words))
+	answer = append(answer, words[0])
+	remaining := make(map[rune]map[string]struct{}, len(words))
+	for i := 1; i < len(words); i++ {
+		word := words[i]
+		firstRune := rune(word[0])
+		if _, ok := remaining[firstRune]; !ok {
+			remaining[firstRune] = make(map[string]struct{})
+		}
+		remaining[firstRune][word] = struct{}{}
+	}
+	return circleWords(answer, remaining)
+}
+
+func circleWords(answer []string, remaining map[rune]map[string]struct{}) []string {
+	if len(remaining) == 0 {
+		return answer
+	}
+	lastWord := answer[len(answer)-1]
+	lastRune := rune(lastWord[len(lastWord)-1])
+	for w := range remaining[lastRune] {
+		delete(remaining[lastRune], w)
+		if len(remaining[lastRune]) == 0 {
+			delete(remaining, lastRune)
+		}
+		if result := circleWords(append(answer, w), remaining); result != nil {
+			return result
+		}
+		if _, ok := remaining[lastRune]; !ok {
+			remaining[lastRune] = make(map[string]struct{})
+		}
+		remaining[lastRune][w] = struct{}{}
+	}
+	return nil
+}


Test patch:
diff --git a/day246/problem_test.go b/day246/problem_test.go
new file mode 100644
index 0000000..b5d0d3a
--- /dev/null
+++ b/day246/problem_test.go
@@ -0,0 +1,39 @@
+package day246
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input, expected []string
+}{
+	{
+		[]string{"chair", "height", "racket", "touch", "tunic"},
+		[]string{"chair", "racket", "touch", "height", "tunic"},
+	},
+	{[]string{"one"}, []string{"one"}},
+	{
+		[]string{"chair", "height", "touch", "tunic"},
+		nil,
+	},
+	{[]string{"a", "aa", "ac", "ad", "ba", "ca", "da"}, nil},
+}
+
+func TestCircleWords(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CircleWords(tc.input); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkCircleWords(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CircleWords(tc.input)
+		}
+	}
+}