#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <random>
#include <tuple>

#ifdef __unix__
#include <signal.h>
#include <termios.h>
#include <unistd.h>
#endif

#ifdef _WIN32
#include <windows.h>
#ifndef ENABLE_VIRTUAL_TERMINAL_PROCESSING
#define ENABLE_VIRTUAL_TERMINAL_PROCESSING 0x0004
#endif
#endif

using namespace std;

struct Game2048 {
    static const int WIDTH = 4, HEIGHT = 4;
    enum struct MoveDirection { UP, LEFT, DOWN, RIGHT };
    enum struct GridStatus { NORMAL, MERGED, NEW };

    static void calc_dir(MoveDirection dir, int& di, int& dj) {
        switch (dir) {
        case MoveDirection::UP: di = -1, dj = 0; break;
        case MoveDirection::DOWN: di = 1, dj = 0; break;
        case MoveDirection::LEFT: di = 0, dj = -1; break;
        case MoveDirection::RIGHT: di = 0, dj = 1; break;
        }
    }

    typedef uint8_t CellType;
    static bool can_merge(CellType x, CellType y) { return x == y; }
    static CellType do_merge(CellType x, CellType) { return assert(x + 1 <= 15), x + 1; }
    static int calc_score(CellType x) { return x ? (1 << x) : 0; }

    static CellType random_new(mt19937& eng) {
        return eng() % 2 ? 1 : 2;  // 2: 50%, 4: 50%;
    }

    struct Grid {
        CellType grid[HEIGHT][WIDTH];
        GridStatus status[HEIGHT][WIDTH];
        Grid() { memset(grid, 0, sizeof(grid)), memset(status, 0, sizeof(status)); }

        int move(MoveDirection dir, Grid& ret) const {
            int di, dj;
            calc_dir(dir, di, dj);
            int di1 = di ? -di : 1, dj1 = dj ? -dj : 1;
            int score_add = 0;
            bool changed = false;
            for (int i = (di > 0 ? HEIGHT - 1 : 0); i >= 0 && i < HEIGHT; i += di1) {
                for (int j = (dj > 0 ? WIDTH - 1 : 0); j >= 0 && j < WIDTH; j += dj1) {
                    if (!grid[i][j]) continue;
                    int i1 = i, j1 = j;
                    while (true) {
                        if (!(0 <= i1 + di && i1 + di < HEIGHT && 0 <= j1 + dj && j1 + dj < WIDTH)
                          || (ret.grid[i1 + di][j1 + dj]
                            && (!can_merge(ret.grid[i1 + di][j1 + dj], grid[i][j])
                              || ret.status[i1 + di][j1 + dj] == GridStatus::MERGED))) {
                            ret.grid[i1][j1] = grid[i][j];
                            break;
                        }
                        i1 += di, j1 += dj, changed = true;
                        if (can_merge(ret.grid[i1][j1], grid[i][j])) {
                            ret.status[i1][j1] = GridStatus::MERGED;
                            ret.grid[i1][j1] = do_merge(ret.grid[i1][j1], grid[i][j]);
                            score_add += calc_score(ret.grid[i1][j1]);
                            break;
                        }
                    }
                }
            }
            return changed ? score_add : -1;
        }

        bool die() const {
            for (int i = 0; i < HEIGHT; i++) {
                for (int j = 0; j < WIDTH; j++) {
                    if (!grid[i][j]) return false;
                }
            }
            for (int i = 1; i < HEIGHT; i++) {
                for (int j = 0; j < WIDTH; j++) {
                    if (grid[i][j] == grid[i - 1][j]) return false;
                }
            }
            for (int i = 0; i < HEIGHT; i++) {
                for (int j = 1; j < WIDTH; j++) {
                    if (grid[i][j] == grid[i][j - 1]) return false;
                }
            }
            return true;
        }
        
        void place_new(int i, int j, CellType x) { grid[i][j] = x, status[i][j] = GridStatus::NEW; }
    };

    Grid grid;
    int score, score_last_add;
    uint32_t seed;
    mt19937 eng;

    Game2048(uint32_t seed_) : score(0), score_last_add(0), seed(seed_), eng(seed_) { }

    bool operate(MoveDirection dir) {
        Grid new_grid;
        int score_add = grid.move(dir, new_grid);
        grid = new_grid;
        if (score_add < 0) return score_last_add = 0, false;
        else return score += score_add, score_last_add = score_add, true;
    }

    bool should_stop() const { return grid.die(); }

    void summon_new_block() {
        vector<tuple<int, int>> free_pos;
        for (int i = 0; i < HEIGHT; i++) {
            for (int j = 0; j < WIDTH; j++) {
                if (!grid.grid[i][j]) free_pos.push_back(make_tuple(i, j));
            }
        }
        int i, j;
        tie(i, j) = free_pos[eng() % free_pos.size()];
        grid.place_new(i, j, random_new(eng));
    }
};

struct Bot {
    // https://sleepycoder.github.io/2014/04/01/2048-ai/
    static_assert(Game2048::HEIGHT == 4 && Game2048::WIDTH == 4, "");
    typedef array<uint8_t, 16> Grid;

    static Grid convert(const Game2048::Grid& grid) {
        Grid ret;
        for (int i=0; i<4; i++) {
            for (int j=0; j<4; j++) ret[i*4+j] = grid.grid[i][j];
        }
        return ret;
    }

    static int move_left(Grid grid, Grid& ret) {
        int score = 0;
        bool changed = false;
        for (int i=0; i<4; i++) {
            bool merged[4];
            for (int j=0, k=0; j<4; j++) {
                ret[i*4+j] = 0, merged[j] = 0;
                if (grid[i*4+j]) {
                    if (k && Game2048::can_merge(ret[i*4+k-1], grid[i*4+j]) && !merged[k-1]) {
                        ret[i*4+k-1] = Game2048::do_merge(ret[i*4+k-1], grid[i*4+j]);
                        score += Game2048::calc_score(ret[i*4+k-1]);
                        merged[k-1] = true, changed = true;
                    } else ret[i*4+k] = grid[i*4+j], changed |= (k!=j), k++;
                }
            }
        }
        return changed ? score : -1;
    }

    static Grid rotate(Grid grid) {
        return {grid[3], grid[7], grid[11], grid[15],
                grid[2], grid[6], grid[10], grid[14],
                grid[1], grid[5], grid[9] , grid[13],
                grid[0], grid[4], grid[8] , grid[12]};
    }

    mt19937 eng;
    Bot(uint32_t seed) : eng(seed) { }

    static int estimate(Grid grid) {
        int sum = 0;
        for (int i=0; i<16; i++) {
            sum += Game2048::calc_score(grid[i]) * 4;
            sum -= i%4 != 3 ? abs(Game2048::calc_score(grid[i]) - Game2048::calc_score(grid[i+1])) : 0;
            sum -= i/4 != 3 ? abs(Game2048::calc_score(grid[i]) - Game2048::calc_score(grid[i+4])) : 0;
        }
        return sum * 2;
    }

    static double _next(Grid grid, int steps, int& tot_cnt) {
        tot_cnt++;
        Grid new_;
        int score_add = move_left(grid, new_);
        if (score_add < 0) return -1e9;
        grid = new_;
        double score = 0;
        int free_cnt = 0;
        for (int i=0; i<16; i++) {
            if (!grid[i]) {
                free_cnt++;
                grid[i] = 1;
                score += dfs(grid, steps-1, tot_cnt) * 0.5;
                grid[i] = 2;
                score += dfs(grid, steps-1, tot_cnt) * 0.5;
                grid[i] = 0;
            }
        }
        return score / free_cnt + score_add;
    }

    static double dfs(Grid grid, int steps, int& tot_cnt) {
        if (!steps) return estimate(grid);
        double max_score = -1e9;
        for (int _ = 0; _ < 4; _++, grid = rotate(grid)) max_score = max(max_score, _next(grid, steps, tot_cnt));
        return max_score;
    }

    Game2048::MoveDirection predict(const Game2048::Grid& grid_in) {
        auto grid = convert(grid_in);
        double max_score = -1e9;
        Game2048::MoveDirection best_dir;
        for (auto dir : {Game2048::MoveDirection::LEFT, Game2048::MoveDirection::UP, Game2048::MoveDirection::RIGHT, Game2048::MoveDirection::DOWN}) {
            int tot_cnt = 0;
            double score;
            for (int dep = 3; tot_cnt <= 1500; dep++) score = _next(grid, dep, tot_cnt);
            if (score > max_score) max_score = score, best_dir = dir;
            grid = rotate(grid);
        }
        return best_dir;
    }
};

struct Interface {
    Game2048* game;

#ifdef __unix__
    termios term_ori, term_cur;
#endif
#ifdef _WIN32
    DWORD input_mode_ori, input_mode_cur;
    DWORD output_mode_ori, output_mode_cur;
#endif

    Interface(Game2048* game_) : game(game_) { }
    void init() {
#ifdef __unix__
        tcgetattr(STDIN_FILENO, &term_ori);
        term_cur = term_ori;
        term_cur.c_lflag &= ~(unsigned) (ECHO | ICANON);
        tcsetattr(STDIN_FILENO, TCSAFLUSH, &term_cur);
#endif
#ifdef _WIN32
        assert(GetConsoleMode(GetStdHandle(STD_INPUT_HANDLE), &input_mode_ori));
        input_mode_cur = input_mode_ori & ~(ENABLE_ECHO_INPUT | ENABLE_LINE_INPUT);
        assert(SetConsoleMode(GetStdHandle(STD_INPUT_HANDLE), input_mode_cur));
        assert(GetConsoleMode(GetStdHandle(STD_OUTPUT_HANDLE), &output_mode_ori));
        output_mode_cur = output_mode_ori | ENABLE_VIRTUAL_TERMINAL_PROCESSING;
        assert(SetConsoleMode(GetStdHandle(STD_OUTPUT_HANDLE), output_mode_cur));
#endif
    }
    void deinit() {
        printf("\x1b[%dB", game->HEIGHT + 1);
#ifdef __unix__
        tcsetattr(STDIN_FILENO, TCSAFLUSH, &term_ori);
#endif
#ifdef _WIN32
        assert(SetConsoleMode(GetStdHandle(STD_INPUT_HANDLE), input_mode_ori));
        assert(SetConsoleMode(GetStdHandle(STD_OUTPUT_HANDLE), output_mode_ori));
#endif
    }

    void display() {
        static const char* names[] = {"", "2", "4", "8", "16", "32", "64", "128", "256", "512", "1024", "2048", "4096", "8192"};
        static const int names_cnt = sizeof(names) / sizeof(*names) - 1;
        static const int bgcol[] = {40, 44, 42};  // Black, Blue, Green
        static const int grid_width = 5;

        for (int i = 0; i < game->HEIGHT; i++) {
            for (int j = 0; j < game->WIDTH; j++) {
                printf("\x1b[%dm", bgcol[(int) game->grid.status[i][j]]);
                auto str = game->grid.grid[i][j] > names_cnt ? "-" : names[game->grid.grid[i][j]];
                int l = (int) strlen(str);
                for (int _ = 1; _ <= (grid_width - l) / 2; _++) putchar(' ');
                printf("%s", str);
                for (int _ = 1; _ <= (grid_width - l + 1) / 2; _++) putchar(' ');
            }
            printf("\x1b[0m\n");
        }
        printf("score: %d (+ %d)                    \n", game->score, game->score_last_add);
        printf("\x1b[%dA", game->HEIGHT + 1);
        fflush(stdout);
    }

    enum struct InputOperation { MOVE, QUIT, BOT_STEP, BOT_TEST, BOT_WHILE };

    pair<InputOperation, Game2048::MoveDirection> get_input() {
        while (true) {
            int key = getchar();
            if (feof(stdin) || ferror(stdin)) return {};
            switch (key) {
            case 'q':
            case 'Q': return {InputOperation::QUIT, {}};
            case 'w':
            case 'W': return {InputOperation::MOVE, Game2048::MoveDirection::UP};
            case 's':
            case 'S': return {InputOperation::MOVE, Game2048::MoveDirection::DOWN};
            case 'a':
            case 'A': return {InputOperation::MOVE, Game2048::MoveDirection::LEFT};
            case 'd':
            case 'D': return {InputOperation::MOVE, Game2048::MoveDirection::RIGHT};
            case 'N': return {InputOperation::BOT_STEP, {}};
            case 'M': return {InputOperation::BOT_WHILE, {}};
#ifdef __unix__
            case '\033': {
                int key2 = getchar();
                if (key2 == '[') {  // Arrow keys
                    int key3 = getchar();
                    switch (key3) {
                    case 'A': return {InputOperation::MOVE, Game2048::MoveDirection::UP};
                    case 'B': return {InputOperation::MOVE, Game2048::MoveDirection::DOWN};
                    case 'C': return {InputOperation::MOVE, Game2048::MoveDirection::RIGHT};
                    case 'D': return {InputOperation::MOVE, Game2048::MoveDirection::LEFT};
                    }
                }
                if (key2 == 'O') {  // Fn keys
                    int key3 = getchar();
                    switch (key3) {
                    case 'P': return {InputOperation::BOT_STEP, {}};
                    case 'Q': return {InputOperation::BOT_WHILE, {}};
                    case 'R': return {InputOperation::BOT_TEST, {}};
                    case 'S': kill(0, SIGTRAP);
                    }
                }
            } break;
#endif
            }
        }
    }
};
Interface* g_interface;

#ifdef __unix__
void sig_quit(int) { g_interface->deinit(), exit(0); }
#endif
#ifdef _WIN32
BOOL sig_quit(DWORD) { return g_interface->deinit(), exit(0), 0; }
#endif

int main() {
#ifdef __unix__
    signal(SIGINT, sig_quit);
    signal(SIGHUP, sig_quit);
    signal(SIGTERM, sig_quit);
#endif
#ifdef _WIN32
    SetConsoleCtrlHandler(sig_quit, true);
#endif

    random_device rd;
    Game2048* game = new Game2048(rd());
    Bot bot(rd());
    Interface interface_(game);
    interface_.init();
    g_interface = &interface_;
    game->summon_new_block();

    while (!game->should_stop()) {
        interface_.display();
        Game2048::MoveDirection dir;
        Interface::InputOperation op;
        tie(op, dir) = interface_.get_input();
        if (op == Interface::InputOperation::QUIT) break;
        if (op == Interface::InputOperation::BOT_WHILE) {
            while (!game->should_stop()) {
                dir = bot.predict(game->grid);
                if (game->operate(dir)) game->summon_new_block();
                interface_.display();
            }
            break;
        }
        if (op == Interface::InputOperation::BOT_TEST) {
            while (true) {
                game = new Game2048(rd());
                game->summon_new_block();
                while (!game->should_stop()) {
                    dir = bot.predict(game->grid);
                    if (game->operate(dir)) game->summon_new_block();
                }
                printf("%d      \n", game->score);
                delete game;
            }
            break;
        }
        if (op == Interface::InputOperation::BOT_STEP)
            dir = bot.predict(game->grid);
        printf("                              direction: %d\x1b[G", (int)dir);
        if (game->operate(dir))
            game->summon_new_block();
    }
    interface_.display();
    interface_.deinit();
    delete game;
}