from turtle import Turtle, Screen
from collections import deque
import numpy as np
import math
import copy

def rotate(point, angle):
    px, py = point
    angle = angle * math.pi/180.0
    qx = math.cos(angle) * px - math.sin(angle) * py
    qy = math.sin(angle) * px + math.cos(angle) * py
    return qx, qy

def dist(p1, p2):
    return math.sqrt((p2[0]-p1[0])**2+(p2[1]-p1[1])**2)

def recompute_sectors(turtle):
    cur_position = turtle.position()
    current_sectors = copy.deepcopy(turtle.current_sectors)
    min_sector_distance = 1000
    for sector in current_sectors:
        if dist(cur_position, sector) > 150:
            turtle.current_sectors.remove(sector)
        if dist(cur_position, sector) < min_sector_distance:
            min_sector_distance = dist(cur_position, sector)

    if min_sector_distance > 10:
        new_sector = cur_position
        turtle.current_sectors.add(new_sector)
        turtle.visited_sectors[new_sector] = 1

    for sector in turtle.visited_sectors:
        if sector not in turtle.current_sectors and dist(cur_position, sector) < 10:
            turtle.visited_sectors[sector] += 1
            turtle.current_sectors.add(sector)

    near_pt = int(cur_position[0]), int(cur_position[1])
    if near_pt in turtle.point_visits:
        turtle.point_visits[near_pt] += 1
    else:
        turtle.point_visits[near_pt] = 1

    cur_color = turtle.color()
    if near_pt in turtle.point_colors:
        turtle.point_colors[near_pt].add(cur_color)
    else:
        turtle.point_colors[near_pt] = set(cur_color)

def validate_sectors(turtle):
    result = True
    for sector in turtle.visited_sectors:
        if turtle.visited_sectors[sector] > 6:
            result = False

    for near_pt in turtle.point_visits:
        if turtle.point_visits[near_pt] > 6:
            result = False

    for near_pt in turtle.point_colors:
        if len(turtle.point_colors[near_pt]) > 4:
            result = False

    #print turtle.position(), turtle.visited_sectors, turtle.point_visits, turtle.point_colors, result
    return result

def validate_position(turtle):
    p = turtle.position()
    new_allowed_rotations = []
    for r in turtle.allowed_rotations:
        _, y = rotate(p, r)
        if y < 10.1 and y > -10.1:
            new_allowed_rotations.append(r)
    if not new_allowed_rotations:
        return False
    turtle.allowed_rotations = new_allowed_rotations

    return True

def process_line(l, turtle):
    items = deque(l.split(" "))
    num_actions = 0
    travel_distance = 0
    success = True
    while items:
        if items[0] == "pd":
            if turtle.isdown():
                num_actions -= 1
                #success = False
            turtle.pendown()
            turtle.moves.append(items[0])
        elif items[0] == "pu":
            if not turtle.isdown():
                num_actions -= 1
                #success = False
            turtle.penup()
            turtle.moves.append(items[0])
        elif items[0] == "co":
            turtle.pencolor(items[1])
            turtle.moves.append((items[0], items[1]))
            items.popleft()
        elif items[0] == "fd":
            turtle.forward(int(items[1]))
            turtle.moves.append((items[0], items[1]))
            turtle.travel_distance += int(items[1])
            travel_distance += int(items[1])
            recompute_sectors(turtle)
            success = success and validate_position(turtle) and validate_sectors(turtle)
            items.popleft()
        elif items[0] == "bk":
            turtle.backward(int(items[1]))
            turtle.moves.append((items[0], items[1]))
            turtle.travel_distance += int(items[1])
            travel_distance += int(items[1])
            success = success and validate_position(turtle) and validate_sectors(turtle)
            items.popleft()
        elif items[0] == "lt":
            turtle.left(int(items[1]))
            turtle.moves.append((items[0], items[1]))
            items.popleft()
        elif items[0] == "rt":
            turtle.right(int(items[1]))
            turtle.moves.append((items[0], items[1]))
            items.popleft()
        else:
            assert False, items[0]
        items.popleft()
        num_actions += 1
        if not success:
            break
    return success, num_actions, travel_distance


def try_to_finish(turtle, sofar):
    endline = "lt 120 pu fd 10 pd fd 10 rt 60 pu fd 30 pd rt 120 fd 20 pu lt 120 fd 40"
    finish_success, finish_numactions, travel_distance = process_line(endline, turtle) # TODO travel distance
    if finish_success:
        print("Solution: ", sofar)
    else:
        print("Finish failed")
        for i in range(finish_numactions):
            turtle.undo()

def backtrack(turtle, num_actions, allowed_rotations, travel_distance, visited_sectors, current_sectors, point_visits, moves, point_colors):
    for i in range(num_actions):
        turtle.undo()
    turtle.allowed_rotations = allowed_rotations
    turtle.travel_distance -= travel_distance
    turtle.visited_sectors = visited_sectors
    turtle.current_sectors = current_sectors
    turtle.point_visits = point_visits
    turtle.moves = moves
    turtle.point_colors = point_colors

def iterate(turtle, lines, sofar, depth=0):

    allowed_rotations = copy.deepcopy(turtle.allowed_rotations)
    visited_sectors = copy.deepcopy(turtle.visited_sectors)
    current_sectors = copy.deepcopy(turtle.current_sectors)
    point_visits = copy.deepcopy(turtle.point_visits)
    point_colors = copy.deepcopy(turtle.point_colors)
    moves = copy.deepcopy(turtle.moves)
    yertle.sofar = sofar
    for l in lines:
        success, num_actions, travel_distance = process_line(l, turtle)
        if success:
            remaining = [ol for ol in lines if l != ol]
            if len(remaining) < 4:
                print len(remaining), turtle.travel_distance
            if len(remaining) == 0:
                print turtle.moves
                print sofar
                clickHandler(0, 0)
            sofar.append((l, num_actions, allowed_rotations))
            iterate(turtle, remaining, sofar, depth+1)
        backtrack(turtle, num_actions, allowed_rotations, travel_distance, visited_sectors, current_sectors, point_visits, moves, point_colors)


startlines = [
    "co blue pd rt 30 fd 10 bk 10 lt 120 fd 10 lt 60 pu fd 10",
#    "pd fd 10 pu fd 10 pd fd 10 bk 10 lt 60 fd 10 lt 120 pu fd 20 pd fd 10 pu bk 50", # 6
#    "bk 10 rt 60 fd 10 lt 120 fd 20 rt 120 pu fd 10 pd lt 120 fd 10 rt 60", # 1
#    "fd 10 pu fd 10 pd fd 10 rt 60 fd 10 rt 120 fd 10 rt 60 fd 10 rt 120 pu fd 20", # 3
#    "fd 10 pd rt 60 fd 20 co cyan lt 120 fd 20 rt 60 pu fd 20 pd rt 120 fd 10 bk 10", # 2
]

midlines = [
    "bk 10 rt 60 fd 10 lt 120 fd 20 rt 120 pu fd 10 pd lt 120 fd 10 rt 60", # 1
    "fd 10 pd rt 60 fd 20 co cyan lt 120 fd 20 rt 60 pu fd 20 pd rt 120 fd 10 bk 10", # 2
    "fd 10 pu fd 10 pd fd 10 rt 60 fd 10 rt 120 fd 10 rt 60 fd 10 rt 120 pu fd 20", # 3
    "lt 60 fd 10 pu bk 20 co magenta pd fd 10 rt 60 pu fd 20 pd lt 60 fd 10 rt 60 pu", # 4
    "pd bk 10 lt 60 pu fd 20 pd rt 60 fd 10 lt 60 pu bk 10 pd rt 60 bk 10 fd 10 co white", # 5
    "pd fd 10 pu fd 10 pd fd 10 bk 10 lt 60 fd 10 lt 120 pu fd 20 pd fd 10 pu bk 50", # 6
    "pd fd 10 rt 60 pu fd 10 pd rt 60 fd 20 bk 10 lt 60 bk 10 pu fd 20 pd fd 10", # 7
    "pd lt 120 fd 10 pu fd 40 pd lt 120 fd 20 rt 120 pu fd 40 pd rt 60 fd 20", # 8
    "pu fd 10 rt 60 fd 60 pd fd 10 pu fd 40 pd rt 180 co green fd 20 lt 60 pu fd 10", # 9
    "pu fd 20 pd rt 60 fd 10 co red fd 10 lt 120 fd 10 lt 60 fd 10 bk 10 lt 60", # 10
    "rt 120 pu fd 30 pd rt 120 fd 10 bk 10 lt 120 pu fd 70 pd rt 120 co yellow fd 10", # 11
    "rt 60 pu fd 10 pd lt 60 fd 10 rt 60 pu fd 10 pd fd 10 pu fd 20 pd rt 60 fd 10" #12
]


yertle = Turtle(visible=False)
def clickHandler(a, b):
    print(yertle.sofar)
    print(yertle.moves)
    input('Press a key')

if __name__ == "__main__":
    screen = Screen()
    screen.bgcolor("black")
    screen.onclick(clickHandler)
    yertle.speed('fastest')
    yertle.penup()
    yertle.allowed_rotations = np.arange(30, 31, 1)
    yertle.travel_distance = 0
    yertle.moves = []
    yertle.current_sectors = set()
    yertle.visited_sectors = dict()
    yertle.point_visits = dict()
    yertle.point_colors = dict()
    yertle.sofar = None
    for l in startlines:
        process_line(l, yertle)
    iterate(yertle, midlines, [])
    screen.exitonclick()