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.

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):

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP

def factorial(n):
        if n == 0 or n == 1:
                return 1
        else:
                return n * factorial(n – 1)

def no_of_paths(order):
        return (factorial(order * 2)) / (factorial(order)) ** 2

print no_of_paths(20)

Happy Coding :)

About this entry

You’re currently reading “Grid Magic,” an entry on Shriphani Palakodety

Published:
03.24.08 / 6am
Category:
Mathematics, python