25 September 2010

A Free game in Java

I wanted to play this game so badly as I use to be very good at it. I was not knowing the proper keyword to find it online. So, what the heck, I went ahead and created one! The front end used was Swing.
The objective of this game is to arrange from numbers 1 through 24 (or depending on the size) in proper order and you have one square free. You can move to that empty sqaure by pressing either of the four arrow keys UP/DOWN/LEFT/RIGHT. All the puzzles formed will have a solution. You can use this code anywhere you want.

If you have Java installed in your browser, you should be able to see the Applet. Just click anywhere inside the applet and start playing using the arrow keys! Have fun!

Screenshot Applet


10 September 2010

Trie data structure - In C++

Having had a comprehensive coverage of the TRIE data structure in Java, me and my roommate thought it would achieve completion if we have the same implemented in C++. Don't get carried away by the length of the code. Its as simple and easy as the equivalent one in Java. You may go through the comprehensive tutorial here. Trust me, it takes only 10 minutes!!.

Please feel free to ask any questions if you face difficulties in understanding any part of the resource. I would respond to you immediately.

Demonstration of trie operations


09 September 2010

Efficient way to calculate prime numbers

In several puzzles/coding competitions we may need to check for prime numbers and this is required to be done in considerable time to save precious run time. The traditional approach is,

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be

Final prime number program in Ruby (bonus)

This approach will check for factors in very minimized number of loops.


08 September 2010

Stack Implementation in C++ through an array

Stack is one of the important data structures that every computer programmer should be aware of. It follows the simple LIFO (Last In First Out) principle. Implementation of stack can be done in many ways. One of the simplest way is using Arrays. Here an array is initialized to a maximum value first, lets call it capacity. As and when we push elements onto the array, its size will get increased. When the size reaches the capacity, we should ideally double the array size. But in the code given below I am not doing that.



In his book, 7 Habits of Highly Effective People, Stephen Covey tells the story of a woodcutter who took a new job for a timber merchant. The woodcutter was determined to do his best, so when the employer presented him with an axe he went straight to work. The first day the woodcutter brought 18 trees to the boss. “Congratulations,” the boss said. “Keep it up!” With this motivational encouragement the cutter went out the next day with even more determination. However, at the end of the day he could only bring back 15 trees. The third day he worked harder still, yet try as he might only 10 trees could be felled. So it went; each succeeding day yielded fewer trees. “I must be losing my strength,” the woodcutter thought. He decided to approach his boss to apologize for his unexplained deteriorating output. “When was the last time you sharpened your axe?” the boss asked. The woodcutter stared dumbfounded. “Sharpen my axe! I had no time to sharpen my axe. I have been too busy trying to cut trees!”

It is possible to be too busy to maintain your effectiveness. Whatever your personal situation, this might be the right time to ask yourself if it is time to “sharpen your axe.”