Advertisement
Guest User

Untitled

a guest
Sep 21st, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 7.83 KB | None | 0 0
  1. student_name = "Joshua Remba"
  2.  
  3. ############################################################
  4. # Imports
  5. ############################################################
  6.  
  7. # Include your imports here, if any are used.
  8. #import collections
  9. #import itertools
  10. #import math
  11. import random
  12. #import time
  13. #import numpy
  14. import copy
  15.  
  16.  
  17. ############################################################
  18. # Section 1: Tile Puzzle
  19. ############################################################
  20.  
  21. def create_tile_puzzle(rows, cols):
  22.     board = []
  23.     counter = 1
  24.     for i in range(rows):
  25.         new_row = []
  26.         for j in range(cols):
  27.             new_row.append(counter)
  28.             counter=counter+1
  29.         if new_row[cols-1]==rows*cols:
  30.             new_row[cols-1]=0
  31.         board.append(new_row)
  32.     return TilePuzzle(board)
  33.        
  34.  
  35. class TilePuzzle(object):
  36.    
  37.     # Required
  38.     def __init__(self, board):
  39.         self.board = board
  40.         self.rows = len(board)
  41.         self.cols = len(board[0])
  42.         for i in range(len(board)):
  43.             for j in range(len(board[0])):
  44.                 if not board[i][j]:
  45.                     self.mt = (i,j)
  46.                    
  47.        
  48.  
  49.     def get_board(self):
  50.         return self.board
  51.  
  52.     def perform_move(self, direction):
  53.         mt_row = self.mt[0]
  54.         mt_col = self.mt[1]
  55.        
  56.         if direction=='up':
  57.             #print('tried to go up')
  58.             if mt_row>0:
  59.                 self.board[mt_row][mt_col]=self.board[mt_row-1][mt_col]
  60.                 self.board[mt_row-1][mt_col] = 0
  61.                 self.mt=(mt_row-1,mt_col)
  62.                 #print('did go up')
  63.                 return True
  64.             else:
  65.                 return False
  66.         elif direction=='down':
  67.             #print('tried to go down')
  68.             if mt_row<self.rows-1:
  69.                 self.board[mt_row][mt_col]=self.board[mt_row+1][mt_col]
  70.                 self.board[mt_row+1][mt_col] = 0
  71.                 self.mt=(mt_row+1,mt_col)
  72.                # print('did go down')
  73.                 return True
  74.             else:
  75.                 return False
  76.         elif direction=='left':
  77.             #print('tried to go left')
  78.             if mt_col>0:
  79.                 self.board[mt_row][mt_col]=self.board[mt_row][mt_col-1]
  80.                 self.board[mt_row][mt_col-1] = 0
  81.                 self.mt=(mt_row,mt_col-1)
  82.                # print('did go left')
  83.                 return True
  84.             else:
  85.                 return False
  86.         elif direction=='right':
  87.             #print('tried to go right')
  88.             if mt_col<self.cols-1:
  89.                 self.board[mt_row][mt_col]=self.board[mt_row][mt_col+1]
  90.                 self.board[mt_row][mt_col+1] = 0
  91.                 self.mt=(mt_row,mt_col+1)
  92.                # print('did go right')
  93.                 return True
  94.             else:
  95.                 return False
  96.         else:
  97.             return False
  98.  
  99.     def scramble(self, num_moves):
  100.         for i in range(num_moves):
  101.             self.perform_move(random.choice(['up','down','left','right']))
  102.  
  103.     def is_solved(self):
  104.         starting_board = create_tile_puzzle(self.rows, self.cols)
  105.         if self.board==starting_board.board:
  106.             return True
  107.         else:
  108.             return False
  109.  
  110.     def copy(self):
  111.         new_copy = copy.deepcopy(self.board)
  112.         return TilePuzzle(new_copy)
  113.  
  114.     def successors(self):
  115.         for i in ['up','down','left','right']:
  116.             #print(i)
  117.             x = self.copy()
  118.             x.perform_move(i)
  119.             #print(type(x))
  120.             if x.get_board()==self.get_board():
  121.                 pass
  122.             else:
  123.                 #print(i)
  124.                 #print(x)
  125.                 yield i, x
  126.  
  127.  
  128.    
  129.            
  130.            
  131.            
  132.            
  133.            
  134.            
  135.            
  136.            
  137.            
  138.            
  139.            
  140.            
  141.  
  142.  
  143. #
  144. #    # Required
  145. #    def find_solutions_iddfs(self,limit=0,moves=[],counter=0,visited=[[]]):
  146. ##        while True:
  147. #
  148. #        while limit<10:
  149. #            if visited==[[]]:
  150. #                visited = [self.board]
  151. #            limit = limit + 1
  152. #            print(limit)
  153. #            if self.is_solved():
  154. #            #print(self.board)
  155. #                yield moves
  156. #            elif counter<limit:
  157. #            #continue to recurse if you haven't hit the depth limit  
  158. ##            if self.board==[[1,2,3],[4,5,6],[7,0,8]]:
  159. ##            if [[1,2,3],[4,5,6],[7,0,8]] in visited:
  160. ##                print('uh oh')
  161. ##            if limit==7:
  162. ##                print(visited)
  163. #                for move, new_p in self.successors():
  164. ##                    print('new board to check: ', new_p.get_board())
  165. ##                    print('what was already visited: ',visited)
  166. #    #                print('visited so far:')
  167. #    #                print(visited)
  168. #    #                print('new board to add')
  169. #    #                print(new_p.board)
  170. #                    if new_p.board==[[1,2,3],[4,5,6],[7,8,0]]:
  171. #                        print('hmmmm')
  172. #                    if new_p.board not in visited:
  173. #                        moves_temp = moves+[move]
  174. #    #                    print('moves: ',moves)
  175. #    #                    print('moves_temp: ', moves_temp)
  176. #    #                    print(new_p)
  177. #                        visited.append(new_p.board)
  178. #                        yield from self.find_solutions_iddfs(limit,moves_temp,counter+1,visited)
  179. #            #print('after the helper call')
  180. #        #return x
  181.              
  182.            
  183.            
  184.            
  185.            
  186.            
  187.            
  188.            
  189.            
  190.            
  191.            
  192.            
  193.            
  194.            
  195.            
  196.            
  197.            
  198.            
  199.            
  200.            
  201.            
  202.            
  203.            
  204.            
  205.                            
  206.     def iddfs_helper(self,limit,moves,counter,visited):
  207.         if self.board==[[1,2,3],[4,5,6],[7,8,0]]:
  208.             print('it is actually solved, but it is saying it is not solved')
  209.        
  210.         if self.is_solved():
  211.             #print(self.board)
  212.             yield moves
  213.         elif counter<limit:
  214.             #continue to recurse if you haven't hit the depth limit  
  215. #            if self.board==[[1,2,3],[4,5,6],[7,0,8]]:
  216. #            if [[1,2,3],[4,5,6],[7,0,8]] in visited:
  217. #                print('uh oh')
  218. #            if limit==7:
  219. #                print(visited)
  220.             for move, new_p in self.successors():
  221. #                print('new board to check: ', new_p.get_board())
  222. #                print('what was already visited: ',visited)
  223. #                print('visited so far:')
  224. #                print(visited)
  225. #                print('new board to add')
  226. #                print(new_p.board)
  227.                 if new_p.board==[[1,2,3],[4,5,6],[7,8,0]]:
  228.                     print('hmmmm')
  229.                 if new_p.board not in visited:
  230.                     moves_temp = moves+[move]
  231. #                    print('moves: ',moves)
  232. #                    print('moves_temp: ', moves_temp)
  233. #                    print(new_p)
  234.                     visited.append(new_p.board)
  235.                     yield from new_p.iddfs_helper(limit,moves_temp,counter+1,visited)
  236.  
  237.  
  238.     # Required
  239.     def find_solutions_iddfs(self):
  240.         limit = 0
  241.         moves=[]
  242. #        while True:
  243.         while limit<10:
  244.             limit = limit + 1
  245.             print(limit)
  246.             yield from self.iddfs_helper(limit, moves,0,[self.board])
  247.             #print('after the helper call')
  248.         #return x
  249.            
  250.    
  251.  
  252.            
  253.            
  254.            
  255. #b = [[4,1,2], [0,5,3], [7,8,6]]
  256. #p = TilePuzzle(b)
  257. #solutions = p.find_solutions_iddfs()
  258. ##solutions = p.iddfs_helper(3,[],0)
  259. #print(next(solutions))
  260.  
  261.        
  262. b = [[1,2,3], [4,0,8], [7,6,5]]
  263. p = TilePuzzle(b)
  264. list(p.find_solutions_iddfs())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement