# gridPaths.py

# Search using DFS
# Start at top-left of grid, and find a path to the bottom right

import math, random, statistics

NUM_TRIALS = 10000  # 20000

DIRS = ['N', 'E', 'S', 'W']
GRID_SIZE = 11
CENTER = (5,5)

def findPath(showGrid=False):
  global grid, visited, nChoices
  grid = [[' ' for y in range(GRID_SIZE)] 
                   for x in range(GRID_SIZE)]
  visited = [(0,0)]
  nChoices = 1
  if not dfs(0,0):
    print("End point not found")
  if showGrid:
    printPath(visited)
    print(*visited)
    print(f"{len(visited)}, {nChoices*1.0:.3g}, {1/nChoices:3g}")
  return visited, nChoices


def dfs(r, c):
  global nChoices
  if atEnd(r,c):
    return True

  possSteps = nextSteps(r,c)
  nSteps = len(possSteps)
  if nSteps > 0:
    nChoices *= nSteps
    for (r1,c1) in possSteps:
      visited.append((r1,c1))
      if dfs(r1, c1):
        return True 
  return False

def atEnd(r, c):
  # at bottom right corner?
  return (r == GRID_SIZE-1) and (c == GRID_SIZE-1)


def nextSteps(r, c):
  random.shuffle(DIRS)
  steps = [dirPos(r, c, dir) for dir in DIRS]
  return [ (r1,c1) for (r1,c1) in steps if isValid(r1,c1)]


def dirPos(r, c, dir):
  if dir == 'N':
    return (r-1, c)
  elif dir == 'E':
    return (r, c+1)
  elif dir == 'S':
    return (r+1, c)
  else:   # assume it's W
    return (r, c-1)


def isValid(r, c):
  if r < 0 or r >= GRID_SIZE:
    return False
  if c < 0 or c >= GRID_SIZE:
    return False
  return not ((r,c) in visited) 



def printPath(path):
  for (r,c) in path:
    if (r,c) == CENTER:
      grid[r][c] = 'x'
    else:
      grid[r][c] = '.'
  printGrid(grid)


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


if __name__ == "__main__":
  vs = []
  nChs = []
  numCenters = 0
  for i in range(NUM_TRIALS):
    visited, nChoices = findPath()
    vs.append(len(visited))
    nChs.append(nChoices)
    numCenters += 1 if (CENTER in visited) else 0

  print(f"ctr: {numCenters/NUM_TRIALS:.1%}")

  plMean = statistics.mean(vs)
  plStdev = statistics.stdev(vs)
  print(f"len. mean = {plMean:.2f};  stdev = {plStdev:.2f}")
  
  chsMean = statistics.mean(nChs)
  chsMedian = statistics.median(nChs)
  chsMode = statistics.mode(nChs)
  chsStdev = statistics.stdev(nChs)
  print(f"choices. mean = {chsMean:.3g};  stdev = {chsStdev:.3g}")
  print(f"choices. median = {chsMedian:.3g};  mode = {chsMode:.3g}")