# -*- coding: utf-8 -*-
# ENGG 2440A Lecture 3 -- python code
# Requires: python3; python scipy package


from matplotlib import pyplot
from random import randint

# plot a tiling for a 2**n by 2**n grid with missing square (mx, my)
def plot_tiling(n, mx, my):
    if mx < 0 or mx > 2**n or my < 0 or my > 2**n:
        print("Empty square is outside the grid")
        return
    g = Grid(n)
    g.tile(mx, my)
    g.plot_tiling()

class Grid:
    def __init__(self, n):
        self.n = n
        self.N = 2**n
        self.tiling = [[0] * self.N for i in range(self.N)]
        self.colors = range(16, 24)
    
    # compute a tiling of the grid with missing square mx, my
    def tile(self, mx, my):
        # mark the missing square
        self.mx = mx
        self.my = my
        
        # tile the grid recursively    
        Subgrid(self, 0, 0, self.n).tile(mx, my)
             
    # add a tile with bottom left corner at (x, y) of a given shape
    # rx, ry indicates the removed corner position (0, 0), (0, 1), (1, 0) or (1, 1)
    def add_tile(self, x, y, rx, ry):
        tile_color = self._find_available_color(x, y, rx, ry)

        for i in range(0, 2):
            for j in range(0, 2):
                if (i != rx or j != ry):
                    self.tiling[x + i][y + j] = tile_color
    
    # display the computed tiling
    def plot_tiling(self):
            pyplot.imshow(self.tiling, cmap='jet', interpolation='none')
                       
    # find an available color for the current tile that does not conflict with neighboring tiles
    def _find_available_color(self, x, y, rx, ry):
        neighbors = [(rx, ry), (-1, -1), (-1, 0), (-1, 1), (-1, 2), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0), (2, -1), (1, -1), (0, -1)]
        forbidden_colors = []
        for i, j in neighbors:
            xn, yn = x + i, y + j
            if 0 <= xn and xn < self.N and 0 <= yn and yn < self.N:
                forbidden_colors.append(self.tiling[xn][yn])
        for c in self.colors:
            if not (c in forbidden_colors):
                return c       

class Subgrid(Grid):
    # instantiate a subgrid of grid with bottom left corner (x0, y0) and dimension 2**n by 2**n
    def __init__(self, grid, x0, y0, n):
        self.parent = grid
        self.x0 = x0
        self.y0 = y0
        self.n = n
        
    def tile(self, mx, my):
        if self.n == 1:
            self.add_tile(0, 0, mx, my)
        else:
            halfN = 2**(self.n - 1)

            # removed corner of central tile
            rx = mx // halfN
            ry = my // halfN
 
            for i in range(0, 2):
                for j in range(0, 2):
                    s = Subgrid(self, halfN * i, halfN * j, self.n - 1)
                    if i == rx and j == ry:
                        # tile quadrant containing removed square
                        s.tile(mx - halfN * i, my - halfN * j)
                    else:
                        # tile other quadrants
                        s.tile((1 - i) * (halfN - 1), (1 - j) * (halfN - 1))
            
            # cover central squares
            self.add_tile(halfN - 1, halfN - 1, rx, ry)
        
    def add_tile(self, x, y, rx, ry):
        self.parent.add_tile(x + self.x0, y + self.y0, rx, ry)
        
        
# play the clicker puzzle
# input the piece to be moved, 'q' to quit, 'i' to display inversions
def puzzle(show_inversions = False):
    blank = ' '
    board = [1, 2, 3, 4, 5, 6, 8, 7, blank]
    
    # play game
    while True:
        # print board
        print('\n', board[0], board[1], board[2], '\n', board[3], board[4], board[5], '\n', board[6], board[7], board[8])
        
        # print inversions
        if show_inversions:
            print('\nInversions: ', end='')
            for j in range(9):
                for i in range(j):
                    if board[i] != blank and board[j] != blank and board[i] > board[j]:
                        print('{', board[i], ',',  board[j], '}  ', end='')
            print()
            
        # make move
        move = input("Your move: ")
        try:
            move_pos = board.index(int(move))
            blank_pos = board.index(blank)
            if move_pos - blank_pos in [-3, -1, 1, 3]:
                board[blank_pos] = board[move_pos]
                board[move_pos] = blank
            else:
                print("Tile can't be moved")
        except:
            if move == 'i':
                show_inversions = not show_inversions
            elif move == 'q':
                return
            else:
                print("Incorrect input")