Grid Magic

Well, a new sum on ProjectEuler enabled me to test my meager math and Python skills. This one however wasn’t as much of a Python challenge as it was a math challenge. Let me introduce you to problem 15 of the Project Euler problem set. The problem describes the number of ways you can move across a 2 x 2 grid.

The solution turned out to be dead simple if you regard the possible movements as follows:

• A horizontal move is represented by x
• A vertical move is represented by y

Consider the first block in the above picture. The bold line can be represented as;

x x y y

using our notation.

The bold line in the second block can be represented as;

x y x y

This is but a permuation of the letters we get in the first series.

So we get that the length of any path from the starting point to the last point in a grid of order “n” is 2n units and compulsorily contains “n” horizontal moves and “n” vertical moves. Our problem is limited to dividing 2n possible moves into n horizontal and n vertical moves. The answer as known to any mathematician with brains is:

2nCn

In case of a 20 x 20 grid that becomes: “Out of 40, choose 20″. Therefore: 40C20. The required code ( I am sure there isn’t any need, but I am too lazy to find my calc and punch in the numbers):

Happy Coding