#!/usr/bin/env python

from puzzle_data import *
import copy

def set_to_list(board):
    """
    convert the set of points to a list
    """
    max_r = max(r for r, c in board) +1
    max_c = max(c for r, c in board) +1
    _board = [["x"] * max_c for _ in range(max_r)]
    for pts in board:
        _board[pts[0]][pts[1]] = -1
    return _board

def shape_to_list(shape, board, _id):
    for pts in shape:
        board[pts[0]][pts[1]] = _id
    return board

def valid_points(board_list):
    _pts = set()
    for row in range(len(board_list)):
        for col in range(len(board_list[0])):
            if board_list[row][col] == -1:
                _pts.add( (row,col) )
    return _pts

def print_board(board):
    print("\n---")
    for row in board:
        print( " ".join( map(str, row) ) )
    print("\n---")

def normalize(cells):
    min_r = min(r for r, c in cells)
    min_c = min(c for r, c in cells)
    return frozenset((r - min_r, c - min_c) for r, c in cells)

def rotate_cw(cells):
    # (r, c) -> (c, -r) is a 90° clockwise rotation
    return normalize({(c, -r) for r, c in cells})

def flip_h(cells):
    # mirror left-right: negate the column
    return normalize({(r, -c) for r, c in cells})

def flip_v(cells):
    # mirror top-bottom: negate the row
    return normalize({(-r, c) for r, c in cells})

def all_orientations(shape):
    seen = set()
    current = normalize(shape)
    for _ in range(4):
        current = rotate_cw(current)
        seen.add(current)
        seen.add(flip_h(current))
    return seen

def all_board_positions(shape,board):
    """
    given a shapes and board, return all the locations that this shape fits
    """
    positions = []
    # loop through every point on the board and try to apply the shape to it
    for point in board:
        r,c = point

        valid = True
        for _pt in [ (_r+r, _c+c) for _r,_c in shape ] :
            if not _pt in board:
                valid = False
                break

        if valid:
            #show_on_board(shape, board,r,c)
            positions.append( [ (_r+r, _c+c) for _r,_c in shape ]  )
            #print()

    return positions


def apply(board, orientation, position, shape_num):
    """
    apply a piece at a position to the board and return the board as a list
    """
    #b = copy.deepcopy(board)
    b = [row[:] for row in board]
    for p in [(row+ position[0], col+position[1]) for row,col, in orientation]:
         b[p[0]][p[1]] = shape_num
    return b
                
def solve(shape_num, board):
    if shape_num >= len(shapes):
        print("out of shapes", shape_num )
        print_board( board)
        return True

    #_or = all_orientations(shapes[shape_num])
    _or = or_list[shape_num]

    # get all the valid points on the board
    valid_pts = valid_points(board)
    if len(valid_pts) == 0:
            print("No positions left", shape_num)
            print_board(board)
            return False

    # loop through all the shapes and their orientations
    for orientation in _or:
        for position in valid_pts:
            # check to see if the orientation can fit in this position, if it can, then apply it to the board and go to the next piece.
            if all( (row+ position[0], col+position[1]) in valid_pts for row,col, in orientation):
                if solve( shape_num +1 , apply(board, orientation, position, shape_num) ):
                    return True
                
    return False

or_list = []
for i in range(len(shapes)):
    or_list.append( all_orientations(shapes[i]) )

solve(0, set_to_list(board - {(1,0), (4,3)}))

# list_board = set_to_list(board)
# list_board = shape_to_list( shapes[0], list_board, 1)
# print_board(  list_board)
#
# for shape in shapes:
#     for orientation in all_orientations(shape):
#         for positions in all_board_positions(orientation, board - {(1,1), (2,4)} ): #subtract month and day position from board
#         print("----")
#         show(orientation)
#         #all_board_positions(orientation, board - {(1,1), (2,4)} ) #subtract month and day position from board
#         print("----------")