- take in the dimension as an argument and
- have it write python code for the dimension required (which I'll do in a minute)

Then I realised that the recursive self-calls stop when they encounter a value, so I can just set boundary conditions for "parent nodes" on the enveloping lower hyper-planes (of which there are only D) to be 0.

Here is the somewhat more "biutiful" code (I rented it, but ended up watching Terminator 3 instead):

#!/usr/bin/python

""" 'codeCountPaths1.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.

CHANGE from codeCountPaths.py:

A branch of the recursion will stop when it encounters a value, so

BCs can be accounted for by putting in lines of

0s at n= -1 and m = -1 as opposed to

restricting the sum for boundary points to just those parent nodes

which lie within the domain. There is no need for the 0-valued

parent nodes to go back to the n+m = 0 line (or soon2B hyperplane)

"""

import sys, math

def NumPaths(i,j,n,m):

if i==0 and j==0:

numpaths = 1 # BC at origin

elif ((i==-1) and j in range(1,m+1)) or ((j==-1) and i in range(1,n+1)):

numpaths = 0 # BCs at enveloping lower lines

else:

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

return numpaths

def main():

# reads command line arguments for the location of the ending point

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

# scolds user for trying to trick poor little machine

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

print "BoundError: n >= 0 and m >= 0. Tricks later, for now positive intege\

r only please"

# asks for answer, and sits back for an awfully long time

ans = NumPaths(n,m,n,m)

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

if __name__ == '__main__':

main()

Question: I have a recursion relation for the number of time-steps needed, but can't solve it analytically, neither can I correctly code to just count each time a call is made.

Can one of you CS gods help put better bounds on "awfully long time"?

## No comments:

## Post a Comment