###maze3.py

import random
import sys
import numpy
X = 2
Y = 2

indicies = numpy.arange(X*Y).reshape(X,Y) # creates X by Y array from 0 to X*Y
rightwalls = numpy.ones(X*Y,bool)   #creates X * Y list of TRUE
downwalls = numpy.ones(X*Y,bool)    #likewise

def generate_walls():

    #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 ]
    TotalRightWalls = (X-1)*Y
    TotalDownWalls = (Y-1)*X
    TotalWalls = TotalRightWalls+TotalDownWalls
    print TotalWalls

    walls = numpy.empty((TotalWalls,3),int) #numpy.empty returns non-zeroed array CAREFUL!
    walls[:TotalRightWalls,0] = indicies[:-1:].flatten() #90 elements 0-90
    walls[:TotalRightWalls,1] = indicies[:,1:].flatten() #90 elements 0-100 skipping multiples of 10, second row
    walls[:TotalRightWalls,2] = True # third row 90 ones

    walls[TotalRightWalls:,0] = indicies[:,:-1].flatten()
    walls[TotalRightWalls:,1] = indicies[:,1:].flatten()
    walls[TotalRightWalls:,2] = False

    return walls

class UnionFind(object):
    def __init__(self,sections):
        self.parent = numpy.arange(sections)
        self.rank = numpy.ones(sections)
        self.final = numpy.ones(sections,bool)

    def find(self,a):
        parents = self.parent
        parent = parents[a]
        if not self.final[parent]:
            parent=  self.find(parent)
            parents[a]= parent
        return parent

    def union(self,a,b):
        find = self.find
        a_par = find(a)
        b_par = find(b)
        if a_par != b_par:
            rank = self.rank
            parent = self.parent
            final = self.final
            a_rank = rank[a_par]
            b_rank = rank[b_par]
            if a_rank < b_rank:
                parent[a_par] = b_par
                final[a_par] = False
            elif b_rank < a_rank:
                parent[b_par] = a_par
                final[b_par] = False
            else:
                parent[b_par] = a_par
                final[b_par] = False
                rank[a_par] += 1
            return True
        else:
            return False

def mazify():
    walls = generate_walls()
    numpy.random.shuffle(walls)
    uf = UnionFind(X*Y)
    for parent, neighbor, right in walls:
        if uf.union(parent,neighbor):
            if right:
                rightwalls[parent] = False
            else:
                downwalls[parent] = False


def output(blocked):
    sys.stdout.write( " @"[blocked])
    if blocked:
        pass
def draw_maze():
    lst = []
    for x in range(2*X+1):
        output(True) #top lines
    sys.stdout.write('\n')
    for y in xrange(Y):
        output(True)    #left lines
        lst.append(True)
        for x in xrange(X):
            lst.append(False)
            lst.append(rightwalls[indicies[x,y]])
            output(False)
            output(rightwalls[indicies[x,y]])
        sys.stdout.write('\n')
        lst.append(True)
        output(True)
        for x in xrange(X):
            lst.append(downwalls[indicies[x,y]])
            lst.append(True)
            output(downwalls[indicies[x,y]])
            output(True)
        sys.stdout.write('\n')

    lst2=[]
    for x in range(len(lst)):
        lst2.append(lst[x])
    step = 2*X+1
    a = []
    for i in range(0,len(lst2),step):
        a.append(lst2[i:i+step])
    a[len(a)-1][2*X-1]=2
    #a[1][1] = 2
    print a
    junk,grid = search(0,0,a)
    for x in range(len(grid)+1):
        sys.stdout.write('%')
    sys.stdout.write('\n')
    for x in range(len(grid)):
        for y in range(len(grid[0])):
            '''
            if grid[x][y] is True:
                sys.stdout.write('%')
            elif grid[x][y] is False:
                sys.stdout.write('_')
            elif grid[x][y] is 3:
                sys.stdout.write('v')
            elif grid[x][y] is 2:
                sys.stdout.write('2')
            if y == Y+1:
                sys.stdout.write('\n')
            '''
            if grid[x][y] is True:
                sys.stdout.write('&')
            else:
                sys.stdout.write('_')
            if y == 4:
                sys.stdout.write('\n')
    for x in range(len(grid)+1):
            sys.stdout.write('%')

def search(x,y,grid):
    if grid[x][y] == 2:
        print 'found at %d,%d' % (x,y)
        return True
    elif grid[x][y] == False:
        print 'wall at %d,%d' % (x,y)
        return False
    elif grid[x][y] == 3:
        print 'vistied at %d,%d' % (x,y)
        return False
    print 'visiting %d,%d' % (x,y)
    grid[x][y] = 3
    if ((x <len(grid)-1 and search(x+1,y,grid))
        or (y>0 and search(x,y-1,grid))
        or (x>0 and search(x-1,y,grid))
        or (y< len(grid)-1 and search(x,y+1,grid))):
        print grid
        return True ,grid
    print grid
    return False




def main():
    mazify()
    draw_maze()

if __name__ == '__main__':
    main()