Friday, June 17, 2011

Game of 24

The 24 Game is a classic game involving a deck of cards (minus the jokers). Draw 4 cards and see who comes up with an equation that makes 24, involving +, -, *, /. For instance, if you have 1, 2, 3, 4. How do you get 24? multiply it all up! 24=1x2x3x4. Another example: 4, 5, 8, 9. One solution is ((9-5)x4)+8.

Little elementary school math whiz may find it fun and challenging to compete with their friends.

Now for the computer science student: how do you solve this problem? Given 4 numbers, how do you come up with an equation? (It may not always exist, for instance if you get 4 aces)

Sure, trial-and-error works. But do you have a quicker more elegant solution?

Ask some title inflated "solution architects" of your company and they probably DON'T HAVE A CLUE. But the real CS student should.

One way is to break down the problem in smaller pieces.
Let's say the first card is 4.
If you can come up with 20 with the rest of cards you got a solution.
If you can come up with 28 with the rest of cards you got a solution.
If you can come up with 6 with the rest of cards you got a solution.
If you can come up with 96 with the rest of cards you got a solution.

Keep breaking down the problem (recursively) until you have 2 cards. Then you do trial and error. (the base case of recursion).

There is a drawback however, this approach does not solve ALL cases, such as 5, 5, 10, 10 (solution is (5x5)-(10/10))

This basic app merely draws 4 cards and show you a solution if it can find one.
There is also a custom mode for you to enter your own card values.

Enjoy this app at the Android Market here:



No comments:

Post a Comment