Maze - All Valid Paths

Maze-AllValidPaths

# PROBLEM:  Count and Construct All Distinct Valid Paths Through a Maze

# TRICK0:  
# - mutable heap-allocated structure to accumulate results to
# - cross-recursion-level visibility
# - use TUPLE to group MUTABLE ELEMENTs for state accumulation
# - globalValidPathCounter as first item of mutable LIST
# - used as INDEX into globalValidPaths Dict
def findAllPaths(point, maze, MAX_DIM, buildOnePath, buildAllPaths):
    
    row, col = point
    # print ('ENTER:  ({},{})'.format(row,col))
    
    # TRICK 1: HACK SPECIAL CASE:  Initialize ORIGIN point so as not have to 
    #                              pre-init
    if ( (row == 0) and (col == 0) ):
        if (maze[row][col] == 1):
            buildOnePath.append((row,col))
    
    if ( (row == (MAX_DIM -1) ) and (col == (MAX_DIM - 1)) ):
        
        if (maze[row][col] == 1):
            # print('DEEPEST:  True')
            # TRICK 2:  - cut DISTINCT path HERE at LEAF of branch but ONLY IFF
            #           incoming buildOnePath is VALID ALL THROUGH TO LEAF!
            #           - in the case where any ONE point of incoming path invalid, 
            #           we ignore adding ENTIRE path entry
            if buildOnePath:
                buildAllPaths[0][0] = buildAllPaths[0][0] + 1 
                # TRICK 3:  - at THIS point, DISTINCT FULL path found, so add it,
                #           assuming PREPENDing path  prior to recursion!
                #           - MUST PREPEND since on backtrack, we LOSE DIFFERENTIATION
                #           between branches at the higher FORKING POINT!
                # TRICK 4:  buildPath is GLOBAL HEAP var which needs to get popped
                #           on function return to simulate backtracking trials;
                #           SO, need to capture FULL COPY of it here at LEAF level 
                #           to buildAllPaths
                buildAllPaths[1][buildAllPaths[0][0]]=list(buildOnePath)
            else:
                pass
        else:
            # in the case where END point is BLOCKED, we won't add any valid path
            pass
            # print('DEEPEST:  False')
    
    else:   
        
        if ((row + 1) < MAX_DIM) and (maze[(row + 1)][col] == 1):
            # print('TRAVERSE DOWN')
            buildOnePath.append( ((row + 1), col) )
            isValidPathCount = findAllPaths( ((row + 1), col), maze, MAX_DIM,                                       buildOnePath, buildAllPaths )
            # TRICK 5:  POP after recursion to permit further backtracking trials
            buildOnePath.pop()
            
         
        #ATTN:  permits ALTERNATE navigation even if above is FALSE!   
        if ((col + 1) < MAX_DIM) and (maze[row][(col + 1)] == 1):
            # print('TRAVERSE RIGHT')
            buildOnePath.append( (row, (col + 1)) )
            isValidPathCount = findAllPaths( (row, (col + 1)), maze, MAX_DIM,                                       buildOnePath, buildAllPaths )
            # TRICK 5:  POP after recursion to permit further backtracking trials
            buildOnePath.pop()
            
            
    # ATTN:  at the END, if all valid, add CURRENT point to whatever
    #        path it's on!
    # PROBLEM:  at this point; we have BACKTRACKED; however need to append to
    #           VALID CHILD FORK PATHs detected, but that info is LOST on 
    #           a BACKTRACK; so INSTEAD, found need to PREPEND prior to recursive call
    #           so then TERMINAL recursion at LEAF will capture the FULL PATH data
    #           - THEN BACKOUT AFTER returning from RECURSION to backtrack for further
    #           trials!
        
    # print ('EXIT:  buildOnePath:{},buildAllPaths:{}'.format(buildOnePath,\
    # buildAllPaths))
      
    return
    
# TEST1:  one point, OPEN => valid
print("TEST1")
maze = [[1]]
buildOnePath = []
buildAllPaths = ([0], {})
validPathsCount = findAllPaths((0,0), maze, 1, buildOnePath, buildAllPaths)
print(buildAllPaths)

# TEST2:  one point, BLOCKED => invalid
print("TEST2")
maze = [[0]]
buildOnePath = []
buildAllPaths = ([0], {})
foundPath = findAllPaths((0,0), maze, 1, buildOnePath, buildAllPaths)
print(buildAllPaths)

# TEST3:  2D, diagonal OPEN => invalid since need to move in right or down NOT diagonal
#                              and does not even enter into next recursion level
print("TEST3")
maze = [
          [1,0],
          [0,1]
       ]
buildOnePath = []
buildAllPaths = ([0], {})
foundPath = findAllPaths((0,0), maze, 2, buildOnePath, buildAllPaths)
print(buildAllPaths)

# TEST4:  2D, top corner OPEN => valid
print("TEST4")
maze = [
          [1,1],
          [0,1]
       ]
buildOnePath = []
buildAllPaths = ([0], {})
foundPath = findAllPaths((0,0), maze, 2, buildOnePath, buildAllPaths)
print(buildAllPaths)

# TEST 5: 3D, BLOCKED at intermediate points => invalid
print("TEST5")
maze = [
          [1,1,1],
          [1,1,0],
          [1,0,1]
       ]
buildOnePath = []
buildAllPaths = ([0], {})
foundPath = findAllPaths((0,0), maze, 3, buildOnePath, buildAllPaths)
print(buildAllPaths)

# TEST 6: valid
print("TEST 6")
maze = [
            [1, 1, 0, 0],
            [1, 1, 0, 1],
            [0, 1, 0, 0],
            [1, 1, 1, 1]
       ]
buildOnePath = []
buildAllPaths = ([0], {})
foundPath = findAllPaths((0,0), maze, 4, buildOnePath, buildAllPaths)
print("FINAL RESULT")
print(buildAllPaths)