CODEWITHSUNDEEP
pythonalgorithmshuffle
Arale
Arale

Reputation: 39

The Nearly Perfect Shuffle

To nearly-perfectly shuffle a deck of n cards using offset k, perform the following steps:

For example:
n = 11, k = 3 with starting deck from the bottom: 3 7 9 A 2 8 J K 6 4 Q
First we place Q, then 4, then 6 on pile P.
Then we split the remaining cards into bottom half: 3 7 9 A and top half: 2 8 J K.
The bottom card of B is then 3 which we place on P followed by the bottom card of T which is 2 Repeating the previous step, we end up with the shuffled deck: Q 4 6 3 2 7 8 9 J A K.
Your task is to write a program which, for given values n and k, outputs how many nearly-perfect shuffles are needed to return a perfectly sorted deck back to its original state.

Example Input 1

6  
0

Example Output 1
4
Example Input 2

11  
3

Example Output 2
10

Constraints

I have puzzled for ages on this problem but I keep running into problems!
How am I supposed to solve this?

My code in progress:

def shuffle(n, k):
  global shuffledA, shuffledB, shuffledZ, cards
  if 0 <= k <= n <= 1000000 and (n-k) % 2 == 0:
    cards = []
    shuffled = [None]
    shuffledA = []
    shuffledB = []
    shuffledZ = []
    num = 1
    for i in range(1, n+1):
      cards.append(i)
    shuffledZ = cards[n-1-k:n-1]
    shuffledA = cards[0:(n-k)/2-1]
    shuffledB = cards[(n-k)/2:n-k-2]

it always outputs this error when I run it where n - k is even:

>>> shuffle(11, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "main.py", line 256, in shuffle
    shuffledA = cards[0:(n-k)/2-1]
TypeError: slice indices must be integers or None or have an __index__ method

Upvotes: 1

Views: 310

Answers (1)

Hari5000
Hari5000

Reputation: 401

There are two ways of answering this question - the second is more efficient as it's faster, and this is why it scores full marks for the Perse Coding Challenge.

The first (less efficient) way

is to create a virtual deck, then virtually shuffle it. This works, but with larger values of n (e.g. 1,000,000) this can be slow, hence leading to a timeout when submitting it as an answer. My code is as follows:

#Accept inputs
n = int(input())
k = int(input())
it = 1

#Apply the Nearly Perfect Shuffle
def shuffle(string):
        P = []
        global n,k
        
    if k!=0:
    #Remove the bottom k cards, place them on top
    #last goes to first, second last --> second, nth last --> nth
        for i in range(k):
            P.append(string[-i-1])
            i += 1
        string = string[:-k]

    #Now for the "perfect" part of the nearly perfect shuffle
        
    #Split deck into two
    l = len(string)//2

    B = string[:l]
    T = string[l:]
    #Add the top card from each pile onto P one by one
    for i in range(l):
        P.append(B[i])
        P.append(T[i])
    return P

#Create a deck of cards
#We do this by creating an array containing numbers from 1 to n
first = list(range(n))
#print(first)
P = shuffle(first)

#We repeatedly shuffle until we get back to where we started
while P != first:
    P = shuffle(P)
    it += 1
print(it)

The more efficient, less time-consuming way

is to find the mathematical pattern that lies behind each card shuffle.

  • For every shuffle, the last card always becomes the first card, the second last always becomes the second... the nth last always becomes the nth.

  • The rest of the deck is split into two.

    • Let's pretend k = 0 for simplicity, and the deck is: A B C D E F G H
    • A is in position 0, B is in position 1, etc.
    • Splitting it into two gives A,B,C,D and E,F,G,H
    • Perfect shuffle gives A E B F C G D H
    • Take notice of the positions of A, B, C, D. Before, they were in positions 0, 1, 2 and 3 of the deck respectively. Now, they are in positions 0, 2, 4, 6. All you've done is multiply their position in the deck by two.
    • Now lets look at E, F, G, H. They were in positions 4, 5, 6, 7 respectively but now they're in positions 1, 3, 5, 7.
      1. First we subtract the size of the first half of the deck from each position (e.g. 4-4 = 0)
      2. Then we multiply this by two like we did before (0*2=0)
      3. Finally we add (0+1=1) since the card has to come after the previous card, not replace it. E was in position 4, but now it's in position 1

  • What you might notice when you follow the path of a single element in the array (a single card in the deck) is that it may loop through the same positions, e.g. a card that is found at position 2, then 4, then 5, then 0, then back to 2.

  • Each card has their own "loop" sequence. Imagine a deck where card X at position 1 goes to 2, then 3 then 1 again, and card Y at position 4 goes to 5,6,7, then 4 again. After 3 cycles, card A returns to its starting point. After 4 cycles, card Y returns to its starting point. Therefore, for both cards to return to their starting point at the same time, we need 12 shuffles. This is because 12 is the lowest common multiple of 3 and 4.

  • Essentially, you will need to find the lowest common multiple of the length of all the "loops" of all cards.

The code can be found here, but I've copied and pasted it below anyway.

"""
12) NEARLY PERFECT SHUFFLE - ALL MARKS
"""

from math import gcd
from functools import reduce

n, k = int(input()), int(input())
sizeHalf = (n - k) // 2

nums = set(range(n))
cycles = []

# example shuffle mapping
# n = 11 k = 3
# 0  1  2  3  4  5  6  7  8  9  10
# AFTER ONE SHUFFLE GOES TO....
# 10 9  8  0  4  1  5  2  6  3  7

def findCycle(i):
  # a different way of thinking 
  # ... can I track the card at index i as it moves around until it gets back to index i?
  #... how many moves does it take (its cycle length)?

  x = i
  count = 0 

  while True:
    
    count += 1

    if x >= n - k:
      x = n - x - 1
    elif x < sizeHalf:
      x = k + x * 2
    else:
      x = k + 1 + (x - sizeHalf) * 2

    if x == i:
      return count

    nums.remove(x)


while len(nums) > 0:
    cycles.append(findCycle(nums.pop()))

lcm = cycles[0]
for i in range(1, len(cycles)):
  lcm = (lcm * cycles[i]) // gcd(lcm, cycles[i])

print(lcm)

# or do 
# print(reduce(lambda a,b : a * b // gcd(a, b), cycles))

Upvotes: 1

Related Questions