Saturday, July 30, 2005

 

How many perfect shuffles are needed to return to original order?

I've been intrigued by this problem ever since I read about it over at NexTag.com. I didn't quite know how to program it at first sight because I wasn't sure what data structure to use to represent the stack of unique cards. Of course I also didn't know the "trick" to calculate the result quickly. Finally I went with an array and decided to just program it the brute force way to understand the problem better. I could have scribbled with pen and paper to see how the perfect shuffle works, but it was just too manual and error-prone if I didn't keep track. I made my program display all the iterations and ran it through several small cases. I also went ahead and ran the ultimate case of 1002 unique cards at the 101st cut and saw that my program just kept running and running.

Seeing the perfect shuffle work on smaller cases was very helpful. I admit I didn't see what was going at first, but I remember now that one of the strategies with problem solving is to see if there is some kind of pattern. I suppose the harder part is actually figuring out a way to make use of it.

The pattern that I was led to notice was that each unique card will always come back to its original position in the same amount of passes, of course not all of them at the same time otherwise the problem would be very easy to solve.(I suppose.)

So after finding out the passes for each unique card, the problem just boiled down to finding a combination of cycles of each unique card's passes so that all of the cards come back together at the same time, in other words the lowest common multiple(LCM) of all the passes is the number of perfect shuffles needed to return the deck back to its original order.

I didn't know how to find the LCM of a set of numbers let alone just two numbers! I mean I knew how for two small numbers just by knowing some of the multiples and also the easy method was to just multiply the numbers but that won't necessarily find the lowest even though it is a common multiple. After some research, I realized one way to express it algorithmically was to take one of the numbers, multiply it through consecutive numbers starting with 2, but check if the result is a multiple of the other number. If so, then that's the LCM. If not, then multiply the first number with the next consecutive number and check the result again until the LCM is found. But there's some "beginning stuff" to check before doing this: if the two numbers are the same, then the LCM is that number and second if the two numbers are multiples of each other, then the LCM is the larger number.

When I coded this strategy, I found out for the part where I have to multiply the consecutive numbers and do the check, I didn't know whether to operate it on the smaller or larger number. I just said I'll work on the smaller number without any reason. Later on I realized I should have operated on the larger number. This resulted in a performance increase because with the smaller number, I would need to go through several multiplications to eventually find a LCM that is a multiple of the larger number. This would be very bad if the two numbers are very far apart. With the larger number, I realized I wouldn't have to go through as many multiplications to eventually find a LCM that is a multiple of the smaller number. Cool!

Actually there's a longer explanation of why I went this route. Before I noticed the difference, I decided to research further on other ways to calculate the LCD and hopped on to Euclid's Algorithm. I scanned over it and quickly implemented into my program and noticed how big of an improvement it made! I made my program display what the calculations were doing at each step of the way and realized it calculated the LCM much quicker. When I was doing my original LCM strategy, I was wondering why it took a while for some numbers and very quickly for others. It finally dawned on me that I was always calculating the LCM from the smaller number and when the difference is very large, that's what took so long.

Whew! So I made the change and was impressed that it performed the same as using Euclid's Algorithm. Neato! I implemented Euclid's using recursion whereas my implementation was just loops.

Btw, I implemented my solution in C++(actually it's just C, I didn't use any of the fancy C++ stuff) because I haven't played with Java for a while.




#include <iostream>
#include <time.h>

using namespace std;

long long shuffles(int nSize, int nCut);
long long findLowestCommonMultiple(int *arrayNumbers, int nSize);

int main(void)
{
int i = 4;
int j = 2;
long long l;
clock_t c_cpubefore, c_cpuafter;

cout << "Deck size: ";
cin >> i;
cout << "Deck cut: ";
cin >> j;

c_cpubefore = clock();
l = shuffles(i, j);
c_cpuafter = clock();

cout << "cpu time spent calculating: " << (double) (c_cpuafter - c_cpubefore) / CLOCKS_PER_SEC << " seconds" << endl;
cout << "perfect shuffles needed for a set of (size " << i << " and a cut at " << j << ") is: " << l << endl;

return 0;
}

long long shuffles(int nSize, int nCut)
{
// simple check for now
if (nCut > nSize) {
cout << "ERROR: can't do shuffle because cut is larger than size of deck" << endl;
return 0;
}

// v2 strategy
// still have originalDeck array, but only do perfect shuffle until each
// element goes back to it's original position
// note: this is not the case where all elements need to be back at the
// same time(because this would just be back to brute force method)
// rather, just record the # of iterations needed for each element to come
// back to its original position individually.
// After that the problem just boils down to finding the unique combination
// for all the iterations such that all the elements come back to their
// original position, in other words, need to find the lowest common
// multiple of the iterations.
// another note: with this strategy, not able to show deck order for all
// iterations, only up to the maximum iterations for an element to come back
// to its original position

int i, j, nTopdeckCount, nBottomdeckCount;
long long lShuffles = 0;
bool bOrdered = false;
bool bNeedToShuffleAgain;
int nBottomdeckSize = nSize - nCut;
int *originalDeck = new int[nSize];
int *keeptrackpositionsDeck = new int[nSize];
int *topDeck = new int[nCut];
int *bottomDeck = new int[nBottomdeckSize];

// initialize the originalDeck and keeptrackpositionsDeck
for (i = 0; i < nSize; i++) {
originalDeck[i] = i;
keeptrackpositionsDeck[i] = 0;
}

while (!bOrdered) {

// get top deck of nCut numbers
for (i = 0; i < nCut; i++) {
topDeck[i] = originalDeck[i];
}

// get bottom deck of nSize - nCut numbers
for (i = nCut; i < nSize; i++) {
bottomDeck[i - nCut] = originalDeck[i];
}

nTopdeckCount = nCut - 1;
nBottomdeckCount = nBottomdeckSize - 1;
for (i = 0, j = nSize - 1; j >= 0; j--, i++) {
if ((i % 2) != 0) {
if (nBottomdeckCount >= 0) {
originalDeck[j] = bottomDeck[nBottomdeckCount];
nBottomdeckCount--;
} else {
for (; j >= 0; j--) {
originalDeck[j] = topDeck[nTopdeckCount];
nTopdeckCount--;
}
break;
}
} else {
if (nTopdeckCount >= 0) {
originalDeck[j] = topDeck[nTopdeckCount];
nTopdeckCount--;
} else {
for (; j >= 0; j--) {
originalDeck[j] = bottomDeck[nBottomdeckCount];
nBottomdeckCount--;
}
break;
}
}
}

// increment shuffles count
lShuffles++;

// just did one perfect shuffle, now analyze each element and see if
// it has come back to its original position

bNeedToShuffleAgain = false;

for (i = 0; i < nSize; i++) {
if (keeptrackpositionsDeck[i] == 0) {
if (originalDeck[i] == i) {
keeptrackpositionsDeck[i] = lShuffles;
} else {
bNeedToShuffleAgain = true;
}
}
}

if (!bNeedToShuffleAgain) {
bOrdered = true;
}
}

// don't need these anymore
delete []topDeck;
delete []bottomDeck;
delete []originalDeck;

lShuffles = findLowestCommonMultiple(keeptrackpositionsDeck, nSize);

delete []keeptrackpositionsDeck;

return lShuffles;
}

long long findLowestCommonMultiple(int *arrayNumbers, int nSize)
{
long long lLCM = arrayNumbers[0];
long long smaller, larger;

for (int j = 1; j < nSize; j++) {
if (lLCM == (long long) arrayNumbers[j]) {
continue;
} else {
if (lLCM < (long long) arrayNumbers[j]) {
smaller = lLCM;
larger = (long long) arrayNumbers[j];
} else {
smaller = (long long) arrayNumbers[j];
larger = lLCM;
}
}

lLCM = larger;
for (int k = 2; (lLCM % smaller) != 0; k++) {
lLCM = larger * k;
}

/* This is where I figured out operating on the larger number resulted
in a performance increase.
The above code is a cleaned up version of below.

if ((larger % smaller) == 0) {
lLCM = larger;
} else {
for (int k = 2; ; k++) {
// lLCM = smaller * k;
lLCM = larger * k;
// if ((lLCM % larger) == 0) {
if ((lLCM % smaller) == 0) {
break;
}
}
}
*/

}

return lLCM;
}

Monday, July 04, 2005

 

DSC01683


DSC01683, originally uploaded by hehemmm.

Ethan making faces to me! How?! hehe


 

DSC01682


DSC01682, originally uploaded by hehemmm.

Another snap of Brandon.


 

DSC01681


DSC01681, originally uploaded by hehemmm.

Trying to snap Brandon, but he saw it coming!


 

DSC01680


DSC01680, originally uploaded by hehemmm.

Back in car and taking pic of Ethan's messy hair after wearing the cap! hehe


 

DSC01679


DSC01679, originally uploaded by hehemmm.

Whoops, heading back now. Didn't even walk much of the bridge. hehe


 

DSC01678


DSC01678, originally uploaded by hehemmm.

Still at the entrance... and look at the crowd!


 

DSC01676


DSC01676, originally uploaded by hehemmm.

Having to look up to Ethan


 

DSC01675


DSC01675, originally uploaded by hehemmm.

Walking on GG Bridge #2, notice the signboard in the background, haven't made much distance. hehe


 

DSC01674


DSC01674, originally uploaded by hehemmm.

Walking on GG Bridge


 

DSC01673


DSC01673, originally uploaded by hehemmm.

Surprising Ethan! Also we're on way to Golden Gate Bridge.


Sunday, July 03, 2005

 

DSC01672


DSC01672, originally uploaded by hehemmm.

Ethan camera shy, but moments later got in trouble for something I forgot.


 

DSC01671


DSC01671, originally uploaded by hehemmm.

Never seen this before: spam and rice(and soy sauce in between) wrapped in seaweed. Chris told me this is Hawaiian.


Friday, July 01, 2005

 

For reference, baby pigeon weeks ago


DSC01645, originally uploaded by hehemmm.

software cropped and zoomed shot #2


 

For reference, baby pigeon weeks ago


DSC01644, originally uploaded by hehemmm.

software cropped and zoomed, shot #1


 

Progress of Baby Pigeon


DSC01670, originally uploaded by hehemmm.

Might be hard to see b/c the baby pigeon stays behind that pillar. But can see that it's quite developed now, gray colored feathers, developed tail and wing feathers.


 

Eggs!


DSC01667, originally uploaded by hehemmm.

Just found out the mommy pigeon laid two new eggs! The original baby pigeon is quite developed now.


This page is powered by Blogger. Isn't yours?