This part is somewhat detached from the actual array manipulation side of the challenge, scroll down for an explanation that is much more array-based
You've been learning how to shuffle poker chips recently, but, as you're still learning, you don't always get the perfect alternating shuffle that you're aiming for. Instead, they often get grouped into pairs or triples of chips between each shuffle. Now, to make things easier, you've been practicing with 2 colors of chips, black and white, so you can see the outcome of the shuffle.
One of your recent shuffles has produced this stack of 10 chips (where the left most element of the array is the top chip):
W B W W B B B W B W
Now, you want to unshuffle these chips and get them back to being two "blocks" of colors, either of these two:
W W W W W B B B B B
B B B B B W W W W W
Unfortunately for you, the only way you like to unshuffle chips is by taking a number of chips off the top, flipping that "substack" of chips over, then adding back to the top:
W B W W B B B W B W
[W B W W]B B B W B W
W W B W B B B W B W
Here, we flipped the top 4 chips over (reversed the prefix of length 4). Indeed, it is possible to unshuffle this stack in 5 flips:
W B W W B B B W B W
[W B]W W B B B W B W
[B W W W]B B B W B W
[W W W B B B B]W B W
[B B B B W W W W]B W
[W W W W B B B B B]W
B B B B B W W W W W
In fact, a greedy approach should, in this case, always generate the fewest number of flips when only using two colors of chips.
However, what if we instead use three colors? In this case, a strictly greedy approach (i.e. the lengths of the prefixes are always increasing) doesn't work. Consider, with green chips added in,
G W G W W B B G G W B B
This can be solved in 5 flips as well:
G W G W W B B G G W B B
[G W G W W B B]G G W B B
[B B W W G W G G G W]B B
[W G G G W G]W W B B B B
[G W]G G G W W W B B B B
[W G G G G]W W W B B B B
G G G G W W W W B B B B
Once we start adding in even more colors, it gets even more complicated. For example, with 5 different colors (W
, B
, R
, G
, Y
), we might have, say:
R G B B G W B G R W W Y Y R Y
which can be done in 8 flips, in at least 2 ways, shown below:
R G B B G W B G R W W Y Y R Y R G B B G W B G R W W Y Y R Y
[R G B B G W B G R W W Y Y]R Y [R G B B G W B G R W W Y Y]R Y
[Y Y W W R G B W G B B G R R]Y [Y Y W W R G B W G B B G R R]Y
[R R G B B G W B G]R W W Y Y Y [R R G B B G W B G]R W W Y Y Y
[G B W G B B]G R R R W W Y Y Y [G B W]G B B G R R R W W Y Y Y
[B B G W]B G G R R R W W Y Y Y [W B G G B B G R R R]W W Y Y Y
[W G B B B G G R R R]W W Y Y Y [R R R G B B G G B]W W W Y Y Y
[R R R G G]B B B G W W W Y Y Y [B G G]B B G R R R W W W Y Y Y
[G G R R R B B B]G W W W Y Y Y [G G B B B]G R R R W W W Y Y Y
B B B R R R G G G W W W Y Y Y B B B G G G R R R W W W Y Y Y
Alternatively, in more array manipulation based terms: given a list of integers, we can rearrange it by repeatedly reversing prefixes of given lengths ("flips"). For example,
[3, 2, 3, 1, 1, 2] -> [2, 3, 3, 1, 1, 2] -> [1, 1, 3, 3, 2, 2] -> [3, 3, 1, 1, 2, 2] -> [2, 2, 1, 1, 3, 3] -> [1, 1, 2, 2, 3, 3]
Here, we sorted the list by reversing the prefixes of lengths \$2\$, \$5\$, \$4\$, \$6\$ and then \$4\$. In this case, 5 flips is the minimum number possible to sort this list in ascending order.
In this challenge, we don't require the final list to be sorted into ascending order. Instead, we simply want the list to be sorted so that equal elements are all adjacent to one another, in any order. For example, the previous example can be shortened to 2 flips:
[3, 2, 3, 1, 1, 2] -> [2, 3, 3, 1, 1, 2] -> [1, 1, 3, 3, 2, 2]
Your task is to, given a list of digits representing a chip stack, output the minimum number of flips required to arrange the list into a series of blocks of identical digits.
For example, we could represent our 5 color example above as
[1,2,3,3,2,4,3,2,1,4,4,5,5,1,5]
or even as the integer 123324321445515
. You may assume that the input does not contain more than 9 distinct digits (so all will be from 123456789
), and that the numbers of each digit are equal. You may take input in any reasonable manner or format.
This is a code-golf so the shortest code in bytes wins!
Test cases
array -> output
[1,2] -> 0
[1,2,1,2] -> 2
[2,1,1,2] -> 1
[3,1,2,1,2,3] -> 3
[3,2,3,1,1,2] -> 2
[3,3,1,1,2,2,4,4] -> 0
[1,2,1,1,2,2,2,1,2,1] -> 5
[2,3,2,3,3,1,1,2,2,3,1,1] -> 5
[3,1,3,1,1,2,2,3,3,1,2,2] -> 5
[1,2,3,3,2,4,3,2,1,4,4,5,5,1,5] -> 8*
[2,5,1,1,5,3,1,5,2,3,3,4,4,2,4] -> 8*
[5,5,1,3,4,1,3,4,5,5,3,3,2,3,4,2,2,1,5,1,2,4,4,1,2] -> 15*
*
: These are currently only an upper bound, and aren't proven to be the minimal number (just suspected). If you can get a lower value, please provide the list of flips to verify that value