Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 250
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

A cryptarithmetic puzzle is a mathematical game where the digits of some numbers are represented by letters. Each letter represents a unique digit.

For example, a puzzle of the form:
```
  SEND
+ MORE
--------
 MONEY
```
may have the solution:

`{'S': 9, 'E': 5, 'N': 6, 'D': 7, 'M': 1, 'O', 0, 'R': 8, 'Y': 2}`

Given a three-word puzzle like the one above, create an algorithm that finds a solution.

Pull request:
Day250
Resolves #516.

Patch:
diff --git a/README.md b/README.md
index 55077a5..7a8bb45 100644
--- a/README.md
+++ b/README.md
@@ -261,6 +261,7 @@ problems from
 * [Day 247](https://github.com/vaskoz/dailycodingproblem-go/issues/510)
 * [Day 248](https://github.com/vaskoz/dailycodingproblem-go/issues/512)
 * [Day 249](https://github.com/vaskoz/dailycodingproblem-go/issues/514)
+* [Day 250](https://github.com/vaskoz/dailycodingproblem-go/issues/516)
 * [Day 251](https://github.com/vaskoz/dailycodingproblem-go/issues/517)
 * [Day 252](https://github.com/vaskoz/dailycodingproblem-go/issues/519)
 * [Day 253](https://github.com/vaskoz/dailycodingproblem-go/issues/521)
diff --git a/day250/problem.go b/day250/problem.go
new file mode 100644
index 0000000..e8948e0
--- /dev/null
+++ b/day250/problem.go
@@ -0,0 +1,76 @@
+package day250
+
+import "sort"
+
+// CryptarithmeticAdditionPuzzle returns a possible solution to the addition.
+func CryptarithmeticAdditionPuzzle(first, second, result string) map[rune]int {
+	letters := make(map[rune]struct{}, 10)
+	for _, part := range []string{first, second, result} {
+		for _, r := range part {
+			letters[r] = struct{}{}
+		}
+	}
+	if len(letters) > 10 {
+		return nil
+	}
+	runes := make([]rune, 0, len(letters))
+	for r := range letters {
+		runes = append(runes, r)
+	}
+	sort.Slice(runes, func(i, j int) bool {
+		return runes[i] < runes[j]
+	})
+	availDigits := make([]bool, 10)
+	for i := 0; i < 10; i++ {
+		availDigits[i] = true
+	}
+	return backtrackingSearch(runes, make(map[rune]int), availDigits, first, second, result)
+}
+
+func backtrackingSearch(runes []rune, visited map[rune]int,
+	availDigits []bool, first, second, result string) map[rune]int {
+	if len(runes) == 0 && validSolution(first, second, result, visited) {
+		return visited
+	} else if len(runes) == 0 {
+		return nil
+	}
+	nextRune := runes[0]
+	for d, avail := range availDigits {
+		if !avail {
+			continue
+		}
+		availDigits[d] = false
+		visited[nextRune] = d
+		if result := backtrackingSearch(runes[1:], visited, availDigits, first, second, result); result != nil {
+			return result
+		}
+		delete(visited, nextRune)
+		availDigits[d] = true
+	}
+	return nil
+}
+
+func validSolution(first, second, result string, visited map[rune]int) bool {
+	f := []rune(first)
+	s := []rune(second)
+	t := []rune(result)
+	exp := 1
+	var fi int
+	for i := len(f) - 1; i >= 0; i-- {
+		fi += visited[f[i]] * exp
+		exp *= 10
+	}
+	exp = 1
+	var si int
+	for i := len(s) - 1; i >= 0; i-- {
+		si += visited[s[i]] * exp
+		exp *= 10
+	}
+	exp = 1
+	var ti int
+	for i := len(t) - 1; i >= 0; i-- {
+		ti += visited[t[i]] * exp
+		exp *= 10
+	}
+	return fi+si == ti
+}


Test patch:
diff --git a/day250/problem_test.go b/day250/problem_test.go
new file mode 100644
index 0000000..851875c
--- /dev/null
+++ b/day250/problem_test.go
@@ -0,0 +1,51 @@
+package day250
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	first, second, result string
+	solution              map[rune]int
+}{
+	{
+		"SEND",
+		"MORE",
+		"MONEY",
+		map[rune]int{
+			'S': 7,
+			'E': 5,
+			'N': 3,
+			'D': 1,
+			'M': 0,
+			'O': 8,
+			'R': 2,
+			'Y': 6,
+		},
+	},
+	{
+		"ABCDEFGHIJKL",
+		"MNOPQRSTUVWXYZ",
+		"TOOMANY",
+		nil,
+	},
+}
+
+func TestCryptarithmeticAdditionPuzzle(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := CryptarithmeticAdditionPuzzle(tc.first, tc.second, tc.result); !reflect.DeepEqual(result, tc.solution) {
+			t.Errorf("Expected %v, got %v", tc.solution, result)
+		}
+	}
+}
+
+func BenchmarkCryptarithmeticAdditionPuzzle(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CryptarithmeticAdditionPuzzle(tc.first, tc.second, tc.result)
+		}
+	}
+}