Skip to content

Instantly share code, notes, and snippets.

@hamadu

hamadu/SquareRemover.cpp

Created April 24, 2014 02:57
Show Gist options
  • Save hamadu/11239927 to your computer and use it in GitHub Desktop.
Save hamadu/11239927 to your computer and use it in GitHub Desktop.
Download ZIP
TCO14 Marathon Round1
Raw
SquareRemover.cpp
bool DEBUG = false;
double TLE = 30.0;
long _xtime = 30000;
int _maxTurn = 10000;
bool _debug = false;
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <stdarg.h>
#include <sys/time.h>
#include <emmintrin.h>
typedef long long int int64;
using namespace std;
const int DX[24] = { 0, 1, 0, -1, 1, 1, -1, -1, 0, 2, 0, -2, -2, -1, 1, 2, 2, 1, -1, -2, -2, 2, -2, 2 };
const int DY[24] = { -1, 0, 1, 0, -1, 1, -1, 1, -2, 0, 2, 0, -1, -2, -2, -1, 1, 2, 2, 1, -2, -2, 2, 2 };
const int QX[4] = { 0, 1, 0, 1 };
const int QY[4] = { 0, 0, 1, 1 };
const int64 CLM = 7;
const int64 DCLM = 63;
const size_t ROWSIZE = sizeof(int64) * 16;
bool WANT_COLUMN[64];
int N, C;
double _start_time = 0.0;
double _end_time = 0.0;
double _record_time = 0.0;
double _limit_time = 0.0;
int _rlt = 0;
int _rlt2 = 0;
const int MAX_N = 16;
const int MAX_C = 6;
const int BUFFER_SIZE = 200000;
int64 BUFFER[BUFFER_SIZE] = {0};
int64 BUFFER_HEAD = 0;
int defaultIsX = 0;
int64 PR = 1000000009;
double get_time(){
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec*1e-6;
}
void swap(int64 board[MAX_N], int i, int j, int d) {
int ti = i + DY[d];
int tj = j + DX[d];
int j3 = 3*j;
int tj3 = 3*tj;
int64 c1 = (board[i] >> j3) & CLM;
int64 c2 = (board[ti] >> tj3) & CLM;
board[i] -= c1 << j3;
board[ti] -= c2 << tj3;
board[i] |= c2 << j3;
board[ti] |= c1 << tj3;
}
int scoreSlow(int64 encoded[MAX_N], int bidx, int fi) {
int plus = 0;
bool upd = true;
while (true) {
upd = false;
for (int i = max(0, fi-1); i < N - 1; i++) {
for (int j = 0; j < N - 1; j++) {
int row1 = (int) ((encoded[i] >> (3 * j)) & DCLM);
int row2 = (int) ((encoded[i + 1] >> (3 * j)) & DCLM);
if (WANT_COLUMN[row1] && row1 == row2) {
plus++;
upd = true;
int64 reg = ~(DCLM << (3 * j));
int64 up = ((BUFFER[bidx]) | ((BUFFER[bidx + 1]) << 3)) << (3 * j);
int64 dw = ((BUFFER[bidx + 2]) | ((BUFFER[bidx + 3]) << 3)) << (3 * j);
encoded[i] = (encoded[i] & reg) | up;
encoded[i + 1] = (encoded[i + 1] & reg) | dw;
bidx += 4;
fi = i;
goto sch;
}
}
}
sch:
if (!upd) {
break;
}
}
return plus;
}
/**
* count score (it's slow)
*
* @param encoded
* @return
*/
int scoreSlow(int64 encoded[MAX_N], int bidx) {
return scoreSlow(encoded, bidx, 0);
}
/**
* count score (only on interested point. fast)
*
* @param encoded
* @param bidx
* @param ci
* @param cj
*/
int scoreFast(int64 encoded[MAX_N], int bidx, int ci, int cj, int di, int dj) {
const int imax = (ci == di) ? min(N-2, ci) : min(N-2, ci+1);
const int jmax = (cj == dj) ? min(N-2, cj) : min(N-2, cj+1);
for (int i = max(0, ci - 1); i <= imax; i++) {
for (int j = max(0, cj - 1); j <= jmax ; j++) {
int row1 = (int) ((encoded[i] >> (3 * j)) & DCLM);
int row2 = (int) ((encoded[i + 1] >> (3 * j)) & DCLM);
if (WANT_COLUMN[row1] && row1 == row2) {
int64 reg = ~(DCLM << (3 * j));
int64 up = ((BUFFER[bidx]) | ((BUFFER[bidx + 1]) << 3)) << (3 * j);
int64 dw = ((BUFFER[bidx + 2]) | ((BUFFER[bidx + 3]) << 3)) << (3 * j);
encoded[i] = (encoded[i] & reg) | up;
encoded[i + 1] = (encoded[i + 1] & reg) | dw;
bidx += 4;
return 1 + scoreSlow(encoded, bidx, i);
}
}
}
return 0;
}
/**
* process state fast
*
* @param score
* @param board
* @param i
* @param j
* @param d
* @return
*/
int fastProcess(int score, int64 board[MAX_N], int i, int j, int d) {
int add = 0;
int ti = i + DY[d];
int tj = j + DX[d];
if (i < ti || (i == ti && j < tj)) {
add = scoreFast(board, score << 2, i, j, ti, tj);
} else {
add = scoreFast(board, score << 2, ti, tj, i, j);
}
return add;
}
int findPathScore = 0;
int findPathOP[128];
int findPathOPIdx = 0;
int collectFourFixed[256];
bool findPath(int fi, int fj, int col, int64 brd[MAX_N]) {
// same
if (((brd[fi] >> (3 * fj)) & 7) == col) {
return true;
}
//
// 1
// 1*1
// 1
//
for (int d = 0 ; d < 4 ; d++) {
int ti = fi + DY[d];
int tj = fj + DX[d];
if (ti < 0 || tj < 0 || ti >= N || tj >= N || collectFourFixed[(ti<<4)+tj]) {
continue;
}
if (((brd[ti] >> (3 * tj)) & 7) == col) {
findPathOP[findPathOPIdx++] = fi;
findPathOP[findPathOPIdx++] = fj;
findPathOP[findPathOPIdx++] = d;
swap(brd, fi, fj, d);
return true;
}
}
//
// 2-2
// -*-
// 2-2
//
for (int d = 4 ; d < 8 ; d++) {
int ti = fi + DY[d];
int tj = fj + DX[d];
if (ti < 0 || tj < 0 || ti >= N || tj >= N || collectFourFixed[(ti<<4)+tj]) {
continue;
}
if (((brd[ti] >> (3 * tj)) & 7) == col) {
// which way to go?
// y@
// *x
int codex = (fi<<4)+tj;
int codey = (ti<<4)+fj;
if (collectFourFixed[codex] && collectFourFixed[codey]) {
continue;
}
int dx = ((d-4)/2)*2+1;
int dy = (d%2)*2;
bool goX = false;
if (collectFourFixed[codey]) {
// x is okay
// -@
// **
goX = true;
} else if (collectFourFixed[codex]) {
// y is okay
// *@
// *-
} else {
// both is okay
// ??
// y@?
// *x
goX = (defaultIsX >= 1);
}
if (goX) {
findPathOP[findPathOPIdx++] = fi;
findPathOP[findPathOPIdx++] = tj;
findPathOP[findPathOPIdx++] = dy;
swap(brd, fi, tj, dy);
findPathOP[findPathOPIdx++] = fi;
findPathOP[findPathOPIdx++] = fj;
findPathOP[findPathOPIdx++] = dx;
swap(brd, fi, fj, dx);
} else {
findPathOP[findPathOPIdx++] = ti;
findPathOP[findPathOPIdx++] = fj;
findPathOP[findPathOPIdx++] = dx;
swap(brd, ti, fj, dx);
findPathOP[findPathOPIdx++] = fi;
findPathOP[findPathOPIdx++] = fj;
findPathOP[findPathOPIdx++] = dy;
swap(brd, fi, fj, dy);
}
return true;
}
}
// 3
// ---
//3-*-3
// ---
// 3
for (int d = 8 ; d < 12 ; d++) {
int ti = fi + DY[d];
int tj = fj + DX[d];
if (ti < 0 || tj < 0 || ti >= N || tj >= N || collectFourFixed[(ti<<4)+tj]) {
continue;
}
if (((brd[ti] >> (3 * tj)) & 7) == col) {
int ci = (fi+ti)/2;
int cj = (fj+tj)/2;
if (collectFourFixed[(ci<<4)+cj]) {
continue;
}
findPathOP[findPathOPIdx++] = ci;
findPathOP[findPathOPIdx++] = cj;
findPathOP[findPathOPIdx++] = d-8;
swap(brd, ci, cj, d-8);
findPathOP[findPathOPIdx++] = fi;
findPathOP[findPathOPIdx++] = fj;
findPathOP[findPathOPIdx++] = d-8;
swap(brd, fi, fj, d-8);
return true;
}
}
return false;
}
int collectFourBestScore;
int64 collectFourBestBoard[MAX_N];
void collectFour(int i, int j, int col, int64 brd[MAX_N], int score) {
memset(collectFourFixed, 0, 256 * sizeof(int));
findPathOPIdx = 0;
collectFourBestScore = -1;
int prm[4] = {0, 0, 0, 0};
int ph = 0;
int pt = 3;
for (int q = 0; q < 4; q++) {
int fi = i + QY[q];
int fj = j + QX[q];
if (((brd[fi] >> (3 * fj)) & 7) == col) {
prm[ph++] = q;
} else {
prm[pt--] = q;
}
}
bool isGood = true;
int64 cpy[MAX_N];
memcpy(cpy, brd, ROWSIZE);
for (int q = 0; q < 4; q++) {
int fi = i + QY[prm[q]];
int fj = j + QX[prm[q]];
bool isok = findPath(fi, fj, col, cpy);
if (!isok) {
isGood = false;
break;
}
collectFourFixed[(fi<<4)+fj] = 1;
}
if (isGood) {
memcpy(collectFourBestBoard, brd, ROWSIZE);
int bscore = score;
for (int o = 0 ; o < findPathOPIdx ; o += 3) {
int fi = findPathOP[o];
int fj = findPathOP[o+1];
int d = findPathOP[o+2];
swap(collectFourBestBoard, fi, fj, d);
score += fastProcess(score, collectFourBestBoard, fi, fj, d);
}
collectFourBestScore = score - bscore;
}
}
vector<int> output(vector<int> result) {
vector<int> ret;
for (int i = 0 ; i < 10000 * 3 ; i++) {
if (i < result.size()) {
ret.push_back(result[i]);
} else {
ret.push_back(1);
}
}
return ret;
}
void initialize(int colors, vector<string> board, int startSeed, int64 ret[MAX_N]) {
N = board.size();
C = colors;
for (int i = 0 ; i < 64 ; i++) {
WANT_COLUMN[i] = false;
}
WANT_COLUMN[0] = true;
WANT_COLUMN[1 | (1 << 3)] = true;
WANT_COLUMN[2 | (2 << 3)] = true;
WANT_COLUMN[3 | (3 << 3)] = true;
WANT_COLUMN[4 | (4 << 3)] = true;
WANT_COLUMN[5 | (5 << 3)] = true;
BUFFER[0] = (int)(startSeed % C);
BUFFER_HEAD = startSeed;
for (int i = 1; i < BUFFER_SIZE; i++) {
BUFFER_HEAD = (BUFFER_HEAD * 48271) % (2147483647L);
BUFFER[i] = (int)(BUFFER_HEAD % C);
}
if (DEBUG) {
cerr << N << "," << C << endl;
}
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < N ; j++) {
int64 z = board[i][j] - '0';
ret[i] |= z<<(3LL*j);
}
}
}
const int MAXBW = 64;
int64 beamDisp[10020][MAXBW];
int beamScore[10020][MAXBW];
int beamSubScore[10020][MAXBW];
int64 beamBoard[10020][MAXBW][16];
int beamOperations[10020][MAXBW][32];
int beamOperationsIdx[10020][MAXBW];
int beamParent[10020][MAXBW][2];
int beamIdx[10020];
vector<int> beam(int64 initialBoard[MAX_N]) {
vector<int> result;
int BW = ((int)(sqrt(7000.0/(pow(N-1, 1.7)*(pow(C, -1.2)))))+1);
const int ROT = 16;
if (DEBUG) {
cerr << "(N,C,BW)=(" << N << "," << C << "," << BW << ")" << endl;
}
int initialScore = scoreSlow(initialBoard, 0);
int size64 = 10020 * BW * sizeof(int64);
int size32 = 10020 * BW * sizeof(int);
memset(beamDisp, 0, size64);
beamDisp[0][0] = -1;
memset(beamScore, 0, size32);
beamScore[0][0] = initialScore;
memset(beamSubScore, 0, size32);
beamSubScore[0][0] = 0;
memset(beamBoard, 0, size64 * MAX_N);
memcpy(beamBoard[0][0], initialBoard, ROWSIZE);
memset(beamOperations, 0, sizeof(beamOperations));
memset(beamOperationsIdx, 0, sizeof(beamOperationsIdx));
memset(beamIdx, 0, sizeof(beamIdx));
beamIdx[0] = 1;
int sum[MAX_C][MAX_N+1][MAX_N+1];
for (int c = 0 ; c < MAX_C ; c++) {
for (int i = 0 ; i <= MAX_N ; i++) {
for (int j = 0 ; j <= MAX_N ; j++) {
sum[c][i][j] = 0;
}
}
}
int maxopsize = 0;
int finalTurn = _maxTurn;
for (int T = 0 ; T < _maxTurn ; T++) {
for (int B = 0 ; B < beamIdx[T] ; B++) {
int currentScore = beamScore[T][B];
int nxcol[MAX_C] = {0};
int bidx = currentScore*4;
for (int i = 0 ; i < 1 ; i++) {
nxcol[BUFFER[bidx]]++;
nxcol[BUFFER[bidx+1]]++;
nxcol[BUFFER[bidx+2]]++;
nxcol[BUFFER[bidx+3]]++;
int64 c = BUFFER[bidx+3];
if (nxcol[c] == 4) {
nxcol[c] = 0;
bidx += 4;
i--;
}
}
int nextBidx = bidx;
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < N ; j++) {
int64 co = (((beamBoard[T][B][i]) >> (3 * j)) & 7);
for (int c = 0 ; c < C ; c++) {
sum[c][i+1][j+1] = sum[c][i+1][j] + sum[c][i][j+1] - sum[c][i][j];
if (co == c) {
sum[c][i+1][j+1] += 1;
}
}
}
}
int btid = T*BW+B;
int subScore = 0;
// three
for (int i = 0 ; i < N-1 ; i++) {
for (int j = 0 ; j < N-1 ; j++) {
int co[MAX_C] = {0};
for (int q = 0 ; q < 4 ; q++) {
int ti = i+QY[q];
int tj = j+QX[q];
int c = (int)((beamBoard[T][B][ti] >> (3 * tj)) & 7);
co[c]++;
}
sort(co, co+MAX_C);
if (co[MAX_C-1] == 3) {
subScore += 7;
} else {
if (co[MAX_C-1] == 2) {
subScore += 2;
if (co[MAX_C-2] == 2) {
subScore += 3;
}
}
}
}
}
beamSubScore[B][T] = subScore;
int candidates = 0;
int scores[256] = {0};
for (int i = 0; i < N-1 ; i++) {
for (int j = 0; j < N-1; j++) {
int maxColorNum = 0;
int colors[MAX_C] = {0, 0, 0, 0, 0, 0};
for (int q = 0; q < 4; q++) {
int ti = i + QY[q];
int tj = j + QX[q];
int c = (int)((beamBoard[T][B][ti] >> (3 * tj)) & 7);
colors[c]++;
maxColorNum = max(maxColorNum, colors[c]);
}
if (maxColorNum <= 1) {
continue;
}
int mul = 0;
for (int q = 0 ; q < 4 ; q++) {
int ei = i + QY[q];
int ej = j + QX[q];
int c = (int)BUFFER[nextBidx+q];
int del = (sum[c][i+2][j+2] - sum[c][i][j+2] - sum[c][i+2][j] + sum[c][i][j]);
int fi = max(0, ei-1);
int fj = max(0, ej-1);
int ti = min(ei+2, N);
int tj = min(ej+2, N);
int add = (sum[c][ti][tj] - sum[c][fi][tj] - sum[c][ti][fj] + sum[c][fi][fj]);
mul += (add - del);
}
int sc = mul;
scores[(i << 4) + j] = ((sc << 16) | (i << 4)) | j;
candidates++;
}
}
sort(scores, scores+256);
for (int d = 0; d < min(40, candidates/2) ; d++) {
if (scores[255-d] == 0) {
break;
}
int pos = scores[255-d] & ((1<<16)-1);
int i = pos >> 4;
int j = pos & 15;
int colors[MAX_C] = {0};
int maxColorNum = 0;
for (int q = 0; q < 4; q++) {
int ti = i + QY[q];
int tj = j + QX[q];
int c = (int)((beamBoard[T][B][ti] >> (3 * tj)) & 7);
colors[c]++;
maxColorNum = max(maxColorNum, colors[c]);
}
for (int col = 0; col < C; col++) {
defaultIsX = rand() % 2;
if (colors[col] < maxColorNum) {
continue;
}
collectFour(i, j, col, beamBoard[T][B], currentScore);
if (collectFourBestScore < 0) {
continue;
}
int tT = (T + findPathOPIdx / 3);
int ts = collectFourBestScore + currentScore;
int minScore = 1<<16;
int minSubScore = 1<<16;
int minScoreIdx = -1;
int64 tbd = 0;
for (int i = 0 ; i < N ; i++) {
tbd *= PR;
tbd += collectFourBestBoard[i];
}
bool foundSameWorse = false;
if (beamIdx[tT] == BW) {
for (int q = 0 ; q <= 5 ; q++) {
for (int k = 0 ; k < beamIdx[tT+q] ; k++) {
if (beamScore[tT+q][k] <= ts) {
bool isSame = (tbd == beamDisp[tT+q][k]);
if (isSame) {
if (q == 0) {
foundSameWorse = true;
minScoreIdx = k;
}
beamScore[tT+q][k] = -1;
}
}
}
}
}
if (!foundSameWorse) {
if (beamIdx[tT] < BW) {
minScoreIdx = beamIdx[tT];
} else {
for (int k = 0 ; k < beamIdx[tT] ; k++) {
int DSi = (ts - beamScore[tT][k]);
int DSSi = (subScore - beamSubScore[tT][k]);
int TH = 16;
if (DSi > 0 || ((DSSi + DSi * TH) > 0)) {
int _DSi = (minScore - beamScore[tT][k]);
int _DSSi = (minSubScore - beamSubScore[tT][k]);
if (_DSi > 0 || ((_DSSi + _DSi * TH) > 0)) {
minScore = beamScore[tT][k];
minSubScore = beamSubScore[tT][k];
minScoreIdx = k;
}
}
}
}
}
if (minScoreIdx >= 0) {
for (int o = 0 ; o < findPathOPIdx ; o++) {
beamOperations[tT][minScoreIdx][o] = findPathOP[o];
}
beamOperationsIdx[tT][minScoreIdx] = findPathOPIdx;
memcpy(beamBoard[tT][minScoreIdx], collectFourBestBoard, ROWSIZE);
beamScore[tT][minScoreIdx] = ts;
beamSubScore[tT][minScoreIdx] = subScore;
beamDisp[tT][minScoreIdx] = tbd;
beamParent[tT][minScoreIdx][0] = T;
beamParent[tT][minScoreIdx][1] = B;
if (beamIdx[tT] < BW) {
beamIdx[tT]++;
}
maxopsize = max(maxopsize, findPathOPIdx);
}
}
}
}
}
finalize:
if (DEBUG) {
cerr << "final" << endl;
cerr << maxopsize << endl;
}
int score = -1;
int nowTurn = finalTurn;
int nowIdx = -1;
for (int t = finalTurn ; t <= finalTurn ; t++) {
for (int l = 0 ; l < beamIdx[t] ; l++) {
if (score < beamScore[t][l]) {
score = beamScore[t][l];
nowIdx = l;
}
}
}
vector<int> ops;
vector<int> revop;
while (true) {
int sz = beamOperationsIdx[nowTurn][nowIdx];
for (int i = sz-1 ; i >= 0 ; i--) {
revop.push_back(beamOperations[nowTurn][nowIdx][i]);
}
if (nowTurn == 0) {
break;
}
int pt = beamParent[nowTurn][nowIdx][0];
int pi = beamParent[nowTurn][nowIdx][1];
nowTurn = pt;
nowIdx = pi;
}
int rs = revop.size();
if (DEBUG) {
cerr << "dsz:" << rs << endl;
cerr << "sco:" << score << endl;
}
if (rs > 30000) {
rs = 30000;
}
for (int i = rs-1 ; i >= 0 ; i--) {
ops.push_back(revop[i]);
}
return ops;
}
class SquareRemover
{
public:
vector<int> playIt(int colors, vector<string> board, int startSeed) {
_start_time = get_time();
_limit_time = _start_time + (TLE * 29.0 / 30);
int64 initialBoard[MAX_N];
for (int i = 0 ; i < MAX_N ; i++) {
initialBoard[i] = 0;
}
initialize(colors, board, startSeed, initialBoard);
vector<int> result = beam(initialBoard);
return output(result);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment