#include <iostream>
#include <random>

enum Direction {
    UP = 0,
    RIGHT,
    DOWN,
    LEFT
};

template <int S>
class Grid
{
private:
    std::random_device rd;
    std::mt19937 gen;

    bool fillABlank()
    {
        if (numBlanks == 0) {
            return( false );
        }

        std::uniform_int_distribution<> dis(1, numBlanks);
        std::uniform_int_distribution<> disBlock(0, 4);

        int sq = dis(gen);

        for (int r = 0; r < S && sq; r++) {
            for (int c = 0; c < S; c++) {
                if (!squares[r][c] && !--sq) {
                    squares[r][c] = !disBlock(gen) ? 2 : 1;
                    numBlanks--;
                    break;
                }
            }
        }

        return( true );
    }

public:
    int squares[S][S];
    int numBlanks;

    Grid()
        : numBlanks(S*S)
    {
        for (int r = 0; r < S; r++) {
            for (int c = 0; c < S; c++) {
                squares[r][c] = 0;
            }
        }

        fillABlank();
    }

    bool print()
    {
        std::cout.width(2);
        std::cout.fill(' ');

        for (int r = 0; r < S; r++) {
            for (int c = 0; c < S; c++) {
                std::cout.width(2);
                std::cout.fill(' ');
                if (squares[r][c])
                    std::cout << squares[r][c] << " | ";
                else
                    std::cout << "   | ";
            }

            std::cout << "\n";
            std::cout.width(5*S);
            std::cout.fill('-');
            std::cout << ' ' << std::endl;
        }

        return( true );
    }

    int& dirAccess(int r, int c, Direction d)
    {
        switch (d) {
        case UP:
            return squares[r][c];
        case DOWN:
            return squares[S-r-1][S-c-1];
        case RIGHT:
            return squares[c][S-r-1];
        case LEFT:
            return squares[S-c-1][r];
        }
    }

    bool canMove()
    {
        if (numBlanks) {
            return( true );
        }

        // Can move if there are any adjacent blocks of the same value.

        for (int c = 0; c < S; c++) {
            for (int r = 0; r < S; r++) {
                if (!squares[r][c]) {
                    continue;
                }

                if ( (r && squares[r][c] == squares[r-1][c])
                        || (c && squares[r][c] == squares[r][c-1])
                        || (c < S-1 && squares[r][c] == squares[r][c+1])
                        || (r < S-1 && squares[r][c] == squares[r+1][c]) ) {
                    return( true );
                }
            }
        }

        return( false );
    }

    bool move(Direction d)
    {
        bool blocksMoved = false;

        int r, c;
        int r2;

        for (c = 0; c < S; c++) {
            // Move into blanks
            r2 = 0;
            for (r = 0; r < S; r++) {
                if (dirAccess(r, c, d)) {
                    if (r2 != r) {
                        dirAccess(r2, c, d) = dirAccess(r, c, d);
                        dirAccess(r, c, d) = 0;

                        blocksMoved = true;
                    }

                    r2++;
                }
            }

            // Combine
            for (r = 1; r < S; r++) {
                if (dirAccess(r, c, d) && dirAccess(r, c, d) == dirAccess(r-1, c, d)) {
                    dirAccess(r-1, c, d)++;
                    numBlanks++;

                    blocksMoved = true;

                    for (r2 = r+1; r2 < S; r2++) {
                        dirAccess(r2-1, c, d) = dirAccess(r2, c, d);
                        dirAccess(r2, c, d) = 0;
                    }
                }
            }
        }

        if (blocksMoved) {
            fillABlank();
        }

        return( blocksMoved );
    }
};


int main(int argc, char const *argv[])
{
    Grid<8> gr;
    Direction d = UP;

    gr.print();
    std::cout << std::endl;

    char c;
    bool running = true;
    for (;;) {
        std::cin >> c;

        switch (c) {
        case 'q':
            running = false;
            break;
        case 'w':
            gr.move(UP);
            break;
        case 'a':
            gr.move(LEFT);
            break;
        case 's':
            gr.move(DOWN);
            break;
        case 'd':
            gr.move(RIGHT);
            break;
        default:
            std::cout << "Dunno what you meant to do. Try WASD or Q." << std::endl;
            break;
        }

        if (!running) {
            break;
        }

        gr.print();
        std::cout << std::endl;
    }

    return 0;
}