OK: I can't believe

0) yesterday's code was so Uuugly!!

1) I completely missed all sorts of beautiful things and the joy of having coded this problem (succesfully, meaning without crashing my computer or bringing down the whole LinkedIn site even though I had been careful enough to close all connections before hitting 'return')

2) Yesss! it was also correct!

Yesterday's code:

#!/usr/bin/python \

""" 'diagPaths.py' """

import sys, math

def diagN(n):

if n < 1:

print "tricks later, for now positive integer only please"

else:

return math.factorial(2*(n-1))/math.factorial(n-1)**2

def main():

if len(sys.argv) < 3:

#

print "usage: $ python diagPaths.py --n natural number"

elif sys.argv[1] == '--n':

n = int(sys.argv[2])

ans = diagN(n)

print "Number of paths between diagonal vertices for ",n, "-square lattice \

= ", ans

if __name__ == '__main__':

main()

3) If you want to exploit the beauty and power of recursion, code backwards! The number of paths to get to (i,j) is = numpaths(i-1,j) + numaths(i,j-1). Then just ask for numpaths(whatever you want) and let the code call itself ...

4) ... Modulo the bounds: while thinking about the bounds I realised that the upper bounds don't constrain anything. Which in turn means ...

5) The number of paths to the point

*(i,j)*from

*(0,0)*is just

*(i+j)C(j)*. Why? It is the

*i+j*th diagonal, and the point is the

*j*th from one end of it, so it is just the Binomial coefficient given above.

6) Which further means that we have an alternative proof of the sum of the squares of the binomial coefficients: yesterday I explained that the numpaths to get to (n,n) is the sum of the squares of the numpaths to get to points on the transvecting diagonal, which is the sum of the squares of the Binomial coefficients. Today, I've explained that the numpaths to get to (i,j) is

*(i+j)C(j)*. Hence to get to (n,n) the numpaths is

*(2n)C(n)*= (2n)!/(n!)^2 !!!! - That is exciting, not factorials.

Analytical answer:

#!/usr/bin/python

""" 'AnalyticalCountPaths.py' 1 argument -> end point (n,n)

2 arguments -> (n,m)

assume complete square Euclidean lattice

starting point = (0,0)

"""

import sys, math

def main():

if len(sys.argv) < 2:

print "usage: $ python AnalyticalCountPaths.py Natural [Natural]"

elif len(sys.argv) == 2:

n = int(sys.argv[1])

m = int(sys.argv[1])

elif len(sys.argv) ==3:

n = int(sys.argv[1])

m = int(sys.argv[2])

if (n < 0) or (m < 0):

print "EEp! Bloink! HAL No Compute, go fall into pole of Riemann Zeta. BoundError"

print "For now positive integers only please"

else:

ans = math.factorial(n+m)/(math.factorial(n)*math.factorial(m))

print "Analytical solution: Number of paths from (0,0) to (",n,', ',m,") on a\

complete Euclidean square lattice moving only in the (+,+) direction = ", ans

print "\n Oh my but this problem is beautiful!! Alternate proof of sum of squ\

ares of Binomial coefficients!"

if __name__ == '__main__':

main()

so why do I need to write the code for actually counting this?

Because, I can't believe I am saying this, it is EVEN more beautiful!

**AND FINALLY**:

#!/usr/bin/python

""" 'codeCountPaths.py Natural [Natural]'

Single argument -> (n,n)

code to count the number of paths

Assumption 1: starting at (0,0)

Assumption 2: ending at user input (n,m)

moving in (+,+) direction only, on a complete Euclidean square lattice.

"""

import sys, math

def NumPaths(n,m):

if (n < 0) or (m < 0):

print "BoundError: n >= 0 and m >= 0. Tricks later, for now positive integer only please"

elif n==0 and m==0:

numpaths = 1

elif n == 0:

numpaths = NumPaths(n, m-1)

elif m == 0:

numpaths = NumPaths(n-1,m)

else: # THE MEAT OF THE CODE

numpaths = NumPaths(n-1,m) + NumPaths(n,m-1)

return numpaths

def main():

if len(sys.argv) < 2:

print "usage: $ python codeCountPaths.py Natural [Natural]"

elif len(sys.argv) == 2:

n = int(sys.argv[1])

m = int(sys.argv[1])

elif len(sys.argv) ==3:

n = int(sys.argv[1])

m = int(sys.argv[2])

ans = NumPaths(n,m) #

**here is where I ask for the answer just once!**

print "Code counted number of paths from (0,0) to (",n,', ',m,") on a complet\

e Euclidean square lattice moving only in the (+,+) direction = ", ans

print "\n Oh my but this problem is beautiful!!"

if __name__ == '__main__':

main()

I'll confess I was nervous when I ran this: I'd already calculated the answer in my head, and was praying to Pascal that my codecounting would be right!

Did I thank _ enough for this problem?

Tomorrow: we'll relax the Euclidean requirement, then the "completeness".

By The Way: I should remind myself that any second year Numerical Path Integral Physics Grad student is probably doing this in their sleep.

## No comments:

## Post a Comment