Saturday, August 13, 2011

simplifying the boundary conditions

Last night and this morning when I woke up I was thinking of the extension to higher dimensions. One thought was that the number of elif conditions with special case sums for the points on the boundary would grow as 2**D -1, all the "lower" edges, faces, vertices etc. Even if I wrote python code to
  1. take in the dimension as an argument and
  2. have it write python code for the dimension required (which I'll do in a minute)
this would be quite tedious.
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):

""" ' 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                                             
    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
    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 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__':

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