This is a problem posted in a job site. 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. Your function should be declared as: static long shuffles(int nCards,int iCut); What is the result for shuffles(1002,101).I am unable to find the result for shuffles(1002, 101). It runs for hours. Can anyone tell the algorithm to solve this problem. Any help is appreciated. Thanks, Arun
When copying questions such as this from other sites, please give a link to the original site. In this case, your question comes from here. Also if I could please direct you to the guidelines for this forum. Questions such as this are very valid for discussion, but the purpose of this forum is not for people to solve other people's problems for them. Perhaps a good way to proceed in this instance is to start by giving some ideas how you might solve this problem.
Interesting definition of "perfect shuffle." As a magician (among other things...), I find this definition to be a little bit odd, in that a true perfect shuffle involves iCut = nCards / 2 and the nproceeding as described. Anyway, I'll give this a little bit of thought and see what interesting approach I can come up with. Maybe I'll even apply for a job....
Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.
And, just as an aside, I hate you all (in that loving sort of hate way....) I really should be asleep by now, but this is such a fascinating problem that it has captured my mind and I can't sleep. I wrote an optimized brute force algorithm. Initial results with lower values detetected no pattern that my feeble, half-asleep mind could discern, so I'm going to let my computer puzzle it out overnight. I've pegged the machine at 100% processing power and I'm letting it go. Not sure if I'll get an answer, but I'm babbling 'cause I'm tired...
i wrote a poker game (c++) in a programming class a few years ago (pre-OO days... not efficient or pretty). i had 3 different shuffling algorithms and one of them does the above mentioned 1-card-alternating method. hmmm, maybe i can rewrite it in java and figure this out. of course, i suppose i should apply for that job if i do!
Originally posted by RArun Kumar: What is the result for shuffles(1002,101).I am unable to find the result for shuffles(1002, 101). It runs for hours. Can anyone tell the algorithm to solve this problem. Any help is appreciated. Thanks, Arun
I wrote a small set of classes.. and got the answer as 66. I got the answer within ~10 seconds.. Can anybody confirm the correctness of this answer? I will post the code after I find time to confirm it myself. (I tried a few other combinations.. 66 is the max answer I get..) P.S. : I did not use any fancy algorithm - just brute force. -GB. [ June 19, 2003: Message edited by: Gopi Balaji ]
Joel, I was also a magician of sorts in a past life. I wrote a solution with a perfect faro shuffle in mind, even testing it with 8 perfect faro shuffles (which would leave the deck in the same order). Except I realized only a few moments ago that this algorithm dictates that you should drop the first card from the top portion of the deck, not the original bottom. Doh! Easy to fix, but it looks like the real answer is somewhat higher...
Joined: Jan 23, 2003
Did not find time to confirm the validity of the results.. but, anyway, here is my code. Card.java
The answer I got was 5,812,104,600 shuffles and was arrived at in 18.957 seconds. I'll post my code after I clean it up a bit (many different trials...) Gopi, I'm not sure what you did wrong, but We get different results for a 6-card deck with a cut of 3: Mine:
Your top and bottom cards never change; you are dropping the bottom card from the bottom stack first (as opposed to the bottom card from the top stack) Anyway, I'll clean up my code and post it an my reasoning....
Here we go: After runnnig a brute force method, I discovered that that was by no means the most efficient way to solve the problem. After spending some time thinking about it (instead of sleeping), I realized that every card would eventually return to its starting position, although not necessarily at the same time. (Of couse, it is having them return to their starting position all at the same time is the solution that we are looking for.) Also, if a card returns to its starting place after x shuffles, it will return to that location every x shuffles. (Basically, each card cycles through certain positions in the deck.) Each card could have a different period; all that we have to do is find the period for each card and then find the smallest number is a multiple of all the periods (The Least Common Multiple, or LCM, of the periods). BTW, does anybody know a good manner of finding the LCM of a set of numbers? I wrote my own, but I'm sure that there are better ways of doing it. Finding the LCM seems to be where most of my processing time is being eaten up.
Joined: Jul 27, 2001
To find the GCD you can use the Euclidean algorithm. Since we're talking computer speak, the binary Euclidean algorithm is probably a good choice. It will be much faster than finding prime factors.
Hi, I am getting the shuffle count value as 1517137304.
Now comes the hard part- explanation :-) I used the same method as Joel at the top-level - First find the unique shuffle counts for each card position - then calulcate the LCM. The difference is in the first step (which i got after a lot of scribbling). Instead of actually performing a shuffle once and then looping through each position, i just calculate the next step(or position) a given card would be in after a shuffle. For example, if we number the positions as 1 through 1002, starting with the bottom-most position as 1 and the top-most as 1002, then the card at position 1 will move to position 2 after the first shuffle, and it will move to position 4 after the second shuffle, 8th after 3rd shufle, and so forth. This will continue till it reaches the 128th position after 7th round of shuffling and then it will not be shuffled anymore because only lower 101 cards shuffle. Then it just keeps moving up by 101 cards each round till it is within the top-most 101 cards. Then it becomes a part of the top-deck in the next cut and goes down again. This continues till the card at position 1 gets back to postion 1 again. The number of shuffles are counted and put in a Vector named unique. I mark all those positions in an array because those cards that are in those positions will follow the same pattern. For exmaple, the cards at position 1,2,4,8,...128, (128+101), (128+101+101)...etc all follow the same pattern. They all have the same periodic cycle. So no need to count their shuffle counts again. After the "for" loop is over once, the position 2 is already marked with -1 and so the loop just continues with pos++. Then it works with the position 3 and marks 6,12,24... and adds their shuffle count into the Vector. Then is repeats it for all those that are not marked (5,10,... then 7,14...), until it marks them all. Then in the second step we just find the LCM of all the numbers in the unique Vector. One interesting problem that i faced earlier was that if the number of cardsToCut is greater then totalCards/2, then it was crashing. After manually going through the steps for pairs like 7 and 5 i found that if you cut 5 out of 7 and then shuffle, the top 3 cards remain at the same position each time. It was identical to 4 and 2. Similarly, 10,7 is same as 6,3, and so forth. So i added a small check
Note that I get the same unique shuffle counts as Joel does (235,230,206,50,232,40,9) but the LCM comes out to be 1517137304. May be I made a mistake implementing Euclid's algorithm.
You have to have made some mistake, because 1517137304 is not a multiple of any of the shuffle counts. However, I implemented Euclid's algorithm the same as you did and reaffirmed my previous answer of 5812104600, so the problem is not in there. (This time my program ran in 80 milliseconds, a considerable improvement over the previous time...somehow, I never learned of Euclid's algorithm until this little puzzle). I'm not sure where the problem is; a cursory glance does not show any problems. I'll take a closer look.
Actually, I've got the answer. Use longs instead of ints. The answer I got is greater than ints can hold, so when you use ints you run into problems when calcualting the LCM. Changing your ints to longs resulted in the same answer I got.
Joined: May 18, 2001
Silly Me! The answer 5812104600 is correct and is a 33 bit value. I should have used long for LCM/GCD. This now works. And it returns almost immediately.
[oh! after hitting submit i saw that you beat me by 3 minutes :-)] [ June 21, 2003: Message edited by: Jignesh Malavia ]
Joined: Jan 23, 2003
Originally posted by Joel McNary:
<snipped /> Gopi, I'm not sure what you did wrong, but We get different results for a 6-card deck with a cut of 3: <snipped /> Your top and bottom cards never change; you are dropping the bottom card from the bottom stack first (as opposed to the bottom card from the top stack)
Ahh.. I see. This is something that should be pretty easy to change in the code.. Perhaps, after the change, you can use this code to confirm the working of your solution. The approach of your solution is noble. I have read your explanation.. yet to read the code. -GB.
Found this looking for another shuffle problem and was intrigued. I know this was a long time ago, but if anyone is interested in a somewhat different approach, here's what I did. The biggest difference is in the simpler gcd method, using Euclid's algorithm:
I need people who solved this problem to verify my answer.
I've used double type to store my lcm value which came out to be 5.8121046E9 the funny thing is the E9 part, is this suppose to be some double type thing? or is my answer really to the 10^9 power? Any Suggestion/Correction is appreciated.
Yes its a double precision thing. The format you have is scientific notation. The number after E specifies the power of 10 to multiply by to get the answer.
5.8121046E9 means multiply this number by 10 ^ 9 Or in other words, move the decimal point 9 places to the right which gives 5812104600 - the answer mentioned above. [ May 31, 2006: Message edited by: Stefan Evans ]
Joined: Feb 23, 2004
I read my prevous thread again, I LAUGHED @ myself so hard. As you can see, the thread was posted 3AM in the morning which i solved the problem just couple mins before the post. Apprently i was not thinking right 3 in the morning, i had thought i was reading the whole number without any dicimal, then i looked again earlier, i went DOH~~~~~~ ROFL