Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Maze - All Valid Paths
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.