mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2003-06-25, 11:06   #1
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22·3·11 Posts
Default 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.
NickGlover is offline   Reply With Quote
Old 2003-06-25, 19:35   #2
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

37010 Posts
Default

Well, brute force doesn't work, unless I was willing to give up a week of GIMPS crunching .
eepiccolo is offline   Reply With Quote
Old 2003-06-27, 02:04   #3
axn
 
axn's Avatar
 
Jun 2003

7×709 Posts
Default

5812104600 - 1 !
axn is offline   Reply With Quote
Old 2003-06-27, 02:26   #4
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

1000100102 Posts
Default

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. ;)
Maybeso is offline   Reply With Quote
Old 2003-06-27, 02:36   #5
axn
 
axn's Avatar
 
Jun 2003

7×709 Posts
Default

5812104600 / 56428200 = 103
axn is offline   Reply With Quote
Old 2003-06-27, 05:18   #6
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22×3×11 Posts
Default

My answer was 5812104600 (or 5812104600 - 1 depending upon your interpretation of the problem).
NickGlover is offline   Reply With Quote
Old 2003-06-27, 07:03   #7
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

2048 Posts
Default

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.
NickGlover is offline   Reply With Quote
Old 2003-06-27, 16:58   #8
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

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 is offline   Reply With Quote
Old 2003-06-27, 18:04   #9
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2·137 Posts
Default

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]
Maybeso is offline   Reply With Quote
Old 2003-06-27, 19:08   #10
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22×3×11 Posts
Default

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
NickGlover is offline   Reply With Quote
Old 2003-06-27, 20:37   #11
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

2×137 Posts
Default

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!)
Maybeso is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:35.

Fri May 14 08:35:42 UTC 2021 up 36 days, 3:16, 0 users, load averages: 2.45, 2.61, 2.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.