Gururaj’s Rumination

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

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