#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

struct GameInfo {
    int numRows;
    int numCols;
    int numColors;
};

GameInfo getDifficulty();
char**   createBoard(GameInfo gameInfo);
void     displayBoard(GameInfo gameInfo, char** board);
void     getMove (GameInfo gameInfo, int &row, int &col);
bool     legalMove(GameInfo gameInfo, char** board, int row, int col);
void     removePiece(GameInfo gameInfo, char** board, int row, int col, char chRemoving);
void     collapse   (GameInfo gameInfo, char** board);
void     compress   (GameInfo gameInfo, char** board);
bool     moveLeft   (GameInfo gameInfo, char** board);

int main () {
    cout << "Welcome to Capt Miller's Console Collapse!" << endl;
    cout << "You should maximize the console window before continuing." << endl;

    // Get difficulty info
    GameInfo gameInfo;
    gameInfo = getDifficulty();

    cout << endl << endl;
    cout << "   # of rows: "       << gameInfo.numRows   << endl;
    cout << "   # of cols: "       << gameInfo.numCols   << endl;
    cout << "   # of \"colors\": " << gameInfo.numColors << endl;

    char **board = createBoard(gameInfo);

    while (true) {
        // Get move from user
        system("cls");
        int row, col;
        displayBoard(gameInfo, board);
        
        if (!moveLeft(gameInfo,board)) {
            break;
        }

        // Loop until we have a valid move
        getMove(gameInfo, row, col);
        while (!legalMove(gameInfo, board, row, col)) {
            cout << "    Invalid move, try again." << endl;
            getMove(gameInfo, row, col);
        }

        // Remove the pieces
        removePiece(gameInfo, board, row, col, board[row][col]);
        collapse   (gameInfo, board);        
        compress   (gameInfo, board);


    }

    cout << "Game is over!  Enter any key to continue.";
    char ch;
    cin  >> ch;

    return 0;

}

// Ask user for difficulty.  Use this to set number of rows, columns, and colors
GameInfo getDifficulty()
{
    // get user's choice
    cout << "Please choose your difficulty:" << endl;
    cout << "1) Army (Super Easy)" << endl;
    cout << "2) Air Force (Pretty Slack)" << endl;
    cout << "3) Coast Guard (Almost a Challenge)" << endl;
    cout << "4) Navy/Marine (A Real Test of Your Skills)" << endl;
    int choice;
    cin >> choice;

    int numRows, numCols, numColors;

    // set difficulty based on choice
    if (choice == 1) {
        numRows   = 8;
        numCols   = 8;
        numColors = 4; 
    }
    else if (choice == 2) {
        numRows   = 10;
        numCols   = 14;
        numColors = 6; 
    }
    else if (choice == 3) {
        numRows   = 14;
        numCols   = 16;
        numColors = 8; 
    }
    else if (choice == 4) {
        numRows   = 28;
        numCols   = 26;
        numColors = 10; 
    }
    else {
        // default
        numRows   = 4;
        numCols   = 4;
        numColors = 3; 
    }

    GameInfo info;
    info.numRows = numRows;
    info.numCols = numCols;
    info.numColors = numColors;
    return info;
}



// Creates a board with rows and columns given by gameInfo.
// Fills in the board with random character based on gameInfo.numColors
char**   createBoard(GameInfo gameInfo)
{
    // Create 2D array
    char** board = new char*[gameInfo.numRows];
    for (int i=0; i<gameInfo.numRows; i++)
    {
        board[i] = new char[gameInfo.numCols];
    }

    // maps colors to displayable characters
    char tileArray[] = {2,3,5,11,14,15,21,30,35,42,43,64};

    // Fill the board
    for (int i=0; i<gameInfo.numRows; i++)
    {
        for (int j=0; j<gameInfo.numCols; j++)
        {
            // pick random color
            int color = rand() % gameInfo.numColors;

            // convert color to character from array
            char ch = tileArray[color];

            // store in board
            board[i][j] = ch;
        }
    }
    return board;
}

// Prints the game board
void     displayBoard(GameInfo gameInfo, char** board)
{
    string indentStr = "        ";

    for (int i=gameInfo.numRows-1; i >=0; i--)
    {
        cout << indentStr;

        // Print the row number
        int rowNumToPrint = i+1;
        if (rowNumToPrint < 10) {
            cout << ' ';
        }
        cout << rowNumToPrint << "|";

        // Now print character from that row
        for (int j=0; j<gameInfo.numCols; j++) {
            cout << board[i][j];
        }

        // Move to next line 
        cout << endl;
    }

    // We've printed board, but now need to print line of dashes
    cout << indentStr << "   ";
    for (int j=0; j<gameInfo.numCols; j++) {
        cout << "-";
    }
    cout << endl;


    // And finally print the letters for the columns
    cout << indentStr << "   ";
    for (int j=0; j<gameInfo.numCols; j++) {
        char ch = 'A' + j;   // 0 should go to 'A' and so forth
        cout << ch;
    }
    cout << endl;


}


// Returns true if the specified (row,col) indices are valid.
// Indices start from zero here.
bool onBoard(GameInfo gameInfo, int row, int col)
{
    if ( (row < 0) || (row >= gameInfo.numRows) || (col < 0) || (col >= gameInfo.numCols) ) {
        return false;
    }
    else {
        return true;
    }
            

}

// Read moves like (12C) repeatedly until we get something on the board
void     getMove (GameInfo gameInfo, int &row, int &col)
{
    do {
        cout << "Remove (example: A5)? ";
        char colCh;

        cin >> colCh >> row;
        row = row   - 1;     // convert row 1 to index 0
        col = colCh - 'A';   // convert col A to index 0
    } while (!onBoard(gameInfo, row, col));
}


// Returns true if (row,col) represents indices of legal piece to remove.
// Piece is legal to remove if directly adjacent to a piece of same color
bool     legalMove(GameInfo gameInfo, char** board, int row, int col)
{
    // The char to match
    char ch = board[row][col];

    // NOT a legal move if there is no piece there
    if (ch ==  ' ')
    {
        return false;
    }

    // Check up
    if (onBoard(gameInfo, row-1, col  ) && ch == board[row-1][col  ]) {
        return true;
    }
    // Check down
    if (onBoard(gameInfo, row+1, col  ) && ch == board[row+1][col  ]) {
        return true;
    }
    // Check left
    if (onBoard(gameInfo, row ,  col-1) && ch == board[row  ][col-1]) {
        return true;
    }
    // Check right
    if (onBoard(gameInfo, row  , col+1) && ch == board[row  ][col+1]) {
        return true;
    }

    // no match found, so move is no good
    return false;
}


// If (row,col) has the piece we are removing, then remove that piece (set to space)
// AND try to remove in all adjacent locations
void     removePiece(GameInfo gameInfo, char** board, int row, int col, char chRemoving)
{
    // base case -- if off board, stop
    if (!onBoard(gameInfo, row, col)) {
        return;
    }

    // OR if not the right character, stop
    if (board[row][col] != chRemoving) {
        return;
    }

    // We DO have a match -- remove the piece
    board[row][col] = ' ';

    // And try to remove from all neighbors.
    // NOTE -- won't cycle forever back where we came from b/c where we came from will have
    // a space there, not the piece we are looking for
    removePiece(gameInfo, board, row-1, col  , chRemoving);
    removePiece(gameInfo, board, row+1, col  , chRemoving);
    removePiece(gameInfo, board, row  , col-1, chRemoving);
    removePiece(gameInfo, board, row  , col+1, chRemoving);

}


// Start from the bottom (row 0): 
// Look for a space with a piece above it.  Move the piece down into the space
// Do this for the whole board
// NOTE that b/c of big gaps this DOES not do all collapsing possible.
// So we return true if any collapse happened, false otherwise
bool doSomeCollapse (GameInfo gameInfo, char** board)
{
    bool didCollapse = false;

    // Look everywhere for a space EXCEPT the very top row -- can't have a piece above it
    for (int i=0;i<gameInfo.numRows-1;i++)  // -1 here to avoid top row
    {
        for (int j=0;j<gameInfo.numCols;j++) 
        {
            if ( board[i][j] == ' ' && board[i+1][j] != ' ' ) {
                // move the piece down
                board[i][j] = board[i+1][j];

                // put space up top
                board[i+1][j] = ' ';
                didCollapse = true;
            }
        }
    }

    return didCollapse;
}

// Repeatedly collpase down pieces into spaces
void collapse(GameInfo gameInfo, char** board) 
{
    while (doSomeCollapse(gameInfo, board)) {
        // keep doing this until test fails -- then no more to collapse
    }

}


// Returns true if the specified column is all spaces
bool emptyColumn (GameInfo gameInfo, char **board, int col)
{
    for (int i=0;i<gameInfo.numRows;i++)
    {
        if (board[i][col] != ' ') {
            return false;
        }
    }
    return true;
}


// Start from the left (row 0): 
// Look for an empty column with an non-empty column to the right.  Move the non-empty column left
// Do this for the whole board
// NOTE that b/c of big gaps this DOES not do all collapsing possible.
// So we return true if any compress happened, false otherwise
bool doSomeCompress (GameInfo gameInfo, char** board)
{
    bool didCompress = false;

    // Look everywhere for empty column EXCEPT the very last column -- can't have a piece right of it
    for (int j=0;j<gameInfo.numCols-1;j++)   // -1 to skip right most column
    {
        if (emptyColumn(gameInfo,board,j) && !emptyColumn(gameInfo,board,j+1)) {
            // move whole column j+1 to j
            for (int i=0;i<gameInfo.numRows;i++) {
                board[i][j] = board[i][j+1];
            }

            // now empty the column that we moved
            for (int i=0;i<gameInfo.numRows;i++) {
                board[i][j+1] = ' ';
            }

            didCompress = true;
            
        }
    }

    return didCompress;
}

// Repeatedly collpase down pieces into spaces
void compress(GameInfo gameInfo, char** board) 
{
    while (doSomeCompress(gameInfo, board)) {
        // keep doing this until test fails -- then no more to collapse
    }

}



// Returns true if any valid moves are left
bool     moveLeft   (GameInfo gameInfo, char** board) {
    for (int i=0;i<gameInfo.numRows;i++) {
        for (int j=0;j<gameInfo.numCols;j++) {
            if (legalMove(gameInfo,board,i,j)) {
                return true;
            }
        }
    }
    return false;
}