Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 226
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

You come across a dictionary of sorted words in a language you've never seen before. Write a program that returns the correct order of letters in this language.

For example, given `['xww', 'wxyz', 'wxyw', 'ywx', 'ywz']`, you should return `['x', 'z', 'w', 'y']`.

Pull request description:
Day226
Resolves #467.

Patch:
diff --git a/README.md b/README.md
index 3626459..8cb2218 100644
--- a/README.md
+++ b/README.md
@@ -236,3 +236,4 @@ problems from
 * [Day 223](https://github.com/vaskoz/dailycodingproblem-go/issues/460)
 * [Day 224](https://github.com/vaskoz/dailycodingproblem-go/issues/462)
 * [Day 225](https://github.com/vaskoz/dailycodingproblem-go/issues/465)
+* [Day 226](https://github.com/vaskoz/dailycodingproblem-go/issues/467)
diff --git a/day226/problem.go b/day226/problem.go
new file mode 100644
index 0000000..159474d
--- /dev/null
+++ b/day226/problem.go
@@ -0,0 +1,58 @@
+package day226
+
+// AlienLanguageOrder returns the correct order of letters
+// of an alien language.
+func AlienLanguageOrder(sortedWords []string) []rune {
+	g := make(map[rune]map[rune]struct{})
+	for i := 1; i < len(sortedWords); i++ {
+		var firstDiff int
+		for firstDiff = 0; sortedWords[i-1][firstDiff] == sortedWords[i][firstDiff]; firstDiff++ {
+		}
+		if _, exists := g[rune(sortedWords[i-1][firstDiff])]; !exists {
+			g[rune(sortedWords[i-1][firstDiff])] = make(map[rune]struct{})
+		}
+		g[rune(sortedWords[i-1][firstDiff])][rune(sortedWords[i][firstDiff])] = struct{}{}
+	}
+	return kahnsTopologicalSort(g)
+}
+
+func kahnsTopologicalSort(g map[rune]map[rune]struct{}) []rune {
+	var result []rune
+	s := make(map[rune]struct{})
+	for k := range g {
+		s[k] = struct{}{}
+	}
+	for _, v := range g {
+		for k := range v {
+			delete(s, k)
+		}
+	}
+	for len(s) != 0 {
+		var n rune
+		for k := range s {
+			n = k
+			break
+		}
+		delete(s, n)
+		result = append(result, n)
+		for m := range g[n] {
+			delete(g[n], m)
+			if !hasIncomingEdges(g, m) {
+				s[m] = struct{}{}
+			}
+		}
+
+	}
+	return result
+}
+
+func hasIncomingEdges(g map[rune]map[rune]struct{}, m rune) bool {
+	for _, to := range g {
+		for k := range to {
+			if k == m {
+				return true
+			}
+		}
+	}
+	return false
+}


Test patch:
diff --git a/day226/problem_test.go b/day226/problem_test.go
new file mode 100644
index 0000000..298fea8
--- /dev/null
+++ b/day226/problem_test.go
@@ -0,0 +1,30 @@
+package day226
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	alienWords []string
+	order      []rune
+}{
+	{[]string{"xww", "wxyz", "wxyw", "ywx", "ywz"}, []rune{'x', 'z', 'w', 'y'}},
+}
+
+func TestAlienLanguageOrder(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if order := AlienLanguageOrder(tc.alienWords); !reflect.DeepEqual(order, tc.order) {
+			t.Errorf("Expected %v, got %v", tc.order, order)
+		}
+	}
+}
+
+func BenchmarkAlienLanguageOrder(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AlienLanguageOrder(tc.alienWords)
+		}
+	}
+}