SHARE
TWEET

Untitled

a guest Dec 7th, 2019 90 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top