Monday, December 26, 2011

Card and Deck - Deal and Shuffle

There are a lot of websites showing how do you write code for the classes Card and Deck implementing two key operations - deal and shuffle. And almost all of them have an O(N) solution for shuffling the cards (N = 52, the number of cards). (For example, http://math.hws.edu/javanotes/c5/s4.html and awesome discussion at http://www.codinghorror.com/blog/2007/12/shuffling.html, or just search on Google for "card deck deal shuffle code" or even "card deck deal shuffle code optimized")

Recently, somebody asked me - if there's a better solution.

Now let me just generalize this problem - we have a collection of N items which need to dealed and shuffled. The order in which the items are dealed should not be predictable (that's what randomness means, right?). Think... can we do it in O(1) with minimal memory? I did it!

For the sake of simplicity, let's number the cards 1-52 and define the interface for the IDeck as follows:

interface IDeck
{
    void Shuffle();          //Shuffles so that the "fresh" deal can start
    int Deal();              //Gives me the next card
    int Remaining { get; }   //Returns the number of cards remaining in the deck
}

Now, let's look at the following solution...

We need to have an array that will hold these cards, in this case - an array of int - int[] cards.

Then we need an index/count indicating how many cards have been dealt or remaining - int index.

Now, dealing is simple - start picking up the items from the start / end and update value of index appropriately. For example, we can initially have index = cards.length - 1 and decrement it each time deal is done.

But the problem is that during shuffle, we need to randomly put all the cards in the array cards. Now, to randomize and shuffle, we'll need another temporary array so that we can start picking up the cards randomly and place them across.

Well, almost all of the solutions that Google gave me do the same.

Let's approach is slightly differently... focus on what we need.

The sum-total of shuffle + deal is to start giving out the cards in random order... an order which is not predictable.

Let's first try to minimize the memory... can we do the shuffling using just one array?

How about just resetting the index back to its default value indicating that all the cards are in deck and shuffled.

Ouch! But we never really did shuffling. Hmmm... that's the real trick.

Ok... so, now what? How do we deal? Because dealing from the order will give me the same cards -- very predictable.

Think once again...

Can we just pick up a random index and deal the card at that index?

Now, that's getting interesting... but the problem is where do we keep these indices?

Ok... there are only 52 cards, just use an int which lower 52-bits as flags to check which cards at which indices have already been dealt.

Looks great, or... errr... wait! How do I check which indices have been used? I need to start looking at the bits once again. Now, that's O(N) once again.

Not looking good. :(

Can we just pick up a random number between 0 to number-of-cards-remaining and deal that card? Let's call it the deal index

Looks better... but the problem is what do we do with this deal index? If we can somehow move the card at this index to somewhere on one side, we can somehow get to an O(1) solution.

And you yell, "Ouch! What did you just say? Not sure if I understood this part. Or have I?". If you have... Hurray! You have the solution.

Here are the stepwise details:

Structure:
  1. An array to keep the cards.
  2. An index to indicate the number of cards in the deck (initial value as cards.length)
Shuffle:
  1. Set index <-- cards.length
Deal:
  1. Pick a random number between 0 (inclusive) to index (exclusive). We call it deal index.
  2. Swap the cards at the "deal index" and "index - 1".
  3. Decrement index by 1
  4. The card at the "deal index" is the card dealt.
No loops. All fixed time operations... total cost O(1). Only one array and one integer.

Great. And the code is for the sake of completeness (written in C#).

class Deck : IDeck
{
  private int[] cards = new int[52];
  private int index;

  public Deck() {
    for(int i = 0; i < cards.Length; i++) {
      cards[i] = i + 1;
    }
    Shuffle();
  }

  public int Remaining {
    get { return index; }
  }

  public void Shuffle() {
     index = cards.Length;
  }

  public int Deal() {
     if(Remaining > 0)
     {
       //Get the random card
       int dealIndex = new Random().Next(index);
       int card = cards[dealIndex];

       //Now swap
       int tmp = cards[dealIndex];
       cards[dealIndex] = cards[index - 1];
       cards[index - 1] = tmp;

       //Update the "end point" => cards remaining / dealt
       index--;

       //Deal
       return card;
     }
     throw new InvalidOperationException();
  }
}

Enjoy!

Tuesday, October 4, 2011

HTML5 and Social Games

On 1st October was jsFoo by HasGeek, and I had a talk on "Effective Gaming techniques using HTML5: Single-player, multi-player and Social Games". Here are the slides...

Sunday, July 3, 2011

July with 5 weekends once in 823yrs - Know the truth

For last few days, I have been getting spam about the awesomeness and rarity of July with 5 weekends... something that is being claimed to happen once in 823 yrs. It's all bullshit. Search on Google for "823 years July five weekends" something around it, and you'll see great results. Once such URL is http://www.google.com/search?q=823+years+july+five+weekends. Even Times of India (the Toilet Paper of India) write this in their article here.

I happen to be a mathematician at heart. Reading these news, I got reminded of a calendar that I given to my father by an MR when I was in VIIth standard - that's about 18-19yrs ago. The calendar was of some 150+ years. I was excited to get such a calendar. And then observing it closely and using some maths - though very trivial now - I realized the Gregorian Calendar repeats itself every 28yrs.

This is how... if there were no leap years, each year would have been for 365 days, that means, the calendar will advance by 1 day a week every year (365 mod 7 = 1), and hence will repeat every 7 yrs.
Because every 4th year is a leap year, the reptition happens every LCM(4, 7) = 28yrs.

And in may be around 15-20minutes, I created a infinitely-usable calendar.

Ok. I admit, I have not taken into account 100yr factor... but it can be taken up.

Coming back to this 823yrs crap, and to verify my stats, I just went to TimeAndDate.com and this is what I got: http://www.timeanddate.com/calendar/?year=1983 as the calendar of 1983!(2011 - 28 = 1983).

Check it out closely... the month of July. What does it read -- 5 weekends.

And so goes the calendars of 2011 +/- 28*n where n can be any number. Let's just checkout the calendar of 2011 - 28 * 10 = 1973. Visit this: http://www.timeanddate.com/calendar/?year=1731 and you'll know the truth.

Thanks for being enlightened! Yet another reason why I hate media... these uneducated people write news that impacts the masses. IMHO, these newspapers and media houses should be banned... donno about any criminal cases of misinformation or anything can be put against them!

Wednesday, March 30, 2011

Android

I have always wanted to a start a series on Android, noting that I have now spent over 3yrs working on Android, mainly at the application level (what you touch and play with on the device) and at times at the middleware level (drivers and codecs, that runs without your knowledge in the background).

So, I finally I have a go... as and when I get time, I will be writing articles on various application development aspects relating to Android. And no, I am definitely not planning to write another "Hello World" tutorial. You can search on Google for several such tutorials on the web.

I will be writing the stuff on the aspects "Beyond Hello World".