Guest User

Untitled

a guest
Dec 7th, 2019
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''class LinkedStack:
  2.    class _Node:
  3.        __slots__ = '_element', '_next'
  4.        def __init__(self , element ,next):
  5.            self._element = element
  6.            self._next = next
  7.    def __init__(self):
  8.        self._head = None
  9.        self._size = 0
  10.    def __len__(self):
  11.        return self._size
  12.    def is_empty(self):
  13.        return self._size  == 0
  14.    def push(self , e):
  15.        self._head = self._Node(e, self._head)
  16.        self._size  += 1
  17.    def top(self):
  18.        if self.is_empty ():
  19.            raiseEmpty('Stack is  empty')
  20.        return self._head._element
  21.    def pop(self):
  22.        if self.is_empty():
  23.            raiseEmpty('Stack is  empty')
  24.        answer = self._head._element
  25.        self._head = self._head._next
  26.        self._size  -= 1
  27.        return answer
  28.  
  29. class LinkedQueue:
  30.    class _Node:
  31.        __slots__ = '_element', '_next'
  32.        def __init__(self, element, next):
  33.            self._element = elementself._next = next
  34.    def __init__(self):
  35.        self._head = None
  36.        self._tail = None
  37.        self._size = 0
  38.    def __len__(self):
  39.        return self._size
  40.    def is_empty(self):
  41.        return self._size  == 0
  42.    def first(self):
  43.        if self.is_empty ():
  44.            raiseEmpty('Queue is  empty')
  45.        return self._head._element
  46.    def dequeue(self):
  47.        if self.is_empty():
  48.            raiseEmpty('Queue is  empty')
  49.        answer = self._head._element
  50.        self._head = self._head._next
  51.        self._size  -= 1
  52.        if self.is_empty ():
  53.            self._tail = None
  54.        return answer
  55.    def enqueue(self , e):
  56.        newest = self._Node(e, None)
  57.        if self.is_empty ():
  58.            self._head = newest
  59.        else:
  60.            self._tail._next = newest
  61.        self._tail = newest
  62.        self._size  += 1'''
  63.  
  64. import random
  65. import sys
  66.  
  67. class Stack:
  68.   def __init__(self):
  69.     self._A = []
  70.   def pop(self):
  71.     self._A.pop()
  72.   def push(self, obj):
  73.     self._A.append(obj)
  74.   def is_empty(self):
  75.     return len(self._A) == 0
  76.  
  77. class Queue:
  78.     def __init__(self):
  79.         self._A = []
  80.     def enqueue(self, obj):
  81.         self._A.append(obj)
  82.     def dequeue(self):
  83.         self._A.pop(0)
  84.     def is_empty(self):
  85.         return len(self._A) == 0
  86.  
  87. class Maze:
  88.   def __init__(self, size):
  89.       self.maze_size = size
  90.       self.goal_x = random.randint(0, self.maze_size + 1) #chooses random x coordinate within maze size for endpoint
  91.       self.goal_y = random.randint(0, self.maze_size + 1) #chooses random y coordinate within maze size for endpoint  
  92.  
  93.   def DrawMaze(self):
  94.       visited = []
  95.       x_s = stack()
  96.       x_s.push(0)
  97.       y_s = stack()
  98.       y_s.push(0)
  99.       while not x_s.is_empty() and y_s.is_empty():
  100.         x_current = x_s.pop() #current x coordinate
  101.         y_current = y_s.pop() #current y coordinate
  102.         visited.append(x_current, y_current)
  103.         temp = []  #will be list of unvisited coordinates surrounding (x_current, y_current)
  104.         if (x_current + 1, y_current) not in visited:
  105.           temp.append(x_current + 1, y_current)
  106.         if (x_current - 1, y_current) not in visited:
  107.           temp.append(x_current - 1, y_current)
  108.         if (x_current, y_current + 1) not in visited:
  109.           temp.append(x_current, y_current + 1)
  110.         if (x_current, y_current - 1) not in visited:
  111.           temp.append(x_current, y_current - 1)
  112.         x_current, y_current = temp.pop(random.randint(0, len(temp) - 1))
  113.        
  114.        
  115.   def TraverseMaze(self):
  116.       visited = [] #visited coordinates
  117.       x_q = Queue()
  118.       x_q.enqueue(0)
  119.       y_q = Queue()
  120.       y_q.enqueue(0)
  121.       while not x_q.is_empty() and y_q.is_empty():
  122.         x_current = x_q.dequeue() #current x coordinate
  123.         y_current = y_q.dequeue() #current y coordinate
  124.         visited.append((x_current, y_current))
  125.         if x_current == self.goal_x and y_current == self.goal_y: #if current coordinates is endpoint
  126.           break
  127.         if (x_current + 1, y_current) not in visited and :  #if reachable and unvisited, enqueue coordinates to right(coordinates east of current)
  128.           x_q.enqueue(x_current + 1)
  129.           y_q.enqueue(y_current)
  130.         if (x_current, y_current + 1) not in visited and :  #if reachable and unvisited, enqueue coordinates below(coordinates south of current)
  131.           x_q.enqueue(x_current)
  132.           y_q.enqueue(y_current + 1)
  133.         if (x_current - 1, y_current) not in visited and :  #if reachable and unvisited, enqueue coordinates to left(coordinates west of current)
  134.           x_q.enqueue(x_current - 1)
  135.           y_q.enqueue(y_current)
  136.         if (x_current, y_current - 1) not in visited and :  #if reachable and unvisited, enqueue coordinates above(coordinates north of current)
  137.           x_q.enqueue(x_current)
  138.           y_q.enqueue(y_current - 1)
  139.  
  140. maze_size = int(input('please enter a maze size'))
  141.  
  142. #prints maze
  143. '''def PrintMaze(maze):
  144.     for row in range(maze_size):
  145.         print(maze[row])
  146.     print'''
  147.  
  148. '''#determines if coordinates are in bounds of maze
  149. def InBounds(x,y):
  150.     return (0 <= x < maze_size) and (0 <= y < maze_size)
  151.  
  152. def TraverseMaze(maze):          # traverse maze
  153.    start = (0,0)
  154.    s = Stack()
  155.    s.push(start);               # push the start coordinates onto s
  156.    while not s.is_empty():      #Loops until stack is empty
  157.         (x, y) = s.pop()          # pop a coordinate off s into the tuple (x,y)
  158.         if InBounds((x,y)):         # if (x,y) is on the maze then
  159.             if maze[x][y] == 'G':    # if (x,y) is the goal then
  160.                 s.empty()             # empty the stack because we're done
  161.             elif maze[x][y] == ' ':  # else if (x,y) is an undiscovered coordinate
  162.                 maze[x] = maze[x][:y] + 'D' + maze[x][y+1:]  # mark (x,y) discovered with 'D'
  163.                 PrintMaze(maze);      # print the maze to show progress so far
  164.                 s.push((x+1, y))      # push right neighbor onto stack s
  165.                 s.push((x-1, y))      # push left neighbor onto stack s
  166.                 s.push((x, y-1))      # push upper neighbor onto stack s
  167.                 s.push((x, y+1))      # push lower neighbor onto stack s'''
RAW Paste Data