Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 361
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Mastermind is a two-player game in which the first player attempts to guess the secret code of the second. In this version, the code may be any six-digit number with all distinct digits.

Each turn the first player guesses some number, and the second player responds by saying how many digits in this number correctly matched their location in the secret code. For example, if the secret code were `123456`, then a guess of `175286` would score two, since `1` and `6` were correctly placed.

Write an algorithm which, given a sequence of guesses and their scores, determines whether there exists some secret code that could have produced them.

For example, for the following scores you should return `True`, since they correspond to the secret code `123456`:

`{175286: 2, 293416: 3, 654321: 0}`
However, it is impossible for any key to result in the following scores, so in this case you should return `False`:
`{123456: 4, 345678: 4, 567890: 4}`

Pull request:
Day361
Resolves #712.

Patch:
diff --git a/README.md b/README.md
index 42ff810..478ce59 100644
--- a/README.md
+++ b/README.md
@@ -342,3 +342,4 @@ problems from
 * [Day 353](https://github.com/vaskoz/dailycodingproblem-go/issues/701)
 * [Day 359](https://github.com/vaskoz/dailycodingproblem-go/issues/708)
 * [Day 360](https://github.com/vaskoz/dailycodingproblem-go/issues/709)
+* [Day 361](https://github.com/vaskoz/dailycodingproblem-go/issues/712)
diff --git a/day361/problem.go b/day361/problem.go
new file mode 100644
index 0000000..b8356aa
--- /dev/null
+++ b/day361/problem.go
@@ -0,0 +1,83 @@
+package day361
+
+import "fmt"
+
+// Guess represents a code and a score for that guess.
+type Guess struct {
+	Code  string
+	Score int
+}
+
+// ValidMastermindGuesses returns true if a code exists that
+// correspond to a valid Mastermind code.
+// Runs in O(151,200*N) time.
+// There are 151,200 permutations of 6 unique digits.
+// 10*9*8*7*6*5 == 151,200 permutations. N is the number of
+// guesses.
+func ValidMastermindGuesses(guesses []Guess) bool {
+	for _, p := range perm6([]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}) {
+		valid := true
+		for _, g := range guesses {
+			var count int
+			for i := 0; i < len(p); i++ {
+				if p[i] == g.Code[i] {
+					count++
+				}
+			}
+			if count != g.Score {
+				valid = false
+				break
+			}
+		}
+		if valid {
+			return true
+		}
+	}
+	return false
+}
+
+// ValidMastermindGuessesAll returns all the codes that
+// correspond to a valid Mastermind code.
+// Runs in O(151,200*N) time.
+// There are 151,200 permutations of 6 unique digits.
+// 10*9*8*7*6*5 == 151,200 permutations. N is the number of
+// guesses.
+func ValidMastermindGuessesAll(guesses []Guess) []string {
+	var result []string
+	for _, p := range perm6([]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}) {
+		valid := true
+		for _, g := range guesses {
+			var count int
+			for i := 0; i < len(p); i++ {
+				if p[i] == g.Code[i] {
+					count++
+				}
+			}
+			if count != g.Score {
+				valid = false
+				break
+			}
+		}
+		if valid {
+			result = append(result, p)
+		}
+	}
+	return result
+}
+
+func perm6(digits []int) []string {
+	if len(digits) == 4 {
+		return []string{""}
+	}
+	var result []string
+	for i, d := range digits {
+		ds := fmt.Sprintf("%d", d)
+		var subdigits []int
+		subdigits = append(subdigits, digits[:i]...)
+		subdigits = append(subdigits, digits[i+1:]...)
+		for _, p := range perm6(subdigits) {
+			result = append(result, ds+p)
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day361/problem_test.go b/day361/problem_test.go
new file mode 100644
index 0000000..5d3b450
--- /dev/null
+++ b/day361/problem_test.go
@@ -0,0 +1,100 @@
+package day361
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	guesses     []Guess
+	expectedAll []string
+	expected    bool
+}{
+	{
+		[]Guess{
+			{"175286", 2},
+			{"293416", 3},
+			{"654321", 0},
+		},
+		[]string{
+			"013486", "023486", "025416", "035416", "043216", "072416", "073456", "073496", "073516", "073816",
+			"073916", "078416", "079416", "083216", "085416", "091486", "092486", "093186", "093246", "093256",
+			"093276", "093586", "093786", "095436", "095476", "095716", "095816", "097216", "097486", "098216",
+			"103456", "103476", "103496", "123406", "123456", "123476", "123496", "183406", "183456", "183476",
+			"183496", "190436", "190456", "190476", "192406", "192436", "192456", "192476", "193046", "193056",
+			"193076", "193480", "193482", "193485", "193487", "193506", "193546", "193576", "193706", "193746",
+			"193756", "193806", "193846", "193856", "193876", "197406", "197436", "197456", "198406", "198436",
+			"198456", "198476", "201486", "203186", "203586", "203786", "203986", "205436", "205476", "205496",
+			"205716", "205816", "205916", "207486", "209486", "210486", "213086", "213586", "213786", "213986",
+			"215406", "215436", "215476", "215496", "217486", "219486", "230486", "231486", "235016", "235406",
+			"235476", "235496", "235716", "235816", "235916", "237486", "239486", "243086", "243186", "243586",
+			"243786", "243986", "245016", "245716", "245816", "245916", "270436", "270456", "270496", "270516",
+			"270816", "270916", "271406", "271436", "271456", "271496", "273046", "273056", "273096", "273106",
+			"273146", "273156", "273196", "273480", "273485", "273489", "273506", "273546", "273596", "273806",
+			"273846", "273856", "273896", "273906", "273946", "273956", "275410", "275413", "275418", "275419",
+			"278016", "278406", "278436", "278456", "278496", "278516", "278916", "279016", "279406", "279436",
+			"279456", "279516", "279816", "285016", "285406", "285436", "285476", "285496", "285716", "285916",
+			"290186", "290586", "290786", "291086", "291586", "291786", "295036", "295046", "295076", "295106",
+			"295136", "295146", "295176", "295480", "295483", "295487", "295706", "295736", "295746", "295806",
+			"295836", "295846", "295876", "297086", "297186", "297586", "305416", "325416", "370416", "372416",
+			"378416", "379416", "385416", "390216", "390486", "391486", "392486", "395016", "395406", "395476",
+			"395716", "395816", "397216", "397486", "398216", "403216", "473016", "473516", "473816", "473916",
+			"483216", "490216", "493086", "493186", "493206", "493256", "493276", "493586", "493786", "495016",
+			"495716", "495816", "497216", "498216", "503216", "503486", "513486", "523486", "543216", "570416",
+			"572416", "573016", "573406", "573496", "573816", "573916", "578416", "579416", "583216", "590216",
+			"590486", "591486", "592486", "593086", "593186", "593206", "593246", "593276", "593786", "597216",
+			"597486", "598216", "703216", "703486", "705416", "713486", "723486", "725416", "735416", "743216",
+			"783216", "785416", "790216", "790486", "791486", "792486", "793086", "793186", "793206", "793246",
+			"793256", "793586", "795016", "795406", "795436", "795816", "798216", "803216", "805416", "825416",
+			"835416", "843216", "870416", "872416", "873016", "873406", "873456", "873496", "873516", "873916",
+			"879416", "890216", "893206", "893246", "893256", "893276", "895016", "895406", "895436", "895476",
+			"895716", "897216", "903216", "903486", "905416", "913486", "923486", "925416", "935416", "943216",
+			"970416", "972416", "973016", "973406", "973456", "973516", "973816", "978416", "983216", "985416",
+		},
+		true,
+	},
+	{
+		[]Guess{
+			{"123456", 4},
+			{"345678", 4},
+			{"567890", 4},
+		},
+		nil,
+		false,
+	},
+}
+
+func TestValidMastermindGuesses(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ValidMastermindGuesses(tc.guesses); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkValidMastermindGuesses(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ValidMastermindGuesses(tc.guesses)
+		}
+	}
+}
+
+func TestValidMastermindGuessesAll(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := ValidMastermindGuessesAll(tc.guesses); !reflect.DeepEqual(result, tc.expectedAll) {
+			t.Errorf("Expected %v, got %v", tc.expectedAll, result)
+		}
+	}
+}
+
+func BenchmarkValidMastermindGuessesAll(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ValidMastermindGuessesAll(tc.guesses)
+		}
+	}
+}