# -*- coding: utf-8 -*-
maze = [[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
        [-1, 0, 0, 0,-1, 0, 0, 0,-1,-1, 0,-1,-1, 0, 0, 0, 0, 0, 0, 0, 0,-1,],
        [ 0, 0, 0, 0, 0, 0,-1, 0, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
        [-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1,-1,-1, 0,-1,-1,-1, 0,-1,-1,],
        [-1, 0,-1, 0, 0, 0,-1, 0,-1, 0,-1,-1, 0, 0, 0, 0,-1,-1,-1, 0, 0,-1,],
        [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1, 0, 0,-1, 0,-1,],
        [-1,-1,-1,-1,-1, 0,-1, 0,-1, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,-1, 0,-1,],
        [-1,-1,-1,-1,-1, 0,-1,-1,-1, 0, 0,-1, 0,-1, 0, 0,-1,-1, 0, 0, 0,-1,],
        [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0,-1, 0, 9,-1, 0,-1, 0, 0,-1,],
        [-1,-1,-1,-1,-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0, 0, 0, 0, 0,-1, 0,-1,],
        [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,]]

"""The above maze is simple. We have obstacles = -1, 0 is an unexplored path, and 9 is the starting point. If we hit the path we want to take, we can give it a value of 3.

We will start at *9* and move until we are outside of the bounds of the maze. Getting the bounds should be easy enough, just use the shape function built into numpy arrays. So if our position $x == 0$ or $y==0$, or $x = x_{bound}$ or $y = y_{bound}$. Lots of options.

"""

import numpy as np
import matplotlib.pyplot as plt

import time
from IPython.display import display, clear_output

mmaze = np.array(maze)
y_b, x_b = mmaze.shape
print(mmaze)
plt.pcolor(mmaze[-1::-1,:])
plt.axis('equal')
plt.axis('off')
plt.show()

y, x = np.where(mmaze == 9)
#Get the starting position

fig = plt.figure()

def move(maze, y, x):
    global fig
    #  run into an obstacle, return false
    if maze[y, x] == -1 :
        return False
    #  run into a square explored, on the path, or dead end
    if maze[y, x] == 1 or maze[y, x] == 2 or maze[y, x] == 3:
        return False
    # Success, an outside edge not occupied by an obstacle
    if x==0 or y == 0 or x >= maze.shape[1] or y >= maze.shape[0]:
        try:
            maze[y,x] = 3
        except:
            print("YOU'RE OUTSIDE!")
        return True
    maze[y,x] = 1

    # Otherwise, use logical short circuiting to try each
    # direction in turn (if needed)
    found = move(maze, y, x+1) or \
            move(maze, y-1, x) or \
            move(maze, y, x-1) or \
            move(maze, y+1, x)
    plt.pcolor(maze[-1::-1,:])
    plt.axis('equal')
    plt.axis('off')

    display(fig)
    clear_output(wait = True)
    plt.pause(1e-1)
    if found:
        maze[y,x] = 3 # This is the path we wanna follow
    else:
        maze[y,x] = 2 #dead end
    return found

"""
Lets run our code on the maze code above and see what happens!
"""

mmaze = np.array(maze)
y, x = np.where(mmaze == 9)
move(mmaze,y,x)

"""The cells in the map above have *Moore* connectivity. This means from your postion you can travel *north, south, east, or west*.

A *Neumann* neighborhood adds in the four additional directions *north-east, south-east, south-west, and north-west*. How can you modify the above function to incorporate the *Neumann* neighborhood?

**Task 1 (30 points)**
"""

def move_neu(maze,y,x):
    global fig
    #  run into an obstacle, return false
    if maze[y, x] == -1 :
        return False
    #  run into a square explored, on the path, or dead end
    if maze[y, x] == 1 or maze[y, x] == 2 or maze[y, x] == 3:
        return False
    # Success, an outside edge not occupied by an obstacle
    if x==0 or y == 0 or x >= maze.shape[1] or y >= maze.shape[0]:
        try:
            maze[y,x] = 3
        except:
            print("YOU'RE OUTSIDE!")
        return True
    maze[y,x] = 1

    # Otherwise, use logical short circuiting to try each
    # direction in turn (if needed)
    found = move_neu(maze, y+1, x+1) or \
            move_neu(maze, y, x+1) or \
            move_neu(maze, y-1, x+1) or \
            move_neu(maze, y-1, x) or \
            move_neu(maze, y-1, x-1) or \
            move_neu(maze, y, x-1) or \
            move_neu(maze, y+1, x-1) or\
            move_neu(maze, y+1, x)

    plt.pcolor(maze[-1::-1,:])
    plt.axis('equal')
    plt.axis('off')

    display(fig)
    clear_output(wait = True)
    plt.pause(1e-1)
    if found:
        maze[y,x] = 3 # This is the path we wanna follow
    else:
        maze[y,x] = 2 #dead end
    return found

mmaze = np.array((maze))
y, x = np.where(mmaze == 9)
print(f"Starting move_neu with x={x} and y={y}")
move_neu(mmaze,y,x)

"""** Task 2 (20 Points) **
Make another maze. Programmatically or by modifying the above maze.

Alter the order of moves in the move function and measure the time it takes to solve the maze. Is there an optimal order of operations?

***Hint: use %timeit and kill the plotting ***
"""
# nue maze made by me
maze = [[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,],
        [-1, 0, 0, 0,-1, 0, 0, 0,-1,-1, 0,-1,-1, 0, 0, 0, 0, 0, 0, 0, 0,-1,],
        [ -1, 0, 0, 0, 0, 0,-1, 0, 0, 0, 0, 0,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,],
        [-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1,-1,-1, 0,-1,-1,-1, 0,-1,-1,],
        [-1, 0,-1, 0, 0, 0,-1, 0,-1, 0,-1,-1, 0, 0, 0, 0,-1,-1,-1, 0, 0,-1,],
        [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,-1,-1, 0, 0,-1, 0,-1,],
        [0,0,-1,-1,-1, 0,-1, 0,-1, 0, 0, 0, 0, 0, 0,-1,-1, 0, 0,-1, 0,-1,],
        [-1,-1,-1,-1,-1, 0,-1,-1,-1, 0, 0,-1, 0,-1, 0, 0,-1,-1, 0, 0, 0,-1,],
        [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0,-1, 0, 9,-1, 0,-1, 0, 0,-1,],
        [-1,-1,-1,-1,-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0, 0, 0, 0, 0,-1, 0,-1,],
        [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,]]


from time import time

def move_rdlu(maze, x, y, order):

    #  run into an obstacle, return false
    if maze[y, x] == -1 :
        return False
    #  run into a square explored, on the path, or dead end
    if maze[y, x] == 1 or maze[y, x] == 2 or maze[y, x] == 3:
        return False
    # Success, an outside edge not occupied by an obstacle
    if x==0 or y == 0 or x >= maze.shape[1] or y >= maze.shape[0]:
        try:
            maze[y,x] = 3
        except:
            print("YOU'RE OUTSIDE!")
        return True
    maze[y,x] = 1

    # Otherwise, use logical short circuiting to try each
    # direction in turn (if needed)
    found = move_rdlu(maze, x + order[0][0], y + order[0][1], order) or \
            move_rdlu(maze, x + order[1][0], y + order[1][1], order) or \
            move_rdlu(maze, x + order[2][0], y + order[2][1], order) or \
            move_rdlu(maze, x + order[3][0], y + order[3][1], order)
    if found:
        maze[y,x] = 3 # This is the path we wanna follow
    else:
        maze[y,x] = 2 #dead end
    return found

# This is all 24 possible combinations (taken from google)
moves = ["rlud", "rldu", "rdlu", "drlu", "ruld", "rudl", "rdul", "drul",
         "urld", "urdl", "udrl", "durl", "lrud", "lrdu", "ldru", "dlru",
         "lurd", "ludr", "ldur", "dlur", "ulrd", "uldr", "udlr", "dulr"]

# These are the numbers that have to be added based on their direction
directions = {
	"r": (1, 0),
	"l": (-1, 0),
	"u": (0, 1),
	"d": (0, -1)
}

# using a dictionary for timing so I can easily do multiple tests
times = dict((move,0) for move in moves)


# for each move calculate a list of addition tuples in order and then run
n = 30
for i in range(n):
    for move in moves:
        mmaze = np.array((maze))
        y, x = np.where(mmaze == 9)
        order = []
        for l in move:
            order.append(directions[l])

        t0 = time()
        move_rdlu(mmaze,x,y, order)
        t1 = time()-t0
        times[move] += t1

for k in times:
    times[k] /= n

times = list(times.values())

print(times)
fig = plt.figure()
plt.bar(moves, times, figure=fig) # purdy graf
plt.show()

"""** Task 3 (50 Points) **

Plagarized from a class on Haskel at Stanford [http://nifty.stanford.edu/2018/stephenson-mondrian-art/Handout_Fall.pdf] We are not doing the same problem, but something similar.

Piet Mondrian (March 7, 1872 – February 1, 1944) was a Dutch painter who created numerous famous
paintings in the early half of the previous century that consisted of a white background, prominent black
horizontal and vertical lines, and regions colored with red, yellow and blue. Three examples are shown
Below is included some boiler plate code to setup a plot employing patches of rectangles onto a 1000 x 800 pixel image.

You need to write a code which will recursively divide the *Canvas* and *paint* each portion of the *canvas*.

It is your choice when to stop dividing the domain and how to paint each of the sections.

You do not need to limit your color pallette or how far down you recurse (though sub pixel division will not produce a change).

In order to get full marks you need to define a series of functions which will recursively produce some **art**.

Thorough comments throughout your code will have a large effect on your final grade. Clearly mark out your base case for recursion. Define any design choices explicitly (i.e. if a sub-divided region is to narrow it merges with a neighbor). If you use a **magic-number**, state why. If you are implementing a random number, why? If using RNG, can you seed it and consistently recreate your art?
"""

import random
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle, Circle

from IPython.display import display, clear_output
plt.rcParams["figure.figsize"] = (10,10)
fig = plt.figure()
domain = (1000,800)
plt.xlim(0,domain[0])
plt.ylim(0,domain[1])
plt.axis('off')
ax = fig.gca()

rects = [Rectangle((50, 100), 400, 320, linewidth=1, edgecolor='r', facecolor='r'),
         Rectangle((125, 500), 100, 200, linewidth=1, edgecolor='k', facecolor='g'),
         Rectangle((625, 10), 290, 50, linewidth=11, edgecolor='k', facecolor='b'),
         Rectangle((725, 600), 75, 150, linewidth=5, edgecolor='g', facecolor='m')]
[ax.add_patch(rect) for rect in rects]

plt.show()

def rectangles(x0, x1, y0, y1):
    """ This Generates nices squares with circles that make what lookes like
        snowy clouds. I like it"""
    # base case because pixels get too tiny
    if (x1-x0)*(y1-y0) < 16*16:
        return False
    else:
        # 2 is a nice number and doesn't leave blanks
        xmid = (x1+x0) // 2
        ymid = (y1+y0) // 2

        width = (x1-x0) // 2
        height = (y1-y0) // 2

        rects = [Rectangle((x0, y0), width, height, linewidth=1, edgecolor='k', facecolor='r'),
                 Rectangle((xmid, ymid), width, height, linewidth=1, edgecolor='k', facecolor='g'),
                 Rectangle((x0, ymid), width, height, linewidth=1, edgecolor='k', facecolor='b'),
                 Rectangle((xmid, y0), width, height, linewidth=1, edgecolor='k', facecolor='m'),
                 Circle((xmid, y1), width//2, linewidth=1, edgecolor='k', facecolor="w") # circle needs to be smaller so you can see squares
                 ]
        [ax.add_patch(rect) for rect in rects]

        show = False # Set this equal to True if you want to see it generate step by step
        if show:
            display(fig)
            clear_output(wait = True)
            plt.pause(1e-15)


        rectangles(x0, xmid, y0, ymid)
        rectangles(xmid, x1, ymid, y1)
        rectangles(x0, xmid, ymid, y1)
        rectangles(xmid, x1, y0, ymid)

plt.rcParams["figure.figsize"] = (10,10)
fig = plt.figure()
domain = (1024, 1024)
plt.xlim(0,domain[0])
plt.ylim(0,domain[1])
plt.axis('off')
ax = fig.gca()
print("STARTING")
rectangles(0, domain[0], 0, domain[1])
plt.savefig('SnowyCloudsInAPlaidSky.png')
plt.show()