Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 12
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2
What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

Pull request:
Day12
Resolves #25.

Patch:
diff --git a/README.md b/README.md
index 78ccbc6..3ee6ba8 100644
--- a/README.md
+++ b/README.md
@@ -21,3 +21,4 @@ problems from
 * [Day 9](https://github.com/vaskoz/dailycodingproblem-go/issues/19)
 * [Day 10](https://github.com/vaskoz/dailycodingproblem-go/issues/21)
 * [Day 11](https://github.com/vaskoz/dailycodingproblem-go/issues/23)
+* [Day 12](https://github.com/vaskoz/dailycodingproblem-go/issues/25)
diff --git a/day12/problem.go b/day12/problem.go
new file mode 100644
index 0000000..d86d5c1
--- /dev/null
+++ b/day12/problem.go
@@ -0,0 +1,44 @@
+package day12
+
+import "sort"
+
+// UniqueClimbs calculates the number of possible ways to climb the steps.
+// Assumes that we have the given number of possible strides.
+// A stride is the number of steps possible.
+// Assumes strides are in sorted order.
+// Runs in exponential time.
+func UniqueClimbs(steps int, strides []int) int {
+	if steps < 0 {
+		return 0
+	} else if steps == 0 {
+		return 1
+	}
+	sum := 0
+	for _, stride := range strides {
+		sum += UniqueClimbs(steps-stride, strides)
+	}
+	return sum
+}
+
+// UniqueClimbsDS doesn't use recursion and instead iterates using memoization of subproblem results.
+// Time complexity is O(K*N) where K is the number of possible strides and N is the number of steps.
+func UniqueClimbsDS(steps int, strides []int) int {
+	sort.Ints(strides)
+	stepData := make([]int, steps+1)
+	stepData[0] = 1
+	return uniqueClimbsDS(steps, strides, stepData)[len(stepData)-1]
+}
+
+func uniqueClimbsDS(steps int, strides, stepData []int) []int {
+	for step := 1; step < len(stepData); step++ {
+		sum := 0
+		for _, stride := range strides {
+			if step < stride {
+				continue
+			}
+			sum += stepData[step-stride]
+		}
+		stepData[step] = sum
+	}
+	return stepData
+}


Test patch:
diff --git a/day12/problem_test.go b/day12/problem_test.go
new file mode 100644
index 0000000..8bf8a7c
--- /dev/null
+++ b/day12/problem_test.go
@@ -0,0 +1,51 @@
+package day12
+
+import "testing"
+
+var testcases = []struct {
+	steps    int
+	strides  []int
+	expected int
+}{
+	{4, []int{1, 2}, 5},
+	{5, []int{1, 2}, 8},
+	{5, []int{1, 2}, 8},
+	{4, []int{1, 2, 3}, 7},
+	{3, []int{1, 2, 3}, 4},
+	{100, []int{1, 100}, 2},
+	{100, []int{1, 50, 100}, 54},
+}
+
+func TestUniqueClimbs(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := UniqueClimbs(tc.steps, tc.strides); result != tc.expected {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkUniqueClimbs(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			UniqueClimbs(tc.steps, tc.strides)
+		}
+	}
+}
+
+func TestUniqueClimbsDS(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := UniqueClimbsDS(tc.steps, tc.strides); result != tc.expected {
+			t.Errorf("Expected %v but got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkUniqueClimbsDS(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			UniqueClimbsDS(tc.steps, tc.strides)
+		}
+	}
+}