Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 292
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

A teacher must divide a class of students into two teams to play dodgeball. Unfortunately, not all the kids get along, and several refuse to be put on the same team as that of their enemies.

Given an adjacency list of students and their enemies, write an algorithm that finds a satisfactory pair of teams, or returns False if none exists.

For example, given the following enemy graph you should return the teams `{0, 1, 4, 5}` and `{2, 3}`.
```
students = {
    0: [3],
    1: [2],
    2: [1, 4],
    3: [0, 4, 5],
    4: [2, 3],
    5: [3]
}
```
On the other hand, given the input below, you should return False.
```
students = {
    0: [3],
    1: [2],
    2: [1, 3, 4],
    3: [0, 2, 4, 5],
    4: [2, 3],
    5: [3]
}
```

Pull request:
Day292
Resolves #598.

Patch:
diff --git a/README.md b/README.md
index 5cacecd..f97243d 100644
--- a/README.md
+++ b/README.md
@@ -302,6 +302,7 @@ problems from
 * [Day 288](https://github.com/vaskoz/dailycodingproblem-go/issues/590)
 * [Day 290](https://github.com/vaskoz/dailycodingproblem-go/issues/594)
 * [Day 291](https://github.com/vaskoz/dailycodingproblem-go/issues/596)
+* [Day 292](https://github.com/vaskoz/dailycodingproblem-go/issues/598)
 * [Day 294](https://github.com/vaskoz/dailycodingproblem-go/issues/600)
 * [Day 295](https://github.com/vaskoz/dailycodingproblem-go/issues/601)
 * [Day 296](https://github.com/vaskoz/dailycodingproblem-go/issues/605)
diff --git a/day292/problem.go b/day292/problem.go
new file mode 100644
index 0000000..62aa7df
--- /dev/null
+++ b/day292/problem.go
@@ -0,0 +1,68 @@
+package day292
+
+import (
+	"errors"
+	"sort"
+)
+
+var errTeamNotPossible = errors.New("building a team without enemies is impossible")
+
+// ErrTeamNotPossible returns the error when a team isn't possible.
+func ErrTeamNotPossible() error {
+	return errTeamNotPossible
+}
+
+// AssignTeams attempts to assign teammates using a constraint of enemies.
+// It uses Breadth-First-Search to accomplish this.
+func AssignTeams(enemies map[int]map[int]struct{}) ([]int, []int, error) {
+	team1 := make(map[int]bool)
+	team2 := make(map[int]bool)
+	var q []int
+	for id := range enemies {
+		team1[id] = true
+		for e := range enemies[id] {
+			q = append(q, e)
+		}
+		break
+	}
+	for len(q) != 0 {
+		var nextQ []int
+		var countNew int
+		for _, id := range q {
+			if _, found := team1[id]; found {
+				return nil, nil, errTeamNotPossible
+			}
+			if _, found := team2[id]; !found {
+				team2[id] = true
+				countNew++
+				for enemy := range enemies[id] {
+					nextQ = append(nextQ, enemy)
+				}
+			}
+		}
+		if countNew > 0 {
+			q = nextQ
+		} else if countNew == 0 {
+			q = nil
+		}
+		team1, team2 = team2, team1
+	}
+	return buildResult(team1, team2)
+}
+
+func buildResult(team1, team2 map[int]bool) ([]int, []int, error) {
+	result1 := make([]int, 0, len(team1))
+	for id := range team1 {
+		result1 = append(result1, id)
+	}
+	result2 := make([]int, 0, len(team2))
+	for id := range team2 {
+		result2 = append(result2, id)
+	}
+	sort.Slice(result1, func(i, j int) bool { return result1[i] < result1[j] })
+	sort.Slice(result2, func(i, j int) bool { return result2[i] < result2[j] })
+	if result1[0] < result2[0] {
+		return result1, result2, nil
+	}
+	return result2, result1, nil
+}


Test patch:
diff --git a/day292/problem_test.go b/day292/problem_test.go
new file mode 100644
index 0000000..abc3e37
--- /dev/null
+++ b/day292/problem_test.go
@@ -0,0 +1,94 @@
+package day292
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	enemies          map[int]map[int]struct{}
+	teamOne, teamTwo []int
+	err              error
+}{
+	{
+		map[int]map[int]struct{}{
+			0: {3: struct{}{}},
+			1: {2: struct{}{}},
+			2: {
+				1: struct{}{},
+				4: struct{}{},
+			},
+			3: {
+				0: struct{}{},
+				4: struct{}{},
+				5: struct{}{},
+			},
+			4: {
+				2: struct{}{},
+				3: struct{}{},
+			},
+			5: {3: struct{}{}},
+		},
+		[]int{0, 1, 4, 5},
+		[]int{2, 3},
+		nil,
+	},
+	{
+		map[int]map[int]struct{}{
+			0: {3: struct{}{}},
+			1: {2: struct{}{}},
+			2: {
+				1: struct{}{},
+				4: struct{}{},
+			},
+			3: {
+				0: struct{}{},
+				2: struct{}{},
+				4: struct{}{},
+				5: struct{}{},
+			},
+			4: {
+				2: struct{}{},
+				3: struct{}{},
+			},
+			5: {3: struct{}{}},
+		},
+		nil,
+		nil,
+		ErrTeamNotPossible(),
+	},
+	{
+		map[int]map[int]struct{}{
+			1: {0: struct{}{}},
+			0: {
+				1: struct{}{},
+				2: struct{}{},
+				3: struct{}{},
+			},
+			2: {0: struct{}{}},
+			3: {0: struct{}{}},
+		},
+		[]int{0},
+		[]int{1, 2, 3},
+		nil,
+	},
+}
+
+func TestAssignTeams(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if t1, t2, err := AssignTeams(tc.enemies); !reflect.DeepEqual(t1, tc.teamOne) ||
+			!reflect.DeepEqual(t2, tc.teamTwo) || err != tc.err {
+			t.Errorf("Expected (%v,%v,%v), got (%v,%v,%v)", tc.teamOne, tc.teamTwo, tc.err, t1, t2, err)
+		}
+	}
+}
+
+func BenchmarkAssignTeams(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			AssignTeams(tc.enemies) // nolint
+		}
+	}
+}