I found this interesting question, any idea? Thanks.
Define a shuffle of a deck of cards as follows: take the top card of the deck and put it on the bottom. Take the next top card and set it on the table. Take the next top card and put in on the bottom of the original deck. Take the next top card and set it on top of the card on the table. Continue in this way until all of the cards are in the deck on the table.
Given a deck with n cards, write a Java program to determine the minimum number of shuffles it takes to return the deck to its original order. The program should accept the number of cards in the deck as an argument and return the result on system.out. You may use any data structures you like but try to minimize the amount of looping.
Provide answers for -1, 0, 1, 2, 10, 33, 51, 9999 cards.
One of the problems with making improvements is you don't REALLY know where your program is slowing down. you can spend hours re-factoring the part you THINK slows it down, only to get a minor improvement.
One of the best places to start is to figure out what is taking so long... is it the shuffling or the checking the order?
there are various tools you can use, or even some java classes that may help. i'd start by analyzing what my program is actually doing first.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
note that with some analysis, you can also figure out a pretty fast way to do the shuffle (i think...).
I believe it is possible to build each new shuffle fairly easily and efficiently, without going through the whole process of moving stuff around. i think you can pretty much simply remove the proper card from one linked list, and insert it into the other in the correct spot...
I'll leave it to you to think about how to do that.
Joined: Jun 03, 2008
This is the one i am using. If there is any improvement? Thanks,
Why use recursion if a simple loop will suffice? Remember, for recursion, you have a fresh set of variables for each call. That could lead to a java.lang.StackOverflowError even though there is no infinite loop if the nesting goes too deep.
2) This will fail if there is an odd number of cards on the stack. Check You have to check inside the loop as well:
You don't have to check inside the loop. The first line in the loop removes the top card from the deck and puts in at the bottom, so when you're down to one card the deck remains unchanged.
I would look at how you're checking that the order of the deck has returned to the starting position. It's possible that the order has returned to normal but you're missing it by a bad order checking method that works for smaller lists. Would you post that method?
You're both absolutely right of course. I just saw two removes after each other and thought that it was waiting for an error to occur. Of course I forgot all about the first removed element being reinserted again.
it might just also be that the number of shuffles grows exponentially... i'm not sure how to calculate it. it just might take a long time. you could put in a counter and print out something every thousand or ten thousand loops and see what's going on that way as well.
also, i don't think you need to really do all that deleting and inserting... here is a look at what happens:
Note that on the line with the star, we have basically removed every other element from the original list. if you start at the 'front' of the original list, you add the elements to the 'back' of the new list.
Then, our original list had 02468. as we go through, we AGAIN add every other element to the front of the new list (the 2, then the 6).
So, if you have a way to remove an element from the middle of the list, you can iterate across the original list, removing every other one, and add them to the front of the new list.
then, YOU CAN DO THAT AGAIN and again, until the original list is empty.
this saves you teh time of moving all those elements from the front to the back.
i don't KNOW that this will speed anything up, but it might...that's why you need to analyze WHERE things are slowing down.
Joined: Jun 03, 2008
fred, That is what I am experiencing now. If that is 10k cards, each shuffle logic cost 15-300ms each.
I also get the similar idea this morning before read yours. Now I will implement them, hope that works.