Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 318
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

You are going on a road trip, and would like to create a suitable music playlist. The trip will require `N` songs, though you only have `M` songs downloaded, where `M < N`. A valid playlist should select each song at least once, and guarantee a buffer of `B` songs between repeats.

Given `N, M, and B`, determine the number of valid playlists.

Pull request:
Day318
Resolves #648.

Thanks to @MaximGovorchuk for 2 great implementations.

Patch:
diff --git a/README.md b/README.md
index 73f5d44..4bd2678 100644
--- a/README.md
+++ b/README.md
@@ -328,6 +328,7 @@ problems from
 * [Day 315](https://github.com/vaskoz/dailycodingproblem-go/issues/642)
 * [Day 316](https://github.com/vaskoz/dailycodingproblem-go/issues/644)
 * [Day 317](https://github.com/vaskoz/dailycodingproblem-go/issues/645)
+* [Day 318](https://github.com/vaskoz/dailycodingproblem-go/issues/648)
 * [Day 319](https://github.com/vaskoz/dailycodingproblem-go/issues/649)
 * [Day 320](https://github.com/vaskoz/dailycodingproblem-go/issues/650)
 * [Day 321](https://github.com/vaskoz/dailycodingproblem-go/issues/651)
diff --git a/day318/problem.go b/day318/problem.go
new file mode 100644
index 0000000..b7c942b
--- /dev/null
+++ b/day318/problem.go
@@ -0,0 +1,82 @@
+package day318
+
+// NumberOfValidPlayListsRec is a recursive solution.
+// Runs in O(N) worst case time.
+func NumberOfValidPlayListsRec(n, m, b int) int {
+	if b >= m {
+		return 0
+	}
+
+	if n == 0 {
+		return 1
+	}
+
+	mp := m
+
+	if b != 0 {
+		mp--
+	}
+
+	return m * NumberOfValidPlayListsRec(n-1, mp, max(0, b-1))
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+
+	return b
+}
+
+// NumberOfValidPlayListsIterative is an iterative solution.
+// Runs in O(N) worst case time.
+func NumberOfValidPlayListsIterative(n, m, b int) int {
+	if b >= m {
+		return 0
+	}
+
+	total := 1
+	available := m
+
+	for i := 0; i <= b; i++ {
+		total *= available
+		available--
+	}
+
+	if available < m {
+		available++
+	}
+
+	for i := b + 1; i < n; i++ {
+		total *= available
+	}
+
+	return total
+}
+
+// NumberOfValidPlayListsFormula is a mathematical formula.
+// Technically, runs in O(1) if factorial and exponential functions are constant.
+// Formula: M!/(M-B!) * (M-B)^(N-B)
+func NumberOfValidPlayListsFormula(n, m, b int) int {
+	return binomial(m, m-b) * pow(m-b, n-b)
+}
+
+func binomial(a, b int) int {
+	result := 1
+
+	for ; a > b; a-- {
+		result *= a
+	}
+
+	return result
+}
+
+func pow(n, exp int) int {
+	result := 1
+
+	for i := 0; i < exp; i++ {
+		result *= n
+	}
+
+	return result
+}


Test patch:
diff --git a/day318/problem_test.go b/day318/problem_test.go
new file mode 100644
index 0000000..5f815e4
--- /dev/null
+++ b/day318/problem_test.go
@@ -0,0 +1,72 @@
+package day318
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	N, M, B  int
+	expected int
+}{
+	{4, 2, 1, 2},
+	{4, 2, 0, 16},
+	{4, 2, 2, 0},
+	{9, 2, 1, 2},
+	{9, 2, 0, 512},
+	{9, 3, 2, 6},
+	{9, 3, 1, 768},
+	{9, 3, 0, 19683},
+}
+
+func TestNumberOfValidPlayListsRec(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := NumberOfValidPlayListsRec(tc.N, tc.M, tc.B); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkNumberOfValidPlayListsRec(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NumberOfValidPlayListsRec(tc.N, tc.M, tc.B)
+		}
+	}
+}
+
+func TestNumberOfValidPlayListsIterative(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := NumberOfValidPlayListsIterative(tc.N, tc.M, tc.B); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkNumberOfValidPlayListsIterative(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NumberOfValidPlayListsIterative(tc.N, tc.M, tc.B)
+		}
+	}
+}
+
+func TestNumberOfValidPlayListsFormula(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := NumberOfValidPlayListsFormula(tc.N, tc.M, tc.B); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkNumberOfValidPlayListsFormula(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NumberOfValidPlayListsFormula(tc.N, tc.M, tc.B)
+		}
+	}
+}