Unshuffle my poker chips

Question

_{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}

Answer 1

Python3, 186 bytes:

import itertools as I
def f(a):
 q=[(a,0)]
 while q:
  j,c=q.pop(0)
  if len(set(t:=[u for u,_ in I.groupby(j)]))==len(t):return c
  for i in range(2,len(j)):q+=[(j[:i][::-1]+j[i:],c+1)]

Try it online!

The code above is a basic brute-force approach. However, the solution below, while longer, uses dynamic programming to produce results for all the test cases in about six seconds:

Python3, 542 bytes

import itertools as I
E=enumerate
P=lambda a:[(j,[*k])for j,k in I.groupby(a)]
L=lambda a:[u for u,_ in P(a)]
V=lambda r:len(set(t:=L(r)))==len(t)
def f(a):
 q,s,R,H=[(a,0)],[a],[],[len(L(a))]
 while q:
  j,c=q.pop(0)
  if V(j):R+=[c];continue
  for x,(_,A)in E(r:=P(j)):
   for y,(_,B)in E(r):
    if x<y and A[-1]==B[0]:
     J=j[:(i:=sum(len(k[1])for k in r[:x])+len(A))][::-1]+j[i:]
     if(O:=J[:(Y:=i+sum(len(k[1])for k in r[x+1:y]))][::-1]+J[Y:])not in s:
      if(M:=len(L(O)))<=min(H):q+=[(O,c+1+(J!=j))];s+=[O];H+=[M]
 return min(R)

Try it online!

Answer 2

Charcoal, 50 bytes

⊞υ⟦⁰Ｓ⟧Ｆυ¿¬ⅉ«≔⊟ιθ¿⊙θ⁻✂θ⌕θκλ¹κＦＬθ⊞υ⟦⊕Σι⁺⮌…θ⊕κ✂θ⊕κ⟧Ｉι

Try it online! Link is to verbose version of code. Takes input as a string of characters. Explanation: Uses brute force, in particular it always tries flipping one character, which is pointless.

⊞υ⟦⁰Ｓ⟧Ｆυ

Start a breadth-first search with 0 flips and the initial input.

¿¬ⅉ«

Stop when a solution has been found.

≔⊟ιθ

Remove the current string from the search term, leaving the flip count.

¿⊙θ⁻✂θ⌕θκλ¹κ

If there is a character that exists in a disjoint range, then...

ＦＬθ⊞υ⟦⊕Σι⁺⮌…θ⊕κ✂θ⊕κ⟧

... reverse each nontrival prefix of the string and push the result to the search list with an incremented flip count, otherwise...

Ｉι

... output the flip count as a string.

99-byte faster version based on @Ajax1234's second version, assuming it's correct (it only flips nontrivial proper prefixes), can easily deal with the second longest test case on TIO:

≔Ｌθη⊞υ⟦⁰θ⟧Ｆυ¿¬ⅉ«≔⊟ιθ≔ΦＬθ∧κ⁻§θκ§θ⊖κζ¿¬›Ｌζη«≔Ｌζη≔Φζ∨⁼§θκ§θ⁰‹κ⌈⌕Ａθ§θ⊖κζ¿ζＦ⁻Ｅζ⁺⮌…θκ✂θκＬθ¹Ｅυ§κ¹⊞υ⊞Ｏ⊕ικＩι

Try it online! Link is to verbose version of code. Works with both strings and lists. Explanation:

≔Ｌθη

Keep track of the minimum number of runs found so far.

⊞υ⟦⁰θ⟧Ｆυ

Start a breadth-first search with 0 flips and the initial input.

¿¬ⅉ«

Stop when a solution has been found.

≔⊟ιθ

Remove the current string from the search term, leaving the flip count.

≔ΦＬθ∧κ⁻§θκ§θ⊖κζ

Get the list of indices of starts of new runs (excluding the first run).

¿¬›Ｌζη«

If this does not exceed the minimum number of runs found so far:

≔Ｌζη

Update the minimum number of runs in case this entry has fewer.

≔Φζ∨⁼§θκ§θ⁰‹κ⌈⌕Ａθ§θ⊖κζ

Keep only those runs which are potentially worth reversing, of which there are two sorts: either the first element is the same as that of the run, or the previous run is not the last run of its element.

¿ζ

If there are any such runs, then:

Ｆ⁻Ｅζ⁺⮌…θκ✂θκＬθ¹Ｅυ§κ¹

For each run, compute the result of flipping up to that run, but then delete any results seen previously.

⊞υ⊞Ｏ⊕ικ

Push the new run with the incremented flip count to the search list.

Ｉι

If there were no such runs, this can only happen when there are no disjoint runs of an element, which means that we've found a solution, so output its flip count.

Answer 3

JavaScript (ES6),  124  109 bytes

Expects a string. Performs a breadth-first search.

f=(s,n=N=0,r)=>!/(.)(?!\1).+\1/.test(s)|[...s].some((c,i)=>n&&f((r=c+[r])+s.slice(i+1),n-1))?N:n==N&&f(s,++N)

Try it online!

Commented

f = (                   // f is a recursive function taking:
  s,                    //   s = input string
  n =                   //   n = remaining number of iterations
  N = 0,                //   N = total number of iterations
  r                     //   r = reversed prefix, initially undefined
) =>                    //
  !/(.)(?!\1).+\1/      // success if there isn't any character appearing
  .test(s) |            // twice with some other characters in between
  [...s].some((c, i) => // for each character c at position i in s:
    n && f(             //   unless n = 0, do a recursive call:
      (r = c + [r]) +   //     update the reversed prefix
      s.slice(i + 1),   //     append the non-reversed suffix
      n - 1             //     decrement n
    )                   //   end of recursive call
  ) ?                   // end of some(); if truthy:
    N                   //   we've found a solution: return N
  :                     // else:
    n == N              //   if it was the root call of the attempt with
    &&                  //   N iterations:
      f(s, ++N)         //     increment N and try again

Answer 4

C(GCC) 218 210 203 bytes?

-8 bytes thanks to @ceilingcat, -7 bytes thanks to myself

f(int*x){int*c,*y=x,o=0,h,i,p=0;while(*y){for(c=y;*y==*++c;);while(*y-*++c&&*c);if(*c){if(y-x)for(c=y,p++;*y==*++c;);for(i=0;i+x<c;x[i++]=*--c,*c=h)h=i[y=x];o++;}else for(c=y;*c==*++y;);}return o-p+p%2;}

Try it online

This code is based on idea of creating a machine, that always does the right shuffle, or at least after finishing can decide, how it is improvable. For some strange reason, it works. The most effective way to unshuffle the poker chips would be to link two pieces (at one place) of the same value every round, without breaking any. However, this is not always possible (the 10th and 11th test case). When the machine runs into a such situation, where nothing can be linked, it will do a sneaky shuffle that brings a linkable block of numbers on the top. The fact that this machine runs only on one path means it can choose the wrong one, and do more (still less than types of numbers) sneaky shuffles, but the right amount of normal shuffles. My theory is, that every deck can be unshuffled with at most one sneaky shuffle, because every two of these are basically a shift, that can be created by rearranging the previous shuffles. That is, why the output is o-p+p%1, where o is the total amount of shuffles and p the amount of sneaky shuffles. But, sadly, I don't have the mathematical tools needed to prove this last theory, so I would be really grateful, if someone could find a counterexample, or correct my naive maths.

Answer 5

Python, 157 bytes

def f(x):
    X=[x,0];n=len(x);m=n//max(x);r=range(1,n)
    while X:
        x,c,*X=X
        if all(x[j]==x[j//m*m]for j in r):return c
        for i in r:X+=[x[i::-1]+x[i+1:],c+1]

Attempt This Online!

Note: it is extremely inefficient, but it eventually terminates correctly.