Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/bin/python3
- import math
- import os
- import random
- import re
- import sys
- #
- # Complete the 'movesToSolve' function below.
- #
- # The function is expected to return an INTEGER.
- # The function accepts 2D_INTEGER_ARRAY puzzle as parameter.
- #
- from collections import deque
- import copy
- def zeroLocation(puzzle): # Helper function to return X,Y coordinates of 0 square
- for i in range(len(puzzle)):
- for j in range(len(puzzle[0])):
- if puzzle[i][j] == 0:
- return (i,j)
- def neighbors(puzzle):
- X, Y = len(puzzle), len(puzzle[0])
- neighbors = []
- x_zero, y_zero = zeroLocation(puzzle)
- for x,y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
- x_new = x_zero + x
- y_new = y_zero + y
- if 0 <= x_new < X and 0 <= y_new < Y:
- new_board = copy.deepcopy(puzzle)
- new_board[x_zero][y_zero], new_board[x_new][y_new] = new_board[x_new][y_new], new_board[x_zero][y_zero]
- neighbors.append(new_board)
- return neighbors
- def movesToSolve(puzzle):
- # Write your code here
- nRows = len(puzzle)
- mRows = len(puzzle[0])
- solved = [[0 for x in range(nRows)] for y in range(mRows)]
- counter = 0 # Generate Solved Board to check for Goal
- for i in range(nRows):
- for j in range(mRows):
- solved[i][j] = counter
- counter += 1
- if puzzle == solved:
- return 0
- queue = deque()
- queue.append((puzzle,[puzzle]))
- import time
- start = time.time()
- seen = set()
- while queue:
- if time.time() - start > 7: return -1
- current, path = queue.popleft()
- neighbs = neighbors(current)
- for p in path:
- if p in neighbs: neighbs.remove(p)
- for neighbor in neighbs:
- if repr(neighbor) not in seen:
- if neighbor == solved:
- return(len(path)) # Number of Moves
- exit()
- else:
- queue.append((neighbor, path+[neighbor]))
- for x in neighbs: seen.add(repr(x))
- return -1
- if __name__ == '__main__':
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement