#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    10
    Rep Power
    0

    Python recursive maze


    the code that i have currently done so far for the recursive maze. it is supposed to start at the S and end at the F and print out a list of coordinate points at the end of the solution to the maze. if no solution, print "no solution".
    thanks in advance!

    this is the input:

    WPPWWW
    WWPWPS
    WWPWPW
    PPPPPW
    FWPWWW
    WPPPPW


    Code:
    #this function reads a maze file, filename, and creates a maze, m.
    # Please declare "m" as a list before calling the function and then pass it in. 
    m=[]  # This declares the maze as an empty list
    def readMaze(m, filename):
      mazeFile = open(filename, "r")
      lines = mazeFile.readlines()
      for line in lines:
        line = line.strip()
        row = [c for c in line]
        m.append(row)
    
    
    readMaze(m, "sampleMaze.txt") # This reads the maze into the list
    print m # This prints the maze, showing it with the usual notation as a "list of lists"
    start  = []
    
    [PHP]
    def findStart(m):
        start = []
        mazeSolution = []
        for row in xrange(len(m)):
            for col in xrange(len(m[row])):
                if m[row][col]== "S":
                    start = [row,col]
                    mazeSolution = start
        return mazeSolution
    
    def solveMaze(m, mazeSolution):
        mazeSolution = findStart(m)
        row = mazeSolution[0]
        col = mazeSolution[1]
        return( solveMaze2(m, mazeSolution, row, col))
    
    
    
    
    ###############
    import copy
    def countMaze(m, row, col):
    
      memoMap = copy.deepcopy(m)
      return solveMaze2(m,memoMap,row,col)
    
    
    def solveMaze2(m,memoMap,row,col):
      memoMap = copy.deepcopy(m)
      if ( (row<0) or (col<0) ):
        return 0
      if ( (row >= len(m[0])) or (col >= len(m[1]))):
        return 0
    
      if (memoMap[row][col] == "F"):
        return 0
    
      if (m[row][col] != "P"):
        return 0
    
      memoMap[row][col] = "W"
    
      if(solveMaze2(m,memoMap,row-1,col)):
                    mazeSolution.append(row-1,col)
                    return True
      elif(solveMaze2(m,memoMap,row,col-1)):
                    mazeSolution.append(row,col-1)
                    return True
      elif(solveMaze2(m,memoMap,row,col+1)):
                    mazeSolution.append(row,col+1)
                    return True
      elif(solveMaze2(m,memoMap,row+1,col)):
                    mazeSolution.append(row+1,col)
                    return True
    
      else:
                    return False
    
    ##################
    def mazeSolver2():
      mazeFile = "sampleMaze.txt"
      readMaze(m, mazeFile)
      mazeSolution = []
     # solution = findStart(m)
      print mazeSolution
    
      if (solveMaze(m, mazeSolution)== True):
        print "True"
        print mazeSolution
      else:
        print "No solution found."
    
    mazeSolver2()
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    You've ruined your program by reassigning mazeSolution in solvemaze instead of modifying the list passed as an argument. I think the program is fixed with following code. I put a "moat" around the maze to eliminate some tests, tests that could have used
    0 <= i < len(LIST) tests. I removed other logic, parentheses, and extraneous code. I'm sure someone else can reduce it a good deal further. http://stackoverflow.com/questions/2...of the others. Oh, the other big problem was that the maze didn't have an exit, or I had a misunderstanding. New input file, with X to mark the exit, is
    WPPWWW
    WWPWPS
    WWPWPW
    PPPPPW
    FWPWWW
    WPPPXW
    Code:
    import pprint
    
    def readMaze(filename):
        with open(filename,'r') as mazeFile:
            return [[c for c in line.strip()] for line in mazeFile]
    
    def moat(maze): # surround with a moat to remove the need for bound testing
        for r in maze:
            r[:0] = ['W']
            r.append('W')
        r0 = ['W']*len(maze[0])
        maze[:0] = [r0]
        maze.append(r0)
    
    def findStart(m):
        start = []
        for row in range(len(m)):
            for col in range(len(m[row])):
                if m[row][col] == 'S':
                    return (row,col,)
     
    def solveMaze2(maze,solution,row,col):
        cell_value = maze[row][col]
        if cell_value not in 'PSX': return False
        if cell_value == 'X': return True
        maze[row][col] = 'W' # drop crumb
        for (dr,dc,) in ((-1,0,), (1,0,), (0,-1,), (0,1)):
            if solveMaze2(maze,solution,row+dr,col+dc):
                solution.append((row+dr,col+dc,))
                return True
    
    def solveMaze(maze, solution):
        start = findStart(maze)
        print('start:',start)
        if start:
            if solveMaze2(maze, solution, *start):
                solution.append(start)
                solution[:] = reversed(solution)
                return True
        return False
    
    def main():
        maze = readMaze('sampleMaze.txt')
        moat(maze)
        pprint.pprint(maze)
        solution = []
        if not solveMaze(maze,solution):
            print('No solution found.')
        else:
            print(solution)
    
    main()
    Last edited by b49P23TIvg; July 24th, 2013 at 12:40 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo