Obtaining ordering of cards [closed]

Question

You are given a deck containing n cards. While holding the deck:

1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is a round.
4. Pick up the deck from the table and repeat steps 1-3 until the deck is in the original order.

Write a program to determine how many rounds it will take to put a deck back into the original order.

I found some answers online that had answers online for comparing and I cannot get the same answers. Either they are wrong or I am completely wrong. I went through a few examples of my own got these answers:

5 cards: order: 12345

1: 24531
2: 43152
3: 35214
4: 51423
5: 12345   <-- 5 rounds

6 cards:

order: 123456

1: 462531
2: 516324
3: 341265
4: 254613
5: 635142
6: 123456   <-- 6 rounds

Answers I found online were:

Problem: http://www.velocityreviews.com/forums/t641157-solution-needed-urgent.html

Answer: http://www.velocityreviews.com/forums/t641157-p2-solution-needed-urgent.html   <-- last post

I found another solution that has the same solution as mine but not sure on any solutions credibility:

http://entrepidea.com/algorithm/algo/shuffleCards.pdf

I was wondering if anyone has done this problem before and would be able to confirm which answers are correct. I need something to test against to see if my program is giving the correct output. THANKS!

Answer 1

Python

def game(a):
    deck = range(1,a+1)
    #store the deck
    origDeck = []
    #copy the deck
    origDeck.extend(deck)
    table =[]
    ans = 0
    while 1:
        while len(deck) > 0:
            table.append(deck.pop(0))
            if len(deck) == 0:
                break
            deck.append(deck.pop(0))
        table.reverse()
        deck,table=table,deck
        ans+=1
        #this is the condition that exits the infinite loop
        if deck==origDeck:
            break
    print ans

Calling game(n) prints the number of rounds for n cards. The code can be easily changed to allow for printing the deck between rounds (add print deck before if deck==origDeck).

---

Tests (1 through 50):

1: 1
2: 2
3: 3
4: 2
5: 5
6: 6
7: 5
8: 4
9: 6
10: 6
11: 15
12: 12
13: 12
14: 30
15: 15
16: 4
17: 17
18: 18
19: 10
20: 20
21: 21
22: 14
23: 24
24: 90
25: 63
26: 26
27: 27
28: 18
29: 66
30: 12
31: 210
32: 12
33: 33
34: 90
35: 35
36: 30
37: 110
38: 120
39: 120
40: 26
41: 41
42: 42
43: 105
44: 30
45: 45
46: 30
47: 60
48: 48
49: 120
50: 50

31 produces a peculiar output; it goes through 210 rounds.

It appears that primes have large cycles. For example, 97 has the largest cycle under 100: 6435.

Answer 2

Pure Bash

It is not clear in your question (unless I missed it) if when you put a card on the table you put it above or below the cards already there. Here are two versions, and you'll see that the answer differs:

Cards above

orig="12345"
deck=$orig
table=

nb=0

play() {
    ((++nb))
    while [[ -n $deck ]]; do table=${deck:0:1}$table; deck=${deck:2}${deck:1:1}; done
    deck=$table
    table=
    echo "$nb: $deck"
}

while ((nb==0)) || [[ $deck != $orig ]]; do play; done

this yields:

1: 24531
2: 43152
3: 35214
4: 51423
5: 12345

Cards below

Replace play with:

play() {
    ((++nb))
    while [[ -n $deck ]]; do table+=${deck:0:1}; deck=${deck:2}${deck:1:1}; done
    deck=$table
    table=
    echo "$nb: $deck"
}

which yields:

1: 13542
2: 15243
3: 12345

Golfed versions, reading input on stdin

• Below:

  read o;d=$o;t=;n=0;p(){((++n));while [[ $d ]];do t+=${d:0:1};d=${d:2}${d:1:1};done;d=$t;t=;echo $d;[[ $d = $o ]]||p; };p;echo $n
  

• Above:

  read o;d=$o;t=;n=0;p(){((++n));while [[ $d ]];do t=${d:0:1}$t;d=${d:2}${d:1:1};done;d=$t;t=;echo $d;[[ $d = $o ]]||p; };p;echo $n
  

Answer 3

Mathematica

shuffleTillUnshuffled[ n] takes a deck of n cards and shuffles it until it returns to the original order.

playRound takes a deck and returns the reordered deck of cards after one round of shuffling.

rule1 places the top card on the table and the second card at the bottom of the deck.

rule2 places the last card of the deck onto the table.

[[2]], that is, Part[{inHand,onTable},2] removes the deck from the table so that it can be used, if still unordered, in the next round.

rule1={{s_,m1_,e___},{l___}}:> {{e,m1},{s,l}};
rule2={{s_},{e__}}:> {{},{s,e}};
playRound[deck_]:=({deck,{}}//.{rule1,rule2})[[2]]
shuffleTillUnshuffled[nCards_]:=  {rr=RotateRight[NestWhileList[playRound[#]&,playRound@Range@nCards,!OrderedQ[#]&]];
"Deck size: "<>ToString@nCards<>" cards; Rounds: "<>ToString@Length[rr],rr//Grid}

shuffleTillUnshuffled[4]
shuffleTillUnshuffled[5]
shuffleTillUnshuffled[13]

Answer 4

Haskell

The way of handling cards is somewhat problematic, the code for turn became rather complex. But finally both the cases for 5 and 6 match.

import Data.List
import Control.Arrow

spl :: [a] -> ([a],[a])
spl = (map snd***map snd) . partition ((==1).(`mod`2).fst) . zip [1..]

turn :: [a] -> [a]
turn' :: [a] -> [a] -> [a]
turn x = reverse $ turn' x []
turn' [] []       = []
turn' [] ls       = turn' (reverse ls) []
turn' [x] []      = [x]
turn' [x] ls      = turn' (x:(reverse ls)) []
turn' (x:y:ys) ls = x : (turn' ys (y:ls))

cardCycle x = first : (takeWhile (/=first) $ iterate turn (turn first))
  where first = [1..x]

ans = length . cardCycle

main = mapM_ (\x -> putStrLn ((show x) ++ ": " ++ (show (ans x)))) [1..20]

.

1: 1
2: 2
3: 3
4: 2
5: 5
6: 6
7: 5
8: 4
9: 6
10: 6
11: 15
12: 12
13: 12
14: 30
15: 15
16: 4
17: 17
18: 18
19: 10
20: 20

16 seems to be an interesting one so here's the cycle (layout added):

> cardCycle 16
[[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
,[16,8,12,4,14,10,6,2,15,13,11,9,7,5,3,1]
,[1,2,9,4,5,13,10,8,3,7,11,15,6,14,12,16]
,[16,8,15,4,14,7,13,2,12,6,11,3,10,5,9,1]]