mersenneforum.org Perfect shuffling puzzle (requires programming)
 Register FAQ Search Today's Posts Mark Forums Read

 2003-06-25, 11:06 #1 NickGlover     Aug 2002 Richland, WA 22·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.
 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 22×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 22·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 1000100102 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 . . .  8) lcm bug fixed [/edit]
 2003-06-27, 19:08 #10 NickGlover     Aug 2002 Richland, WA 22×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!)

 Similar Threads Thread Thread Starter Forum Replies Last Post pinhodecarlos Programming 2 2012-07-23 18:17 lorgix Miscellaneous Math 9 2010-12-08 22:22 alaa Homework Help 12 2007-06-12 22:17 Xyzzy Programming 5 2005-10-15 00:29 graeme Puzzles 7 2003-08-19 20:40

All times are UTC. The time now is 11:49.

Fri Jun 9 11:49:59 UTC 2023 up 295 days, 9:18, 0 users, load averages: 0.97, 0.89, 0.85