Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 329
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

The stable marriage problem is defined as follows:

Suppose you have `N` men and `N` women, and each person has ranked their prospective opposite-sex partners in order of preference.

For example, if `N = 3`, the input could be something like this:
```
guy_preferences = {
    'andrew': ['caroline', 'abigail', 'betty'],
    'bill': ['caroline', 'betty', 'abigail'],
    'chester': ['betty', 'caroline', 'abigail'],
}

gal_preferences = {
    'abigail': ['andrew', 'bill', 'chester'],
    'betty': ['bill', 'andrew', 'chester'],
    'caroline': ['bill', 'chester', 'andrew']
}
```
Write an algorithm that pairs the men and women together in such a way that no two people of opposite sex would both rather be with each other than with their current partners.

Pull request description:
Day329
Resolves #664.

Patch:
diff --git a/README.md b/README.md
index 0ff32a8..82990c5 100644
--- a/README.md
+++ b/README.md
@@ -336,6 +336,7 @@ problems from
 * [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
 * [Day 326](https://github.com/vaskoz/dailycodingproblem-go/issues/661)
 * [Day 328](https://github.com/vaskoz/dailycodingproblem-go/issues/663)
+* [Day 329](https://github.com/vaskoz/dailycodingproblem-go/issues/664)
 * [Day 331](https://github.com/vaskoz/dailycodingproblem-go/issues/666)
 * [Day 332](https://github.com/vaskoz/dailycodingproblem-go/issues/669)
 * [Day 333](https://github.com/vaskoz/dailycodingproblem-go/issues/668)
diff --git a/day329/problem.go b/day329/problem.go
new file mode 100644
index 0000000..7ccd287
--- /dev/null
+++ b/day329/problem.go
@@ -0,0 +1,66 @@
+package day329
+
+// Matches is a mapping from key=male to value=female.
+type Matches map[string]string
+
+// StableMarriage returns N stable marriage pairs.
+func StableMarriage(males, females map[string][]string) Matches {
+	free := make(map[string]struct{}, len(males)*2)
+	proposals := make(map[string]int, len(males)*2)
+	engaged := make(map[string]string, len(males)*2)
+
+	for person := range males {
+		free[person] = struct{}{}
+		proposals[person] = 0
+	}
+
+	for person := range females {
+		free[person] = struct{}{}
+	}
+
+	for len(proposals) != 0 {
+		var m string
+
+		for man := range proposals {
+			if _, ok := free[man]; ok {
+				m = man
+				break
+			}
+		}
+
+		if m == "" {
+			break
+		}
+
+		w := males[m][proposals[m]]
+
+		if _, ok := free[w]; ok {
+			engaged[m] = w
+			engaged[w] = m
+			delete(free, m)
+			delete(free, w)
+		} else {
+			mp := engaged[w]
+
+			for _, suitor := range females[w] {
+				if suitor == m {
+					delete(engaged, mp)
+					engaged[w] = m
+					engaged[m] = w
+					delete(free, m)
+					free[mp] = struct{}{}
+					break
+				} else if suitor == mp {
+					break
+				}
+			}
+		}
+		proposals[m]++
+	}
+
+	for female := range females {
+		delete(engaged, female)
+	}
+
+	return engaged
+}


Test patch:
diff --git a/day329/problem_test.go b/day329/problem_test.go
new file mode 100644
index 0000000..175f7cb
--- /dev/null
+++ b/day329/problem_test.go
@@ -0,0 +1,82 @@
+package day329
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	males, females map[string][]string
+	matches        Matches
+}{
+	{
+		map[string][]string{
+			"andrew":  {"caroline", "abigail", "betty"},
+			"bill":    {"caroline", "betty", "abigail"},
+			"chester": {"betty", "caroline", "abigail"},
+		},
+		map[string][]string{
+			"abigail":  {"andrew", "bill", "chester"},
+			"betty":    {"bill", "andrew", "chester"},
+			"caroline": {"bill", "chester", "andrew"},
+		},
+		Matches{
+			"andrew":  "abigail",
+			"bill":    "caroline",
+			"chester": "betty",
+		},
+	},
+	{
+		map[string][]string{
+			"0": {"7", "5", "6", "4"},
+			"1": {"5", "4", "6", "7"},
+			"2": {"4", "5", "6", "7"},
+			"3": {"4", "5", "6", "7"},
+		},
+		map[string][]string{
+			"4": {"0", "1", "2", "3"},
+			"5": {"0", "1", "2", "3"},
+			"6": {"0", "1", "2", "3"},
+			"7": {"0", "1", "2", "3"},
+		},
+		Matches{
+			"2": "4",
+			"1": "5",
+			"3": "6",
+			"0": "7",
+		},
+	},
+	{
+		map[string][]string{
+			"0": {"2", "3"},
+			"1": {"3", "2"},
+		},
+		map[string][]string{
+			"2": {"1", "0"},
+			"3": {"1", "0"},
+		},
+		Matches{
+			"0": "2",
+			"1": "3",
+		},
+	},
+}
+
+func TestStableMarriage(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := StableMarriage(tc.males, tc.females); !reflect.DeepEqual(res, tc.matches) {
+			t.Errorf("Expected %v, got %v", tc.matches, res)
+		}
+	}
+}
+
+func BenchmarkStableMarriage(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			StableMarriage(tc.males, tc.females)
+		}
+	}
+}