Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 240
Good morning! Here's your coding interview problem for today.

This problem was asked by Spotify.

There are N couples sitting in a row of length 2 * N. They are currently ordered randomly, but would like to rearrange themselves so that each couple's partners can sit side by side.

What is the minimum number of swaps necessary for this to happen?

Pull request:
Day240
Resolves #492.

Patch:
diff --git a/README.md b/README.md
index bcb745e..8bb7875 100644
--- a/README.md
+++ b/README.md
@@ -247,4 +247,5 @@ problems from
 * [Day 236](https://github.com/vaskoz/dailycodingproblem-go/issues/485)
 * [Day 237](https://github.com/vaskoz/dailycodingproblem-go/issues/487)
 * [Day 238](https://github.com/vaskoz/dailycodingproblem-go/issues/489)
+* [Day 240](https://github.com/vaskoz/dailycodingproblem-go/issues/492)
 * [Day 241](https://github.com/vaskoz/dailycodingproblem-go/issues/493)
diff --git a/day240/problem.go b/day240/problem.go
new file mode 100644
index 0000000..56451e4
--- /dev/null
+++ b/day240/problem.go
@@ -0,0 +1,46 @@
+package day240
+
+// MinSwapsAdjacentPairs returns the minimum number of swaps
+// required to bring all pairs together.
+// A pair consists of the same value.
+// Invalid input results in a panic.
+func MinSwapsAdjacentPairs(pairs []int) int {
+	if len(pairs)%2 != 0 {
+		panic("must even number of inputs")
+	}
+	indicies := make(map[int][]int, len(pairs)/2)
+	for i, id := range pairs {
+		indicies[id] = append(indicies[id], i)
+	}
+	if len(indicies) != len(pairs)/2 {
+		panic("invalid pair data")
+	}
+	for _, pos := range indicies {
+		if len(pos) != 2 {
+			panic("all values must be pairs")
+		}
+	}
+	return minSwapsAdjacentPairs(pairs, indicies, 0)
+}
+
+func minSwapsAdjacentPairs(pairs []int, indicies map[int][]int, pos int) int {
+	if pos == len(pairs) {
+		return 0
+	}
+	firstIndex := pos
+	secondIndex := pos + 1
+	first := pairs[firstIndex]
+	second := pairs[secondIndex]
+	if first == second {
+		return minSwapsAdjacentPairs(pairs, indicies, pos+2)
+	}
+	min := int(^uint(0) >> 1)
+	// NOTE: It doesn't matter which one you swap due to symmetry.
+	swapWithSecond := indicies[first][1]
+	pairs[secondIndex], pairs[swapWithSecond] = pairs[swapWithSecond], pairs[secondIndex]
+	if minBelow := 1 + minSwapsAdjacentPairs(pairs, indicies, pos+2); min > minBelow {
+		min = minBelow
+	}
+	pairs[secondIndex], pairs[swapWithSecond] = pairs[swapWithSecond], pairs[secondIndex]
+	return min
+}


Test patch:
diff --git a/day240/problem_test.go b/day240/problem_test.go
new file mode 100644
index 0000000..dd9806e
--- /dev/null
+++ b/day240/problem_test.go
@@ -0,0 +1,70 @@
+package day240
+
+import "testing"
+
+var testcases = []struct {
+	pairs    []int
+	minSwaps int
+}{
+	{[]int{0, 2, 1, 2, 0, 1}, 2},
+	{[]int{0, 3, 1, 1, 2, 2, 3, 0}, 1},
+	{[]int{0, 3, 2, 3, 0, 2}, 2},
+	{[]int{1, 2, 3, 3, 1, 2}, 1},
+	{[]int{3, 2, 3, 1, 1, 2}, 2},
+	{[]int{0, 3, 0, 2, 3, 2}, 2},
+	{[]int{0, 3, 2, 3, 0, 2}, 2},
+}
+
+func TestMinSwapsAdjacentPairs(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := make([]int, len(tc.pairs))
+		copy(copied, tc.pairs)
+		if result := MinSwapsAdjacentPairs(copied); result != tc.minSwaps {
+			t.Errorf("Expected %v, got %v", tc.minSwaps, result)
+		}
+	}
+}
+
+func TestMinSwapsAdjacentPairsNotEventInput(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected an error for odd number of pairs")
+		}
+	}()
+	pairs := []int{1, 1, 1}
+	MinSwapsAdjacentPairs(pairs)
+}
+
+func TestMinSwapsAdjacentPairsMoreThanTwoInPair(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected an error if there are more than 2 in a pair")
+		}
+	}()
+	pairs := []int{1, 1, 1, 1}
+	MinSwapsAdjacentPairs(pairs)
+}
+
+func TestMinSwapsAdjacentPairsThreeInPair(t *testing.T) {
+	t.Parallel()
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("Expected an error if there are more than 2 in a pair")
+		}
+	}()
+	pairs := []int{3, 2, 3, 3, 1, 1}
+	MinSwapsAdjacentPairs(pairs)
+}
+
+func BenchmarkMinSwapsAdjacentPairs(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := make([]int, len(tc.pairs))
+			copy(copied, tc.pairs)
+			MinSwapsAdjacentPairs(copied)
+		}
+	}
+}