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

# https://en.wikipedia.org/wiki/15_Puzzle

'''
The 8 puzzle problem solution is a 3 by 3 board with 8 tiles (each tile has a number from 1 to 8) and a single empty space numbered as 0. The goal is to use the vacant space to arrange the numbers on the tiles such that they match the goal state. Four neighbouring (left, right, up, and down) tiles can be moved into the available area.
 
The goal state == [ 1 2 3 4 5 6 7 8 0 ]

Search uses DFS recursive, BFS, or AStar

The Python recursion-limit is changed, and the time and memory used
is reported.

'''

import searchUtils
import sys, threading
import time, tracemalloc


initLoc = [1, 2, 5, 3, 4, 0, 6, 7, 8]
'''
  1 2 5
  3 4 0
  6 7 8
'''

# initLoc = [1, 4, 2, 6, 5, 8, 7, 3, 0]
'''
  1 4 2
  6 5 8
  7 3 0
'''

# initLoc = [1, 0, 2, 7, 5, 4, 8, 6, 3]
'''
  1 0 2
  7 5 4
  8 6 3
'''

# initLoc = [0, 8, 7, 6, 5, 4, 3, 2, 1]
'''    
  0 8 7
  6 5 4
  3 2 1
'''



GOAL = [0, 1, 2, 3, 4, 5, 6, 7, 8]
SIZE = 3


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

def isGoal(loc):
  return loc == GOAL


def nextStates(loc):
  nLocs = []
  idx = loc.index(0) # find pos of 0
  getLoc(loc, idx, 'Up', nLocs)
  getLoc(loc, idx, 'Down', nLocs)
  getLoc(loc, idx, 'Left', nLocs)
  getLoc(loc, idx, 'Right', nLocs)
  return nLocs


def getLoc(loc, idx, move, nLocs):
  nLoc = list(loc)

  if move == 'Right':
    if idx % SIZE == SIZE-1:
      return
    swap(nLoc, idx, idx+1)
    nLocs.append(nLoc)

  elif move == 'Left':
    if idx % SIZE == 0:
      return
    swap(nLoc, idx, idx-1)
    nLocs.append(nLoc)

  elif move == 'Up':
    if idx < SIZE:
      return
    swap(nLoc, idx, idx-3)
    nLocs.append(nLoc)

  elif move == 'Down':
    if idx > len(nLoc)-1-SIZE:
      return
    swap(nLoc, idx, idx+3)
    nLocs.append(nLoc)


def swap(locs, i, j):
  locs[i], locs[j] = locs[j], locs[i]



def printPath(path):
  for loc in path:
    printTiles(loc)
  print("Path length:", len(path))


def printTiles(loc):
  i = 0
  while i < len(loc):
    print(loc[i], end=' ')
    i += 1
    if i%SIZE == 0:
      print()
  print()



def goalDist(loc):
  ''' The sum of the Manhattan distances 
      (sum of the vertical and horizontal dists) 
      from the tiles to their goal positions
  '''
  tot = 0
  for i in range(len(loc)):
    idx =  loc.index(i)   # location of tile i
    row, col = idx//SIZE, idx%SIZE

    idxG =  GOAL.index(i) # goal location of tile i
    rowG, colG = idxG//SIZE, idxG%SIZE

    tot += abs(row-rowG) + abs(col-colG)
  return tot



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

  
# ---------------

def main(alg):
  print("Initial Tile locations", initLoc)

  start_time = time.time()
  tracemalloc.start()

  if alg == 'd':
    path, numVisited = searchUtils.dfs(initLoc)
  elif alg == 'a':
    path, numVisited = searchUtils.aStar(initLoc)
  else:
    path, numVisited = searchUtils.bfs(initLoc)

  elapsed_time = time.time() - start_time
  _, peakMem = tracemalloc.get_traced_memory()
  tracemalloc.stop()

  if path == None:
    print("No path found")
  else:
    printPath(path)

  print("\nNo. states visited:", numVisited)
  print(f"Duration: {elapsed_time:.3f} secs")
  print("Peak memory:", peakMem, "bytes")


# ---------------

alg = input("bfs, astar, or dfs (b, a, d)? ").lower()[0]

if alg == 'd':
  sys.setrecursionlimit(10**6)
  threading.stack_size(67108864) # 64MB stack

  # only new threads get the redefined stack size
  thread = threading.Thread(target=main, args=(alg))
  thread.start()
else: 
  main(alg)