Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 128
Good morning! Here's your coding interview problem for today.

The Tower of Hanoi is a puzzle game with three rods and n disks, each a different size.

All the disks start off on the first rod in a stack. They are ordered by size, with the largest disk on the bottom and the smallest one at the top.

The goal of this puzzle is to move all the disks from the first rod to the last rod while following these rules:

You can only move one disk at a time.
A move consists of taking the uppermost disk from one of the stacks and placing it on top of another stack.
You cannot place a larger disk on top of a smaller disk.
Write a function that prints out all the steps necessary to complete the Tower of Hanoi. You should assume that the rods are numbered, with the first rod being 1, the second (auxiliary) rod being 2, and the last (goal) rod being 3.

For example, with n = 3, we can do this in 7 moves:

Move 1 to 3
Move 1 to 2
Move 3 to 2
Move 1 to 3
Move 2 to 1
Move 2 to 3
Move 1 to 3

Pull request:
Day128
Resolves #260.

Patch:
diff --git a/README.md b/README.md
index c1553c8..46a144b 100644
--- a/README.md
+++ b/README.md
@@ -134,5 +134,6 @@ problems from
 * [Day 125](https://github.com/vaskoz/dailycodingproblem-go/issues/257)
 * [Day 126](https://github.com/vaskoz/dailycodingproblem-go/issues/258)
 * [Day 127](https://github.com/vaskoz/dailycodingproblem-go/issues/259)
+* [Day 128](https://github.com/vaskoz/dailycodingproblem-go/issues/260)
 * [Day 129](https://github.com/vaskoz/dailycodingproblem-go/issues/263)
 * [Day 130](https://github.com/vaskoz/dailycodingproblem-go/issues/265)
diff --git a/day128/problem.go b/day128/problem.go
new file mode 100644
index 0000000..9e3326e
--- /dev/null
+++ b/day128/problem.go
@@ -0,0 +1,19 @@
+package day128
+
+import "fmt"
+
+// TowerOfHanoiMoves returns a slice of strings that describe how to optimally achieve
+// the goal. O(2^N) is the complexity and result size.
+func TowerOfHanoiMoves(disks int) []string {
+	return towerOfHanoi(disks, 1, 3, 2)
+}
+
+func towerOfHanoi(disks, from, to, extra int) []string {
+	if disks == 1 {
+		return []string{fmt.Sprintf("Move %d to %d", from, to)}
+	}
+	moves := towerOfHanoi(disks-1, from, extra, to)
+	moves = append(moves, fmt.Sprintf("Move %d to %d", from, to))
+	moves = append(moves, towerOfHanoi(disks-1, extra, to, from)...)
+	return moves
+}


Test patch:
diff --git a/day128/problem_test.go b/day128/problem_test.go
new file mode 100644
index 0000000..2a0ed08
--- /dev/null
+++ b/day128/problem_test.go
@@ -0,0 +1,55 @@
+package day128
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	disks int
+	moves []string
+}{
+	{3, []string{
+		"Move 1 to 3",
+		"Move 1 to 2",
+		"Move 3 to 2",
+		"Move 1 to 3",
+		"Move 2 to 1",
+		"Move 2 to 3",
+		"Move 1 to 3",
+	}},
+	{4, []string{
+		"Move 1 to 2",
+		"Move 1 to 3",
+		"Move 2 to 3",
+		"Move 1 to 2",
+		"Move 3 to 1",
+		"Move 3 to 2",
+		"Move 1 to 2",
+		"Move 1 to 3",
+		"Move 2 to 3",
+		"Move 2 to 1",
+		"Move 3 to 1",
+		"Move 2 to 3",
+		"Move 1 to 2",
+		"Move 1 to 3",
+		"Move 2 to 3",
+	}},
+}
+
+func TestTowerOfHanoiMoves(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if moves := TowerOfHanoiMoves(tc.disks); !reflect.DeepEqual(moves, tc.moves) {
+			t.Errorf("Expected %v got %v", tc.moves, moves)
+		}
+	}
+}
+
+func BenchmarkTowerOfHanoiMoves(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TowerOfHanoiMoves(tc.disks)
+		}
+	}
+}