Perfect shuffling puzzle (requires programming)

NickGlover · 2003-06-25, 11:06

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 32-bit int (most compilers/languages include a 64-bit 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.

eepiccolo · 2003-06-25, 19:35

Well, brute force doesn't work, unless I was willing to give up a week of GIMPS crunching

.

axn · 2003-06-27, 02:04

5812104600 - 1 !

Maybeso · 2003-06-27, 02:26

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. ;)

axn · 2003-06-27, 02:36

5812104600 / 56428200 = 103

NickGlover · 2003-06-27, 05:18

My answer was 5812104600 (or 5812104600 - 1 depending upon your interpretation of the problem).

NickGlover · 2003-06-27, 07:03

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.

Maybeso · 2003-06-27, 16:58

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?

Maybeso · 2003-06-27, 18:04

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]

NickGlover · 2003-06-27, 19:08

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

Maybeso · 2003-06-27, 20:37

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!)

2003-06-25, 11:06	#1
NickGlover Aug 2002 Richland, WA 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 32-bit int (most compilers/languages include a 64-bit 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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Need some help on php programming	pinhodecarlos	Programming	2	2012-07-23 18:17
New to programming. What to do?	lorgix	Miscellaneous Math	9	2010-12-08 22:22
plz, help me in c programming	alaa	Homework Help	12	2007-06-12 22:17
Programming puzzle question...	Xyzzy	Programming	5	2005-10-15 00:29
factorial puzzle (requires maths)	graeme	Puzzles	7	2003-08-19 20:40

2003-06-25, 19:35	#2
eepiccolo 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 .

2003-06-27, 02:04	#3
axn Jun 2003 43·127 Posts	5812104600 - 1 !

2003-06-27, 02:26	#4
Maybeso 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. ;)

2003-06-27, 02:36	#5
axn Jun 2003 43·127 Posts	5812104600 / 56428200 = 103

2003-06-27, 05:18	#6
NickGlover Aug 2002 Richland, WA 2²×3×11 Posts	My answer was 5812104600 (or 5812104600 - 1 depending upon your interpretation of the problem).

2003-06-27, 07:03	#7
NickGlover Aug 2002 Richland, WA 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.

2003-06-27, 16:58	#8
Maybeso 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?

2003-06-27, 18:04	#9
Maybeso Aug 2002 Portland, OR USA 100010010₂ 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]

2003-06-27, 19:08	#10
NickGlover Aug 2002 Richland, WA 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

2003-06-27, 20:37	#11
Maybeso 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!)