#include <bits/stdc++.h>
// #include "solution.h"
using namespace std;
#define rep(i, j) for (int i = 0; i < 4; i++)\
for (int j = 0; j < 4; j++)
typedef array<array<int, 4>, 4> board;
board flip(board a, bool z = 1) {
board b;
rep(i, j) {
if (z) b[i][j] = a[j][i];
else b[i][j] = a[3 - j][3 - i];
}
return b;
}
board dir(board a, char c) {
if (c == 'U') return a;
if (c == 'L') return flip(a);
if (c == 'R') return flip(a, 0);
return flip(flip(a, 0));
}
board move(board a, char c) {
a = dir(a, c);
rep(j, i) {
if (a[i][j] == 0) continue;
for (int k = i + 1; k < 4; k++) {
if (a[k][j] == 0) continue;
if (a[i][j] == a[k][j]) {
a[i][j] *= -2;
a[k][j] = 0;
}
break;
}
}
rep(i, j) if (a[i][j] < 0) a[i][j] = -a[i][j];
rep(j, i) {
if (a[i][j] > 0) continue;
for (int k = i + 1; k < 4; k++) {
if (a[k][j] > 0) {
a[i][j] = a[k][j];
a[k][j] = 0;
break;
}
}
}
a = dir(a, c);
return a;
}
board put(board a) {
vector<pair<int, int>> zeros;
rep(i, j) if (a[i][j] == 0) zeros.push_back({i, j});
int p = rand() % 100;
int k = rand() % zeros.size();
int i = zeros[k].first;
int j = zeros[k].second;
int val = (p < 10) ? 4 : 2;
a[i][j] = val;
return a;
}
// BEGIN
// Энд функц заралж ашиглаж болно
board flip1(board a, bool z = 1) {
board b;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (z)
b[i][j] = a[j][i];
else
b[i][j] = a[3 - j][3 - i];
}
}
return b;
}
board dir1(board a, char c) {
if (c == 'U')
return a;
if (c == 'L')
return flip1(a);
if (c == 'R')
return flip1(a, 0);
return flip1(flip1(a, 0));
}
board move1(board a, char c) {
a = dir1(a, c);
for (int j = 0; j < 4; j++) {
for (int i = 0; i < 4; i++) {
if (a[i][j] == 0) continue;
for (int k = i + 1; k < 4; k++) {
if (a[k][j] == 0) continue;
if (a[i][j] == a[k][j]) {
a[i][j] *= -2;
a[k][j] = 0;
}
break;
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (a[i][j] < 0) a[i][j] = -a[i][j];
}
}
for (int j = 0; j < 4; j++) {
for (int i = 0; i < 4; i++) {
if (a[i][j] > 0) continue;
for (int k = i + 1; k < 4; k++) {
if (a[k][j] > 0) {
a[i][j] = a[k][j];
a[k][j] = 0;
break;
}
}
}
}
a = dir1(a, c);
return a;
}
bool over(const board& a, char move) {
board b = move1(a, move);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (b[i][j] == 0) {
return false;
}
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if ((i < 3 && b[i][j] == b[i + 1][j]) || (j < 3 && b[i][j] == b[i][j + 1])) {
return false;
}
}
}
return true;
}
int findsum(const board& a) {
int sum = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
sum += a[i][j];
}
}
return sum;
}
int sumafter(const board& a, char move) {
board x = move1(a, move);
return findsum(x);
}
char play(board a) {
char up = 'U';
char down = 'D';
char right = 'R';
char left = 'L';
if (over(a, right)) {
return right;
}
board b = move1(a, up);
if (a != b) {
if (!over(b, up)) {
return up;
}
}
b = move1(a, down);
if (a != b) {
if (!over(b, down)) {
return down;
}
}
b = move1(a, right);
if (a != b) {
if (!over(b, right)) {
return right;
}
}
return left;
}
// Энд бичсэн хэсгээ л сервэрт илгээнэ
// END
int main(int argc, char **argv) {
string token;
if (argc == 2) token = argv[1];
srand(247);
srand(time(0));
board a; rep(i, j) a[i][j] = 0;
int itr = 0;
clock_t begin = clock();
while (true) {
char c = play(a);
rep(i, j) cout << a[i][j] << " \n"[j == 3];
cout << c << "\n";
if (c != 'U' && c != 'R' && c != 'D' && c != 'L') break;
board b = move(a, c);
if (itr > 0 && b == a) break;
a = put(b);
double timer = double(clock() - begin) / CLOCKS_PER_SEC;
if (timer > 10) break;
itr++;
}
int score = 0;
rep(i, j) score += a[i][j];
cout << "Score: " << score << endl;
cout << "Last state:\n";
rep(i, j) cout << a[i][j] << " \n"[j == 3];
double timer = double(clock() - begin) / CLOCKS_PER_SEC;
cout << "Time: " << (int)timer <<"sec\n";
return 0;
}