20030625, 11:06  #1 
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
Perfect shuffling puzzle (requires programming)
Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order.
Give the answer for nCards = 1002, iCut = 101. You will need to write a program to solve this. Ideally the solution should be calculated by a function that works for any values of nCards and iCut (as long as the answer does not overflow your data types). It would probably be declared something like: long long shuffles( int nCards, int iCut ); Note that the answer for shuffles( 1002, 101 ) is between 2^32 and 2^33, so you will need to use a data type larger than the standard 32bit int (most compilers/languages include a 64bit integer type). Try to write your program so that it calculates the answer within a few seconds. No assembly language/hardware optimization should be required to do this. I wrote my solution in Java and it runs instantly on my 1GHz Tbird. Feel free to post a numerical answer as soon as you get it, since it won't really ruin the problem for everyone else. Please wait a day or two before describing the algorithm your solution uses to give others a chance to come up with it. Original source of problem: a job posting. Feel free to try applying for the job if you are interested, but they never replied to me when I applied 4 months ago. 
20030625, 19:35  #2 
Dec 2002
Frederick County, MD
2·5·37 Posts 
Well, brute force doesn't work, unless I was willing to give up a week of GIMPS crunching .

20030627, 02:04  #3 
Jun 2003
43·127 Posts 
5812104600  1 !

20030627, 02:26  #4 
Aug 2002
Portland, OR USA
2·137 Posts 
Hmm,
I get 56428200. Your answer is within the range NickGlover gave and mine isn't. I'll show you my algorithm if you show me yours. ;) 
20030627, 02:36  #5 
Jun 2003
43·127 Posts 
5812104600 / 56428200 = 103

20030627, 05:18  #6 
Aug 2002
Richland, WA
2^{2}×3×11 Posts 
My answer was 5812104600 (or 5812104600  1 depending upon your interpretation of the problem).

20030627, 07:03  #7 
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
I'll shed some light on what I think the problem with Maybeso's implementation is. I'll give a bit away about how to solve the problem, but hopefully not too much.
Assuming you're solving the problem similar to how I am, you calculate an LCM (least common multiple) to get the final answer. I put some extra print's in my code and found that I was calculating LCM( 230, 206, 235, 9, 232, 50, 40 ). Since 206 = 2*103, it is likely that you are missing the 206 when you calculate your LCM. 
20030627, 16:58  #8 
Aug 2002
Portland, OR USA
2·137 Posts 
Yes, that's what it was! :D I now get 5812104600.
I was worried about time, and an early version was collecting 1002 "numbers", so I sorted them to remove duplicates. I guess my sort was clobbering all 206's for some reason. Later, faster versions avoided duplicates another way, but I forgot to remove the sort! My algorithm does a single pass (1002) for setup, a single pass (1002) to solve it, then the lcm tests primes against each "number" (7*64). O(2N)  How does that compare with the rest of y'all? 
20030627, 18:04  #9 
Aug 2002
Portland, OR USA
100010010_{2} Posts 
shuffles(1002, 240) = 110676004422984
shuffles(1002, 255) = 415879067400720 shuffles(1002, 334) = 22452171121806840000 ( or am I still doing this wrong? ) ops: I'm getting strange answers when iCut > nCards/2 . . . [edit] 8) lcm bug fixed [/edit] 
20030627, 19:08  #10 
Aug 2002
Richland, WA
2^{2}×3×11 Posts 
shuffles( 1002, 240 ): 110676004422984
shuffles( 1002, 255 ): 415879067400720 Your results look right, except the answer for shuffles( 1002, 334 ) is greater than 2^64, which my program can't handle. I haven't had any problems when iCut > nCards/2. shuffles( 1002, 501 ): 232 shuffles( 1002, 502 ): 60 shuffles( 1002, 637 ): 56 shuffles( 1002, 804 ): 44 
20030627, 20:37  #11 
Aug 2002
Portland, OR USA
2×137 Posts 
Yes, I was surprised by the answer to 334.
My app shuffle.html, is an HTML form with javascript for the math. I guess it has a big enough integer type for 2^64. When iCut > nCards/2, some of the high prime factors were above my lcm sieve bounds and got skipped. Answers came back < 10, some = 1. Now it modifies the list, and I go until it's all 1's. (Had to move my debug prints above where lcm destroys the list!) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Need some help on php programming  pinhodecarlos  Programming  2  20120723 18:17 
New to programming. What to do?  lorgix  Miscellaneous Math  9  20101208 22:22 
plz, help me in c programming  alaa  Homework Help  12  20070612 22:17 
Programming puzzle question...  Xyzzy  Programming  5  20051015 00:29 
factorial puzzle (requires maths)  graeme  Puzzles  7  20030819 20:40 