# SearchMaze.py
# Andrew Davison, Dec 2023, ad@coe.psu.ac.th

# Search using DFS recursive, DFS iterative, or BFS
# Start at top-left of maze, and find a path to the bottom right

import math, sys
import searchUtils


DIRS = [(1,0), (0,1), (-1,0), (0,-1)]  # down, left, up, right
        # (rowstep, colstep)


# problem-specific ---------------


def isGoal(state):
  # at bottom right corner?
  (r, c) = state
  return (r == len(maze)-1) and (c == len(maze[0])-1)


def nextStates(state):
  (r, c) = state
  sts = []
  for dir in DIRS: # try all valid directions from (r,c)
    r1 = r+dir[0]; c1 = c+dir[1]
    if isValid(r1,c1):
      sts.append((r1,c1)) 
  return sts

def isValid(r, c):
  return ((r >= 0) and (r < len(maze)) and 
          (c >= 0) and (c < len(maze[0])) and 
          (maze[r][c] == ' '))


def printPath(path):
  for (r,c) in path:
    maze[r][c] = '.'
  printMaze(maze)


def printMaze(maze):
  wallLen = (len(maze[0])+1)*2 + 1
  print('-'*wallLen)
  for row in maze:
    print('|', end = ' ')
    for cell in row:
      print(cell, end = ' ')
    print('|')
  print('-'*wallLen)


# override the imported dummy functions
searchUtils.isGoal = isGoal
searchUtils.nextStates = nextStates


# -------------- main ----------------

# ' ' = space; '*' = wall
maze = [ [' ', '*', '*', '*', ' ', ' ', ' '],   
         [' ', ' ', ' ', ' ', ' ', '*', ' '],
         ['*', ' ', '*', '*', '*', ' ', ' '],
         ['*', ' ', '*', '*', ' ', ' ', ' '],
         ['*', ' ', '*', '*', ' ', '*', ' '],
         ['*', ' ', '*', '*', ' ', '*', ' '],
         ['*', ' ', '*', '*', ' ', '*', ' '],
         ['*', ' ', '*', '*', ' ', '*', ' '],
         [' ', ' ', ' ', ' ', ' ', '*', ' '] ]
printMaze(maze)

technique = input("DFS rec, DFS iter, or BFS (r, i, b)? ")

if technique[0] == 'r':
  print("DFS Recursive")
  path, numVisited = searchUtils.dfs((0,0), 30)  # increased depth limit
elif technique[0] == 'i':
  print("DFS Iterative")
  path, numVisited = searchUtils.dfsIter((0,0))
else:
  print("BFS")
  path, numVisited = searchUtils.bfs((0,0))


print("No. of states visited:", numVisited)
if path == None:
  print("No path found");
  sys.exit()

print("Path length:", len(path))
printPath(path)