import random
import copy

BLANK = 0
GRID_SIZE = 4
VALID_KEYS = ['W', 'A', 'S', 'D', 'Q']
MAX_TILE = 64

# Constants for messages
USER_PROMPT = "Enter move (W/A/S/D/Q): "
INVALID_INPUT_MSG = "Invalid input, try again."
GAME_OVER_MSG = "Game Over!"
YOU_WIN_MSG = "You Win!"
QUITTING_MSG = "Quitting the game."


def check_grid(grid):
    """
    Validate that the grid is a proper 4x4 2048 grid.

    Conditions checked:
        - grid is a list of 4 lists
        - each row has 4 elements
        - each cell is either BLANK (0) or a power of 2 between 2 and MAX_TILE (inclusive)

    Raises:
        TypeError: if grid is not a list of lists
        ValueError: if grid dimensions are incorrect or contains invalid values
    """
    if not isinstance(grid, list):
        raise TypeError("Grid must be a list")

    if len(grid) != GRID_SIZE:
        raise ValueError(f"Grid must have {GRID_SIZE} rows")

    valid_values = {BLANK} | {
        2 ** i for i in range(1, MAX_TILE.bit_length() + 1) if 2 ** i <= MAX_TILE}

    for row_idx, row in enumerate(grid):
        if not isinstance(row, list):
            raise TypeError(f"Row {row_idx} must be a list")
        if len(row) != GRID_SIZE:
            raise ValueError(f"Row {row_idx} must have {GRID_SIZE} columns")

        for col_idx, cell in enumerate(row):
            if cell not in valid_values:
                raise ValueError(
                    f"Invalid value '{cell}' at position ({row_idx}, {col_idx})")

    return True


def display_grid(grid):
    """
    Prints the current game grid as a multiline string in the console.

    Each cell is printed as a box 4 characters wide and 3 lines tall.
    Numbers are centered using str.center(4), BLANK cells show as empty.
    """
    check_grid(grid)
    horizontal_line = '+----' * GRID_SIZE + '+'
    lines = []

    for row in grid:
        lines.append(horizontal_line)
        lines.append('|    ' * GRID_SIZE + '|')
        cells = '|'.join(
            [str(cell if cell != BLANK else '').center(4) for cell in row])
        lines.append('|' + cells + '|')
        lines.append('|    ' * GRID_SIZE + '|')

    lines.append(horizontal_line)

    print('\n'.join(lines) + '\n')


def init_grid():
    """
    Create and return an empty 4x4 game grid.

    Returns:
        list: A 2D list of size 4x4 filled with BLANK.

    Example:

    init_grid() returns ->
        [
            [0, 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 0, 0],
            [0, 0, 0, 0]
        ]
    """
    pass


def get_user_input():
    """
    Read and validate player input for a move.

    Returns:
        str: One of 'W', 'A', 'S', 'D', 'Q'

    Behavior:
        - Prompt: "Enter move (W/A/S/D/Q): "
        - Case insensitive and ignores surrounding spaces.
        - Repeats until a valid input is given.

    Example:
        Enter move (W/A/S/D/Q): x
        Invalid input, try again.
        Enter move (W/A/S/D/Q):   a  
        -> returns 'A'
    """
    pass


def move(grid, direction):
    """
    Shift and merge tiles in the given direction.

    Inputs:
        grid (list): Current 4x4 grid with BLANKs for empty cells.
        direction (str): 'W', 'A', 'S', or 'D'

    Returns:
        list: Grid after applying the move. Can be the same object modified or a new one.

    Example:
        grid = [
            [2, 0, 2, 0],
            [4, 4, 4, 4],
            [0, 0, 0, 0],
            [0, 2, 16, 2]
        ]

        move(grid, 'A') returns -> 
        [
            [4, 0, 0, 0],
            [8, 8, 0, 0],
            [0, 0, 0, 0],
            [2, 16, 2, 0]
        ]
    """
    pass


def get_empty_positions(grid):
    """
    Return a list of all empty positions in the grid.

    Returns:
        list: list of tuples (row, col) for empty cells.

    Example:
        grid = [
            [2, 0, 0, 4],
            [0, 2, 2, 16],
            [0, 4, 64, 0],
            [4, 0, 32, 0]
        ]
        -> [(0,1),(0,2),(1,0),(2,0),(2,3),(3,1),(3,3)]
    """
    pass


def add_new_tile(grid):
    """
    Add a new tile 2 to a random empty position in the grid.

    Steps:
        - Get empty positions using get_empty_positions(grid)
        - Choose one randomly
        - Set that position to 2
    """
    pass


def can_move(grid):
    """
    Check if any move is possible.

    A move is possible if:
        - There is at least one BLANK cell
        - OR two adjacent tiles (horizontally or vertically) have the same value

    Returns:
        bool: True if a move is possible, False otherwise.

    Example:
        grid = [
            [2, 4, 2, 8],
            [8, 16, 8, 2],
            [4, 2, 16, 4],
            [2, 8, 4, 2]
        ]
        -> False

        grid = [
            [2, 4, 2, 8],
            [8, 0, 8, 2],
            [4, 2, 16, 4],
            [2, 8, 4, 2]
        ]
        -> True
    """
    pass


def game_won(grid):
    """
    Returns True if the grid contains at least one MAX_TILE value.

    Returns:
        bool: True if a cell equals MAX_TILE, False otherwise.

    Example:
    grid = [
        [2, 4, 2, 8],
        [8, 16, 8, 2],
        [4, 2, 64, 4],
        [2, 8, 4, 2]
    ]
    -> True

    grid = [
        [2, 4, 2, 8],
        [8, 0, 8, 2],
        [4, 2, 16, 4],
        [2, 8, 4, 2]
    ]
    -> False
    """
    pass


def main():
    """
    Main game loop for 2048.

    Steps:
        1. Initialize grid and add two 2s randomly.
        2. Loop:
            - Display the grid
            - Check if moves are possible (can_move)
            - Ask for user input (get_user_input)
            - If user inputs 'Q', quit the game
            - Apply move (move)
            - If player has won (game_won), print "You Win!" and exit
            - Add new tile only if move changed the grid
        3. When no moves possible, print "Game Over".
    """
    pass


if __name__ == "__main__":
    """
    Main entry point to start the 2048 game. 
    The code of your main function should all be inside the main() function above.
    You are allowed to write test code here to test individual functions if you want, 
    only your main function will be graded.
    """
    main()