Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 272
Good morning! Here's your coding interview problem for today.

This problem was asked by Spotify.

Write a function, `throw_dice(N, faces, total)`, that determines how many ways it is possible to throw `N` dice with some number of faces each to get a specific total.

For example, `throw_dice(3, 6, 7)` should equal `15`.

Pull request description:
Day272
Resolves #555.

Patch:
diff --git a/README.md b/README.md
index 91ed69c..6e819b2 100644
--- a/README.md
+++ b/README.md
@@ -278,3 +278,4 @@ problems from
 * [Day 269](https://github.com/vaskoz/dailycodingproblem-go/issues/547)
 * [Day 270](https://github.com/vaskoz/dailycodingproblem-go/issues/548)
 * [Day 271](https://github.com/vaskoz/dailycodingproblem-go/issues/553)
+* [Day 272](https://github.com/vaskoz/dailycodingproblem-go/issues/555)
diff --git a/day272/problem.go b/day272/problem.go
new file mode 100644
index 0000000..b6d953b
--- /dev/null
+++ b/day272/problem.go
@@ -0,0 +1,53 @@
+package day272
+
+// PossibleWaysToThrowFaster returns the number of possible distinct throws
+// of N dice with a given number of faces to equal a desired total.
+// Runs in O(dice*total) with memory O(dice*total).
+func PossibleWaysToThrowFaster(ndice, faces, total int) int {
+	table := make([][]int, ndice+1)
+	for i := range table {
+		table[i] = make([]int, total+1)
+	}
+	table[0][0] = 1
+	for i := 1; i <= ndice; i++ {
+		for j := i; j <= total; j++ {
+			table[i][j] = table[i][j-1] + table[i-1][j-1]
+			if j-faces-1 >= 0 {
+				table[i][j] -= table[i-1][j-faces-1]
+			}
+		}
+	}
+	return table[ndice][total]
+}
+
+// PossibleWaysToThrow returns the number of possible distinct throws
+// of N dice with a given number of faces to equal a desired total.
+// Runs in O(dice*faces*total) with memory O(dice*total).
+func PossibleWaysToThrow(ndice, faces, total int) int {
+	//# The main function that returns number of ways to get sum 'x'
+	//# with 'n' dice and 'm' with m faces.
+	table := make([][]int, ndice+1)
+	for i := range table {
+		table[i] = make([]int, total+1)
+	}
+	for i := 0; i < min(faces+1, total+1); i++ {
+		table[1][i] = 1
+	}
+	for i := 2; i < ndice+1; i++ {
+		for j := 1; j < total+1; j++ {
+			for k := 1; k < min(faces+1, j); k++ {
+				table[i][j] += table[i-1][j-k]
+			}
+		}
+	}
+	lastRow := len(table) - 1
+	lastCol := len(table[lastRow]) - 1
+	return table[lastRow][lastCol]
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day272/problem_test.go b/day272/problem_test.go
new file mode 100644
index 0000000..38c16e2
--- /dev/null
+++ b/day272/problem_test.go
@@ -0,0 +1,45 @@
+package day272
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n, faces, total int
+	possibleWays    int
+}{
+	{3, 6, 7, 15},
+}
+
+func TestPossibleWaysToThrow(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PossibleWaysToThrow(tc.n, tc.faces, tc.total); result != tc.possibleWays {
+			t.Errorf("Expected %v, got %v", tc.possibleWays, result)
+		}
+	}
+}
+
+func BenchmarkPossibleWaysToThrow(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PossibleWaysToThrow(tc.n, tc.faces, tc.total)
+		}
+	}
+}
+
+func TestPossibleWaysToThrowFaster(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := PossibleWaysToThrowFaster(tc.n, tc.faces, tc.total); result != tc.possibleWays {
+			t.Errorf("Expected %v, got %v", tc.possibleWays, result)
+		}
+	}
+}
+
+func BenchmarkPossibleWaysToThrowFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PossibleWaysToThrowFaster(tc.n, tc.faces, tc.total)
+		}
+	}
+}