Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 321
Good morning! Here's your coding interview problem for today.

This problem was asked by PagerDuty.

Given a positive integer `N`, find the smallest number of steps it will take to reach `1`.

There are two kinds of permitted steps:

* You may decrement `N` to `N - 1`.
* If `a * b = N`, you may decrement `N` to the larger of `a` and `b`.
For example, given `100`, you can reach `1` in five steps with the following route: `100 -> 10 -> 9 -> 3 -> 2 -> 1`.

Pull request description:
Day321
Resolves #651.

Patch:
diff --git a/README.md b/README.md
index 939059e..3693706 100644
--- a/README.md
+++ b/README.md
@@ -323,3 +323,4 @@ problems from
 * [Day 314](https://github.com/vaskoz/dailycodingproblem-go/issues/640)
 * [Day 315](https://github.com/vaskoz/dailycodingproblem-go/issues/642)
 * [Day 317](https://github.com/vaskoz/dailycodingproblem-go/issues/645)
+* [Day 321](https://github.com/vaskoz/dailycodingproblem-go/issues/651)
diff --git a/day321/problem.go b/day321/problem.go
new file mode 100644
index 0000000..e4843e5
--- /dev/null
+++ b/day321/problem.go
@@ -0,0 +1,40 @@
+package day321
+
+import "math"
+
+// SmallestStepsToOne returns the smallest possible
+// number of steps to reach run using two rules.
+// First, n-1
+// Second, a*b=N goto the larger of a and b.
+// This is effectively BFS.
+func SmallestStepsToOne(n int) int {
+	if n < 1 {
+		panic("n must be greater than 0")
+	}
+	seen := make(map[int]struct{})
+	q := []int{n}
+	var steps int
+	for len(q) != 0 {
+		nextQ := make([]int, 0, 2*len(q))
+		for _, v := range q {
+			if v == 1 {
+				nextQ = nil
+				break
+			} else if _, found := seen[v]; !found {
+				seen[v] = struct{}{}
+				nextQ = append(nextQ, v-1)
+				a := v
+				for b := int(math.Sqrt(float64(v))); b > 0; b-- {
+					if v%b == 0 {
+						a = v / b
+						break
+					}
+				}
+				nextQ = append(nextQ, a)
+			}
+		}
+		q = nextQ
+		steps++
+	}
+	return steps - 1
+}


Test patch:
diff --git a/day321/problem_test.go b/day321/problem_test.go
new file mode 100644
index 0000000..3636e44
--- /dev/null
+++ b/day321/problem_test.go
@@ -0,0 +1,43 @@
+package day321
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n, expected int
+}{
+	{100, 5},
+	{1, 0}, // 1
+	{2, 1}, // 2 -> 1
+	{3, 2}, // 3 -> 2 -> 1
+	{4, 2}, // 4 -> 2 -> 1
+	{5, 3}, // 5 -> 4 -> 2 -> 1
+	{6, 3}, // 6 -> 3 -> 2 -> 1
+}
+
+func TestSmallestStepsToOne(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestStepsToOne(tc.n); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func TestSmallestStepsToOneBadInput(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected an error, but got nil")
+		}
+	}()
+	SmallestStepsToOne(0)
+}
+
+func BenchmarkSmallestStepsToOne(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestStepsToOne(tc.n)
+		}
+	}
+}