# Obtaining ordering of cards [closed]

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


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!

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

# 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  • You can infer from the question that the cards are placed above. See the example for five cards. – Justin Nov 17 '13 at 8:06 • @Quincunx that's right... but that might also be a source of confusion. That's why I explicitly mentioned it and gave the two possibilities. – gniourf_gniourf Nov 17 '13 at 13:57 # 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. [], 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})[] shuffleTillUnshuffled[nCards_]:= {rr=RotateRight[NestWhileList[playRound[#]&,playRound@Range@nCards,!OrderedQ[#]&]]; "Deck size: "<>ToString@nCards<>" cards; Rounds: "<>ToString@Length[rr],rr//Grid} shuffleTillUnshuffled shuffleTillUnshuffled shuffleTillUnshuffled ## 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).(mod2).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]]

• Sorry but I don't think you did. A deck with 4 cards takes 2 rounds. 1234 (1 on top) --> 4231 --> 1234. Nice try! I appreciate your effort! – Liondancer Nov 16 '13 at 11:56
• Ah, true. I only laid every other card on the table and left the others in hand. Once half the cards were on the table I put them on the bottom and started again. I will have to take a look if I can correct this. – shiona Nov 16 '13 at 16:35