Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 290
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

On a mysterious island there are creatures known as Quxes which come in three colors: red, green, and blue. One power of the Qux is that if two of them are standing next to each other, they can transform into a single creature of the third color.

Given `N` Quxes standing in a line, determine the smallest number of them remaining after any possible sequence of such transformations.

For example, given the input `['R', 'G', 'B', 'G', 'B']`, it is possible to end up with a single Qux through the following steps:
```
        Arrangement       |   Change
----------------------------------------
['R', 'G', 'B', 'G', 'B'] | (R, G) -> B
['B', 'B', 'G', 'B']      | (B, G) -> R
['B', 'R', 'B']           | (R, B) -> G
['B', 'G']                | (B, G) -> R
['R']                     |
```

Pull request:
Day290
Resolves #594.

Patch:
diff --git a/README.md b/README.md
index f20815b..d8ba37f 100644
--- a/README.md
+++ b/README.md
@@ -299,3 +299,4 @@ problems from
 * [Day 286](https://github.com/vaskoz/dailycodingproblem-go/issues/585)
 * [Day 287](https://github.com/vaskoz/dailycodingproblem-go/issues/587)
 * [Day 288](https://github.com/vaskoz/dailycodingproblem-go/issues/590)
+* [Day 290](https://github.com/vaskoz/dailycodingproblem-go/issues/594)
diff --git a/day290/problem.go b/day290/problem.go
new file mode 100644
index 0000000..edf3695
--- /dev/null
+++ b/day290/problem.go
@@ -0,0 +1,33 @@
+package day290
+
+// MinimizeQux returns the smallest Qux slice
+// possible.
+// Runs in O(N*K) where K is the number of elements that can removed.
+// Uses O(N) extra space to avoid modifying the input.
+func MinimizeQux(input []rune) []rune {
+	copied := make([]rune, len(input))
+	copy(copied, input)
+	var lastLen int
+	for len(copied) != lastLen {
+		lastLen = len(copied)
+		copied = minimizeQux(copied)
+	}
+	return copied
+}
+
+func minimizeQux(input []rune) []rune {
+	min := input
+	for i := 1; i < len(input); i++ {
+		if input[i] != input[i-1] {
+			missing := 'R' + 'G' + 'B' - input[i] - input[i-1]
+			end := append([]rune{missing}, input[i+1:]...)
+			candidate := append([]rune{}, input[:i-1]...)
+			candidate = append(candidate, end...)
+			candidate = minimizeQux(candidate)
+			if len(candidate) < len(min) {
+				min = candidate
+			}
+		}
+	}
+	return min
+}


Test patch:
diff --git a/day290/problem_test.go b/day290/problem_test.go
new file mode 100644
index 0000000..5ca9826
--- /dev/null
+++ b/day290/problem_test.go
@@ -0,0 +1,33 @@
+package day290
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input    []rune
+	expected []rune
+}{
+	{[]rune{'R', 'G', 'B', 'G', 'B'}, []rune{'R'}},
+	{[]rune{'G', 'B', 'G', 'B'}, []rune{'B', 'B'}},
+	{[]rune{'B', 'B', 'B', 'R', 'G', 'G', 'G'}, []rune{'G', 'G'}},
+}
+
+func TestMinimizeQux(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinimizeQux(tc.input); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMinimizeQux(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinimizeQux(tc.input)
+		}
+	}
+}