8
\$\begingroup\$

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 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

\$\endgroup\$
1
  • \$\begingroup\$ Sandbox. No sample Jelly program to beat for brownie points this time, I'm afraid \$\endgroup\$ May 7 at 1:06

4 Answers 4

3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ You can shave off one byte by doing {*(...)} instead of set(...) \$\endgroup\$
    – Steffan
    May 7 at 1:36
  • 1
    \$\begingroup\$ Your brute force version can be slowed down even more by removing the 2,. \$\endgroup\$
    – Neil
    May 7 at 10:35
2
\$\begingroup\$

Charcoal, 50 bytes

⊞υ⟦⁰S⟧Fυ¿¬ⅉ«≔⊟ιθ¿⊙θ⁻✂θ⌕θκλ¹κFLθ⊞υ⟦⊕Σι⁺⮌…θ⊕κ✂θ⊕κ⟧Iι

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.

⊞υ⟦⁰S⟧Fυ

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...

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

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

Iι

... 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:

≔Lθη⊞υ⟦⁰θ⟧Fυ¿¬ⅉ«≔⊟ιθ≔ΦLθ∧κ⁻§θκ§θ⊖κζ¿¬›Lζη«≔Lζη≔Φζ∨⁼§θκ§θ⁰‹κ⌈⌕Aθ§θ⊖κζ¿ζF⁻Eζ⁺⮌…θκ✂θκLθ¹Eυ§κ¹⊞υ⊞O⊕ικIι

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

≔Lθη

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

⊞υ⟦⁰θ⟧Fυ

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.

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

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

¿¬›Lζη«

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

≔Lζη

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

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

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:

F⁻Eζ⁺⮌…θκ✂θκLθ¹Eυ§κ¹

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

⊞υ⊞O⊕ικ

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

Iι

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.

\$\endgroup\$
1
  • \$\begingroup\$ I can save two bytes by flipping proper prefixes instead of nontrivial prefixes but I don't know whether the problem can always be solved without reversing the entire string, nor can I find a counterexample. \$\endgroup\$
    – Neil
    May 7 at 10:29
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.