4
\$\begingroup\$

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!

\$\endgroup\$

closed as off-topic by Johannes Kuhn, Doorknob, J B, manatwork, John Dvorak Nov 17 '13 at 15:33

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "General programming questions are off-topic here, but can be asked on Stack Overflow." – Doorknob, manatwork
  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Johannes Kuhn, J B
If this question can be reworded to fit the rules in the help center, please edit the question.

2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
    
\$\endgroup\$
  • \$\begingroup\$ You can infer from the question that the cards are placed above. See the example for five cards. \$\endgroup\$ – Justin Nov 17 '13 at 8:06
  • \$\begingroup\$ @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. \$\endgroup\$ – gniourf_gniourf Nov 17 '13 at 13:57
1
\$\begingroup\$

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]

shuffles

\$\endgroup\$
1
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Liondancer Nov 16 '13 at 11:56
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – shiona Nov 16 '13 at 16:35

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