Gururaj’s Rumination

Rumination – The word says it all…

Solution to Robot Problem

leave a comment »

As I’ve described in my previous post that the first puzzle is more kinda directed graph traversing problem, indeed I tried that approach to solve the problem.

Well, I should admit that I’m not a genius to have figured the method at the first glance but I’ve spent enough time trying few brute force methods to arrive at the solution. After trying few methods to solve the problem I stumbled on this approach which actually solved the problem.

2 x 2 Matrix Example

2 x 2 Matrix Example

4 x 3 Matrix Example

4 x 3 Matrix Example

I approached the problem using the Dynamic Programming methodology. The method is not very complex neither it uses any Permutation and Combinations to compute the different ways of reaching the target node. Say, you’ve 3 x 3 matrix and you number each cell from left-to-right and the goal is reach from Cell 1 (1,1) to Cell 9 (3, 3) (read robot problem on problem statement). You can see that there are only 6 ways to reach Cell numbered 9. Now expanding the same to 4 x 3 matrix’s you can see that there are only 10 different ways to reach the target node. See demonstration diagrams for better understanding.

Isn’t that easy to program too: definitely. But there’s one caveat here. For small sized matrix it’s easy to compute and save the result in Integer data type but when the size of matrix increase there are chances of Integer overflow – I confide to hit this problem too. I tried using other data types but everything in vein. That’s it I hit this block and stopped exploring other ways to overcome this problem, may be I was very much satisfied to have solved the problem than taking it to the completion putting myself into waiting more for the next up coming puzzle 😉
Advertisements

Written by Gururaj

June 6, 2008 at 7:51 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: