Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 264
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

Given a set of characters `C` and an integer `k`, a De Bruijn sequence is a cyclic sequence in which every possible k-length string of characters in C occurs exactly once.

For example, suppose C = {0, 1} and k = 3. Then our sequence should contain the substrings `{'000', '001', '010', '011', '100', '101', '110', '111'}`, and one possible solution would be `00010111`.

Create an algorithm that finds a De Bruijn sequence.

Pull request description:
Day264
Resolves #540.

Patch:
diff --git a/README.md b/README.md
index 8d434d5..5014d04 100644
--- a/README.md
+++ b/README.md
@@ -275,6 +275,7 @@ problems from
 * [Day 261](https://github.com/vaskoz/dailycodingproblem-go/issues/534)
 * [Day 262](https://github.com/vaskoz/dailycodingproblem-go/issues/538)
 * [Day 263](https://github.com/vaskoz/dailycodingproblem-go/issues/539)
+* [Day 264](https://github.com/vaskoz/dailycodingproblem-go/issues/540)
 * [Day 266](https://github.com/vaskoz/dailycodingproblem-go/issues/542)
 * [Day 267](https://github.com/vaskoz/dailycodingproblem-go/issues/543)
 * [Day 268](https://github.com/vaskoz/dailycodingproblem-go/issues/544)
diff --git a/day264/problem.go b/day264/problem.go
new file mode 100644
index 0000000..babd31e
--- /dev/null
+++ b/day264/problem.go
@@ -0,0 +1,31 @@
+package day264
+
+// DeBruijnSequence returns a cyclic sequence in
+// which every possible k-length string of characters
+// in C occurs exactly once.
+func DeBruijnSequence(c string, k int) string {
+	alphabet := []rune(c)
+	a := make([]int, len(alphabet)*k)
+	var seq []int
+	var db func(int, int)
+	db = func(t, p int) {
+		if t > k {
+			if k%p == 0 {
+				seq = append(seq, a[1:p+1]...)
+			}
+		} else {
+			a[t] = a[t-p]
+			db(t+1, p)
+			for j := a[t-p] + 1; j < len(c); j++ {
+				a[t] = j
+				db(t+1, t)
+			}
+		}
+	}
+	db(1, 1)
+	result := make([]rune, len(seq))
+	for i, v := range seq {
+		result[i] = alphabet[v]
+	}
+	return string(result)
+}


Test patch:
diff --git a/day264/problem_test.go b/day264/problem_test.go
new file mode 100644
index 0000000..5105f24
--- /dev/null
+++ b/day264/problem_test.go
@@ -0,0 +1,33 @@
+package day264
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	c        string
+	k        int
+	expected string
+}{
+	{"01", 3, "00010111"},
+	{"abcd", 2, "aabacadbbcbdccdd"},
+}
+
+func TestDeBruijnSequence(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := DeBruijnSequence(tc.c, tc.k); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkDeBruijnSequence(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			DeBruijnSequence(tc.c, tc.k)
+		}
+	}
+}