Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 239
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

One way to unlock an Android phone is through a pattern of swipes across a 1-9 keypad.

For a pattern to be valid, it must satisfy the following:

All of its keys must be distinct.
It must not connect two keys by jumping over a third key, unless that key has already been used.
For example, `4 - 2 - 1 - 7` is a valid pattern, whereas `2 - 1 - 7` is not.

Find the total number of valid unlock patterns of length `N`, where `1 <= N <= 9`.

Pull request description:
Day239
Resolves #491.

Patch:
diff --git a/README.md b/README.md
index d42c62a..4f7bd49 100644
--- a/README.md
+++ b/README.md
@@ -249,6 +249,7 @@ problems from
 * [Day 236](https://github.com/vaskoz/dailycodingproblem-go/issues/485)
 * [Day 237](https://github.com/vaskoz/dailycodingproblem-go/issues/487)
 * [Day 238](https://github.com/vaskoz/dailycodingproblem-go/issues/489)
+* [Day 239](https://github.com/vaskoz/dailycodingproblem-go/issues/491)
 * [Day 240](https://github.com/vaskoz/dailycodingproblem-go/issues/492)
 * [Day 241](https://github.com/vaskoz/dailycodingproblem-go/issues/493)
 * [Day 242](https://github.com/vaskoz/dailycodingproblem-go/issues/498)
diff --git a/day239/problem.go b/day239/problem.go
new file mode 100644
index 0000000..e471b02
--- /dev/null
+++ b/day239/problem.go
@@ -0,0 +1,36 @@
+package day239
+
+// ValidUnlockKeypadNumber returns the number of possible
+// valid combinations.
+func ValidUnlockKeypadNumber() int {
+	var jumps [10][10]int
+	jumps[1][3], jumps[3][1] = 2, 2
+	jumps[7][9], jumps[9][7] = 8, 8
+	jumps[1][7], jumps[7][1] = 4, 4
+	jumps[3][9], jumps[9][3] = 6, 6
+	jumps[1][9], jumps[9][1], jumps[2][8], jumps[8][2],
+		jumps[3][7], jumps[7][3], jumps[4][6], jumps[6][4] = 5, 5, 5, 5, 5, 5, 5, 5
+	var visited [10]bool
+	ways := 0
+	for numDots := 4; numDots < 10; numDots++ {
+		ways += 4 * validUnlockKeypadNumber(visited, jumps, 1, numDots-1)
+		ways += 4 * validUnlockKeypadNumber(visited, jumps, 2, numDots-1)
+		ways += validUnlockKeypadNumber(visited, jumps, 5, numDots-1)
+	}
+	return ways
+}
+
+func validUnlockKeypadNumber(visited [10]bool, jumps [10][10]int, cur, to int) int {
+	if to == 0 {
+		return 1
+	}
+	ways := 0
+	visited[cur] = true
+	for i := 1; i < 10; i++ {
+		if !visited[i] && (jumps[i][cur] == 0 || visited[jumps[i][cur]]) {
+			ways += validUnlockKeypadNumber(visited, jumps, i, to-1)
+		}
+	}
+	visited[cur] = false
+	return ways
+}


Test patch:
diff --git a/day239/problem_test.go b/day239/problem_test.go
new file mode 100644
index 0000000..4a0365f
--- /dev/null
+++ b/day239/problem_test.go
@@ -0,0 +1,16 @@
+package day239
+
+import "testing"
+
+func TestValidUnlockKeypadNumber(t *testing.T) {
+	t.Parallel()
+	if result := ValidUnlockKeypadNumber(); result != 389112 {
+		t.Errorf("Expected 389112, got %v", result)
+	}
+}
+
+func BenchmarkValidUnlockKeypadNumber(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		ValidUnlockKeypadNumber()
+	}
+}