daily pastebin goal
4%
SHARE
TWEET

Untitled

a guest Sep 25th, 2018 64 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. ###maze3.py
  2.  
  3. import random
  4. import sys
  5. import numpy
  6. X = 2
  7. Y = 2
  8.  
  9. indicies = numpy.arange(X*Y).reshape(X,Y) # creates X by Y array from 0 to X*Y
  10. rightwalls = numpy.ones(X*Y,bool)   #creates X * Y list of TRUE
  11. downwalls = numpy.ones(X*Y,bool)    #likewise
  12.  
  13. def generate_walls():
  14.  
  15.     #this function creates a numpy array, [first column is all possible down walls, second is all possible right walls (notice X size -1 missing), third row is still a bit of a mystery ]
  16.     TotalRightWalls = (X-1)*Y
  17.     TotalDownWalls = (Y-1)*X
  18.     TotalWalls = TotalRightWalls+TotalDownWalls
  19.     print TotalWalls
  20.  
  21.     walls = numpy.empty((TotalWalls,3),int) #numpy.empty returns non-zeroed array CAREFUL!
  22.     walls[:TotalRightWalls,0] = indicies[:-1:].flatten() #90 elements 0-90
  23.     walls[:TotalRightWalls,1] = indicies[:,1:].flatten() #90 elements 0-100 skipping multiples of 10, second row
  24.     walls[:TotalRightWalls,2] = True # third row 90 ones
  25.  
  26.     walls[TotalRightWalls:,0] = indicies[:,:-1].flatten()
  27.     walls[TotalRightWalls:,1] = indicies[:,1:].flatten()
  28.     walls[TotalRightWalls:,2] = False
  29.  
  30.     return walls
  31.  
  32. class UnionFind(object):
  33.     def __init__(self,sections):
  34.         self.parent = numpy.arange(sections)
  35.         self.rank = numpy.ones(sections)
  36.         self.final = numpy.ones(sections,bool)
  37.  
  38.     def find(self,a):
  39.         parents = self.parent
  40.         parent = parents[a]
  41.         if not self.final[parent]:
  42.             parent=  self.find(parent)
  43.             parents[a]= parent
  44.         return parent
  45.  
  46.     def union(self,a,b):
  47.         find = self.find   
  48.         a_par = find(a)
  49.         b_par = find(b)
  50.         if a_par != b_par:
  51.             rank = self.rank
  52.             parent = self.parent
  53.             final = self.final
  54.             a_rank = rank[a_par]
  55.             b_rank = rank[b_par]
  56.             if a_rank < b_rank:
  57.                 parent[a_par] = b_par
  58.                 final[a_par] = False
  59.             elif b_rank < a_rank:
  60.                 parent[b_par] = a_par
  61.                 final[b_par] = False
  62.             else:
  63.                 parent[b_par] = a_par
  64.                 final[b_par] = False
  65.                 rank[a_par] += 1
  66.             return True
  67.         else:
  68.             return False
  69.  
  70. def mazify():
  71.     walls = generate_walls()
  72.     numpy.random.shuffle(walls)
  73.     uf = UnionFind(X*Y)
  74.     for parent, neighbor, right in walls:
  75.         if uf.union(parent,neighbor):
  76.             if right:
  77.                 rightwalls[parent] = False
  78.             else:
  79.                 downwalls[parent] = False
  80.  
  81.  
  82. def output(blocked):
  83.     sys.stdout.write( " @"[blocked])
  84.     if blocked:
  85.         pass
  86. def draw_maze():
  87.     lst = []
  88.     for x in range(2*X+1):
  89.         output(True) #top lines
  90.     sys.stdout.write('\n')
  91.     for y in xrange(Y):
  92.         output(True)    #left lines
  93.         lst.append(True)
  94.         for x in xrange(X):
  95.             lst.append(False)
  96.             lst.append(rightwalls[indicies[x,y]])
  97.             output(False)
  98.             output(rightwalls[indicies[x,y]])
  99.         sys.stdout.write('\n')
  100.         lst.append(True)
  101.         output(True)
  102.         for x in xrange(X):
  103.             lst.append(downwalls[indicies[x,y]])
  104.             lst.append(True)
  105.             output(downwalls[indicies[x,y]])
  106.             output(True)
  107.         sys.stdout.write('\n')
  108.        
  109.     lst2=[]
  110.     for x in range(len(lst)):
  111.         lst2.append(lst[x])
  112.     step = 2*X+1
  113.     a = []
  114.     for i in range(0,len(lst2),step):
  115.         a.append(lst2[i:i+step])
  116.     a[len(a)-1][2*X-1]=2
  117.     #a[1][1] = 2
  118.     print a
  119.     junk,grid = search(0,0,a)
  120.     for x in range(len(grid)+1):
  121.         sys.stdout.write('%')
  122.     sys.stdout.write('\n')
  123.     for x in range(len(grid)):
  124.         for y in range(len(grid[0])):
  125.             '''
  126.             if grid[x][y] is True:
  127.                 sys.stdout.write('%')
  128.             elif grid[x][y] is False:
  129.                 sys.stdout.write('_')
  130.             elif grid[x][y] is 3:
  131.                 sys.stdout.write('v')
  132.             elif grid[x][y] is 2:
  133.                 sys.stdout.write('2')
  134.             if y == Y+1:
  135.                 sys.stdout.write('\n')
  136.             '''
  137.             if grid[x][y] is True:
  138.                 sys.stdout.write('&')
  139.             else:
  140.                 sys.stdout.write('_')
  141.             if y == 4:
  142.                 sys.stdout.write('\n')
  143.     for x in range(len(grid)+1):
  144.             sys.stdout.write('%')
  145.  
  146. def search(x,y,grid):
  147.     if grid[x][y] == 2:
  148.         print 'found at %d,%d' % (x,y)
  149.         return True
  150.     elif grid[x][y] == False:
  151.         print 'wall at %d,%d' % (x,y)
  152.         return False
  153.     elif grid[x][y] == 3:
  154.         print 'vistied at %d,%d' % (x,y)
  155.         return False
  156.     print 'visiting %d,%d' % (x,y)
  157.     grid[x][y] = 3
  158.     if ((x <len(grid)-1 and search(x+1,y,grid))
  159.         or (y>0 and search(x,y-1,grid))
  160.         or (x>0 and search(x-1,y,grid))
  161.         or (y< len(grid)-1 and search(x,y+1,grid))):
  162.         print grid
  163.         return True ,grid
  164.     print grid
  165.     return False
  166.  
  167.  
  168.  
  169.  
  170. def main():
  171.     mazify()
  172.     draw_maze()
  173.  
  174. if __name__ == '__main__':
  175.     main()
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