Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 170
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a `start` word, an `end` word, and a dictionary of valid words, find the shortest transformation sequence from start to end such that only one letter is changed at each step of the sequence, and each transformed word exists in the dictionary. If there is no possible transformation, return null. Each word in the dictionary have the same length as start and end and is lowercase.

For example, given `start = "dog", end = "cat"`, and `dictionary = {"dot", "dop", "dat", "cat"}`, return `["dog", "dot", "dat", "cat"]`.

Given `start = "dog"`, `end = "cat"`, and `dictionary = {"dot", "tod", "dat", "dar"}`, return `null` as there is no possible transformation from dog to cat.

Pull request:
Day170
Resolves #353.

Patch:
diff --git a/README.md b/README.md
index b862e6e..b2e55e4 100644
--- a/README.md
+++ b/README.md
@@ -180,3 +180,4 @@ problems from
 * [Day 166](https://github.com/vaskoz/dailycodingproblem-go/issues/346)
 * [Day 167](https://github.com/vaskoz/dailycodingproblem-go/issues/347)
 * [Day 168](https://github.com/vaskoz/dailycodingproblem-go/issues/348)
+* [Day 170](https://github.com/vaskoz/dailycodingproblem-go/issues/353)
diff --git a/day170/problem.go b/day170/problem.go
new file mode 100644
index 0000000..6fb4680
--- /dev/null
+++ b/day170/problem.go
@@ -0,0 +1,50 @@
+package day170
+
+import "errors"
+
+var errTransformationNotPossible = errors.New("transformation is not possible")
+
+// ErrTransformationNotPossible is returned when the start word can not be
+// transformed into the end word, 1 letter at a time given the dictionary.
+func ErrTransformationNotPossible() error {
+	return errTransformationNotPossible
+}
+
+// ShortestTransformation returns the shortest possible sequence of transformations
+// to reach 'end' from 'start' using the given dictionary.
+// Runs in O(N^2) time.
+// Assumes start, end and dictionary words are of the same length.
+func ShortestTransformation(start, end string, dictionary []string) ([]string, error) {
+	queue := [][]string{{start}}
+	for len(queue) != 0 {
+		path := queue[0]
+		n := path[len(path)-1]
+		if n == end {
+			return path, nil
+		}
+		visited := make(map[string]struct{})
+		for _, n := range path {
+			visited[n] = struct{}{}
+		}
+		queue = queue[1:]
+		for _, v := range dictionary {
+			if _, seen := visited[v]; !seen && editDistance(n, v) == 1 {
+				newPath := append([]string{}, path...)
+				newPath = append(newPath, v)
+				queue = append(queue, newPath)
+			}
+		}
+
+	}
+	return nil, ErrTransformationNotPossible()
+}
+
+func editDistance(a, b string) int {
+	var diffs int
+	for i := range a {
+		if a[i] != b[i] {
+			diffs++
+		}
+	}
+	return diffs
+}


Test patch:
diff --git a/day170/problem_test.go b/day170/problem_test.go
new file mode 100644
index 0000000..6874472
--- /dev/null
+++ b/day170/problem_test.go
@@ -0,0 +1,33 @@
+package day170
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	start, end  string
+	dict        []string
+	expected    []string
+	expectedErr error
+}{
+	{"dog", "cat", []string{"dot", "dop", "dat", "cat"}, []string{"dog", "dot", "dat", "cat"}, nil},
+	{"dog", "cat", []string{"dot", "tod", "dat", "dar"}, nil, ErrTransformationNotPossible()},
+}
+
+func TestShortestTransformation(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := ShortestTransformation(tc.start, tc.end, tc.dict); err != tc.expectedErr || !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.expected, tc.expectedErr, result, err)
+		}
+	}
+}
+
+func BenchmarkShortestTransformation(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ShortestTransformation(tc.start, tc.end, tc.dict)
+		}
+	}
+}