Guest User

Untitled

a guest
Nov 20th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.29 KB | None | 0 0
  1. # don't worry much about these things; I've defined a few functions for you that may be useful
  2. # skip down past these to see where you should start writing your code
  3.  
  4.  
  5. import numpy as np
  6. from typing import List, Tuple
  7. from collections import deque
  8.  
  9.  
  10. def get_puzzle(shape: Tuple[int, int]=(3, 3)) -> Tuple:
  11. """
  12. 0 denotes the blank space.
  13. :param shape: the shape of the puzzle. If an int is given, it will be a square of that size. If two ints are given,
  14. it will be a rectangle of that shape.
  15. :returns:
  16. """
  17.  
  18. size = np.prod(shape)
  19. num_inversions = 1 # so that we go into the while loop
  20. while num_inversions % 2 != 0:
  21. puzzle = np.random.permutation(np.arange(size))
  22.  
  23. num_inversions = 0
  24. for i in range(len(puzzle)):
  25. if puzzle[i] == 0:
  26. continue # ignore blank space
  27. for j in range(i): # all spaces before this one
  28. if puzzle[j] > puzzle[i]:
  29. num_inversions += 1
  30.  
  31. return tuple(puzzle)
  32.  
  33.  
  34. def get_goal_state(shape: Tuple[int, int]=(3, 3)) -> Tuple:
  35. """
  36. 0 denotes the blank space.
  37. :param shape: the shape of the puzzle. If an int is given, it will be a square of that size. If two ints are given,
  38. it will be a rectangle of that shape.
  39. :returns:
  40. """
  41. return tuple(range(1, np.prod(shape))) + (0,)
  42.  
  43.  
  44. class Puzzle(object):
  45. def __init__(self, shape: Tuple[int, int]):
  46. """
  47. 1x1 is not supported
  48. :param shape: height, length
  49. """
  50.  
  51. self.height = shape[0]
  52. self.length = shape[1]
  53. self.size = self.length * self.height
  54.  
  55. # set up parameters needed for computing neighbors for a puzzle of this size
  56.  
  57. left_swap = -1 # sliding left means the index goes down one
  58. right_swap = 1 # up one for a right slide
  59. top_swap = -self.length # moving up is like moving backwards an entire length
  60. bottom_swap = self.length
  61.  
  62. idx = {
  63. 'top': tuple(range(self.length)),
  64. 'left': tuple(range(0, self.size, self.length)),
  65. 'right': tuple(range(self.length - 1, self.size, self.length)),
  66. 'bottom': tuple(range(self.size - self.length, self.size))
  67. }
  68.  
  69. valid_swaps = {
  70. 'left': [right_swap, top_swap, bottom_swap],
  71. 'right': [left_swap, top_swap, bottom_swap],
  72. 'top': [left_swap, right_swap, bottom_swap],
  73. 'bottom': [left_swap, right_swap, top_swap]
  74. }
  75.  
  76. valid_swaps_top_left_corner = [right_swap, bottom_swap]
  77. valid_swaps_top_right_corner = [left_swap, bottom_swap]
  78. valid_swaps_bottom_left_corner = [right_swap, top_swap]
  79. valid_swaps_bottom_right_corner = [left_swap, top_swap]
  80.  
  81. all_swaps = [left_swap, right_swap, top_swap, bottom_swap]
  82.  
  83. # {zero_idx: [valid_swaps]}
  84. self.valid_swaps = {i: valid_swaps[direction] for direction in idx for i in idx[direction]}
  85.  
  86. # add in all of the points not on an edge
  87. for i in range(self.size):
  88. if i not in self.valid_swaps:
  89. self.valid_swaps[i] = all_swaps
  90.  
  91. # fix the corners
  92. self.valid_swaps[0] = valid_swaps_top_left_corner
  93. self.valid_swaps[self.length - 1] = valid_swaps_top_right_corner
  94. self.valid_swaps[self.size - self.length] = valid_swaps_bottom_left_corner
  95. self.valid_swaps[self.size - 1] = valid_swaps_bottom_right_corner
  96.  
  97. def swap(self, state: Tuple[int], i: int, j: int) -> Tuple[int]:
  98. """
  99. Swaps two elements in the given state tuple.
  100. :param state: a tuple with the current state of a puzzle
  101. :type state: tuple
  102. :param i: index of one element to swap
  103. :param j: index of other element to swap; j != i
  104. :return: a tuple which is a copy of state except the elements at i, j are swapped
  105. """
  106.  
  107. first, second = sorted([i, j])
  108. swapped = (*state[:first], state[second], *state[first + 1: second], state[first], *state[second + 1:])
  109. # swapped = state[:first] + (state[second],) + state[first+1:second] + (state[first],) + state[second+1:]
  110. return swapped
  111.  
  112. def neighbors(self, state):
  113. """
  114. Returns a list of all the states reachable from the given state with one slide
  115. :type state: tuple
  116. :param state: the state from which to
  117. :return: a list of states that are reachable with one slide
  118. """
  119.  
  120. blank_idx = state.index(0) # where the blank spot is; slides have to move a piece to here
  121. return [self.swap(state, blank_idx, blank_idx + swap) for swap in self.valid_swaps[blank_idx]]
  122.  
  123.  
  124. def print_path(path: List[Tuple[int]], shape: Tuple[int, int]):
  125. print([np.array(path[i]).reshape(shape).tolist() for i in range(len(path))])
  126.  
  127.  
  128. #### YOUR CODE HERE #####
  129.  
  130. puzzle_shape = (3, 3)
  131. start = get_puzzle(puzzle_shape) # randomly makes a puzzle for you
  132. goal = get_goal_state(puzzle_shape) # get to this state to win!
  133.  
  134. print("Starting puzzle state:", start) # this is stored as 1D, but it represents a 3x3 puzzle
  135. print("Goal state:", goal)
  136.  
  137. # this defines the function to get neighbors from a given puzzle node
  138. puzzle_helper = Puzzle(puzzle_shape)
  139.  
  140. print("Neighbors of starting state:", puzzle_helper.neighbors(start))
  141.  
  142.  
  143. ### WRITE YOUR FUNCTION HERE
  144. # it should return a path: a list of nodes which begins with start and ends with goal
  145. expanded = set()
  146. # expanded.add('hi')
  147. # print(expanded)
  148. parents = {}
  149. # parents[start] = None
  150. fringe = deque()
  151. # fringe.popleft
  152. # fringe.pop
  153. # fringe.append
  154. # fringe.appendleft
  155.  
  156. for neighbor in puzzle_helper.neighbors(start):
  157. new_parents_entry = parents.get(neighbor, set())
  158. new_parents_entry.add(start)
  159. print(new_parents_entry)
  160. parents[neighbor] = new_parents_entry
  161. fringe.append(neighbor)
  162.  
  163. print(parents)
  164.  
  165. while len(fringe) > 0:
  166. cur_neighbor = fringe.pop()
  167. if cur_neighbor == goal:
  168. solved = True
  169. print(cur_neighbor)
  170. print("Found goal")
  171. expanded.add(cur_neighbor)
  172. for neighbor in puzzle_helper.neighbors(cur_neighbor):
  173. if neighbor not in expanded:
  174. fringe.append(neighbor)
  175.  
  176.  
  177.  
  178. # this will format the path you found in the right way so you can visualize it with the website
  179. # just copy
  180. path = [start, goal] # not a real path; missing all of the nodes in the middle
  181. # print("Path:")
  182. # print_path(path, puzzle_shape)
Add Comment
Please, Sign In to add comment