Beautiful code!!!
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 jth 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