# 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

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


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


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

  possSteps = nextSteps(r,c)
  nSteps = len(possSteps)
  for (r1,c1) in possSteps:
    path.append((r1,c1))
    visited.append((r1,c1))
    nchs = dfs(r1, c1, nChoices*nSteps)
    if nchs != -1:  
      return nchs
    else:
      path.remove((r1,c1))
  return -1


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__":
  numCenters = 0
  pathLens = []
  nChs = []
  for i in range(NUM_TRIALS):
    path, nChoices = findPath()
    numCenters += 1 if (CENTER in path) else 0
    pathLens.append(len(path))
    nChs.append(nChoices)

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

  plMean = statistics.mean(pathLens)
  plStdev = statistics.stdev(pathLens)
  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}")