Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 359
Good morning! Here's your coding interview problem for today.

This problem was asked by Slack.

You are given a string formed by concatenating several words corresponding to the integers zero through nine and then anagramming.

For example, the input could be 'niesevehrtfeev', which is an anagram of 'threefiveseven'. Note that there can be multiple instances of each integer.

Given this string, return the original integers in sorted order. In the example above, this would be `357`.

Pull request:
Day359
Resolves #708.

Patch:
diff --git a/README.md b/README.md
index 321ccea..b9438ab 100644
--- a/README.md
+++ b/README.md
@@ -340,3 +340,4 @@ problems from
 * [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
 * [Day 352](https://github.com/vaskoz/dailycodingproblem-go/issues/699)
 * [Day 353](https://github.com/vaskoz/dailycodingproblem-go/issues/701)
+* [Day 359](https://github.com/vaskoz/dailycodingproblem-go/issues/708)
diff --git a/day359/problem.go b/day359/problem.go
new file mode 100644
index 0000000..08f8f41
--- /dev/null
+++ b/day359/problem.go
@@ -0,0 +1,68 @@
+package day359
+
+import "fmt"
+
+// ErrNotPossible returns the error associated with an
+// impossible input.
+func ErrNotPossible() error {
+	return errNotPossible
+}
+
+var errNotPossible = fmt.Errorf("no solution possible")
+
+// ConvertAnagramToInt takes a concatenation
+// of integers and returns a sorted list of decimal integers.
+// Panics if impossible due to too many letters or incorrect
+// letters.
+func ConvertAnagramToInt(str string) (string, error) {
+	freq := make(map[rune]int)
+	for _, r := range str {
+		freq[r]++
+	}
+	nums := []string{"zero", "one", "two", "three", "four",
+		"five", "six", "seven", "eight", "nine"}
+	numFreq := make([]map[rune]int, len(nums))
+	for i := range nums {
+		numFreq[i] = make(map[rune]int)
+		for _, r := range nums[i] {
+			numFreq[i][r]++
+		}
+	}
+	return convertAnagramToInt(freq, numFreq, "")
+}
+
+// Runs DFS until a solution is found.
+func convertAnagramToInt(freq map[rune]int, nums []map[rune]int, result string) (string, error) {
+	baseCase := true
+	for _, c := range freq {
+		if c != 0 {
+			baseCase = false
+			break
+		}
+	}
+	if baseCase {
+		return result, nil
+	}
+	for digit := 0; digit < 10; digit++ {
+		valid := true
+		for r, c := range nums[digit] {
+			if freq[r]-c < 0 {
+				valid = false
+				break
+			}
+		}
+		if valid {
+			for r, c := range nums[digit] {
+				freq[r] -= c
+			}
+			r, err := convertAnagramToInt(freq, nums, fmt.Sprintf("%s%d", result, digit))
+			if err == nil {
+				return r, nil
+			}
+			for r, c := range nums[digit] {
+				freq[r] += c
+			}
+		}
+	}
+	return "", errNotPossible
+}


Test patch:
diff --git a/day359/problem_test.go b/day359/problem_test.go
new file mode 100644
index 0000000..68fdd81
--- /dev/null
+++ b/day359/problem_test.go
@@ -0,0 +1,31 @@
+package day359
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	anagram   string
+	sortedInt string
+	err       error
+}{
+	{"niesevehrtfeev", "357", nil},
+	{"fourzeroninesixseven", "04679", nil},
+	{"nineextra", "", ErrNotPossible()},
+}
+
+func TestConvertAnagramToInt(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := ConvertAnagramToInt(tc.anagram); result != tc.sortedInt || err != tc.err {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.sortedInt, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkConvertAnagramToInt(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ConvertAnagramToInt(tc.anagram) // nolint
+		}
+	}
+}