Skip to content

Instantly share code, notes, and snippets.

@PardhavMaradani

PardhavMaradani/pardhav.cpp

Last active January 19, 2025 02:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save PardhavMaradani/8736c25cf70e36292204ec27058c213f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save PardhavMaradani/8736c25cf70e36292204ec27058c213f to your computer and use it in GitHub Desktop.
Download ZIP
My CodeCup 2025 submission
Raw
pardhav.cpp
#include <algorithm>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <bitset>
using namespace std;
#define DEBUG 1
#define LOG(msg, ...) { \
if (DEBUG) { \
fprintf(stderr, "" msg "\n", ##__VA_ARGS__); \
} \
}
typedef unsigned char u8;
typedef pair<u8, u8> u8pair;
typedef struct {
u8 a[3];
} u8a3_t;
typedef struct {
u8 a[4];
} u8a4_t;
typedef struct {
vector <u8a3_t> a[2];
} tilev_t;
typedef struct {
double sqScore;
double trScore;
double liScore;
u8 nSquares;
u8 nTriangles;
u8 nLines;
} sscore_t;
typedef pair<int, double> spair_t;
typedef struct {
u8 color;
bitset <12> o[2];
vector <u8a4_t> sc;
} cell_t;
cell_t cells[16][20];
set <u8pair> ccells[7]; // 0 - ignore, colors 1 - 6
typedef struct {
map <set<u8pair>, u8> vbox;
} cstate_t;
cstate_t cstate[7];
map <pair<int, int>, vector<int>> xMap = {
{{ 0, 1}, {-1, 1, -1, 0, 1, 1, 1, 0}},
{{-1, 1}, {-1, 0, 0, 1}},
{{-1, 0}, {-1, -1, 0, -1, -1, 1, 0, 1}},
{{-1, -1}, {-1, 0, 0, -1}},
{{ 0, -1}, {-1, -1, -1, 0, 1, -1, 1, 0}},
{{ 1, -1}, {0, -1, 1, 0}},
{{ 1, 0}, {1, -1, 0, -1, 1, 1, 0, 1}},
{{ 1, 1}, {1, 0, 0, 1}}
};
int secret = 0;
bool player1 = false;
typedef struct {
u8 r;
u8 c;
bool d; // 0 - h, 1 - v
double score[7]; // 0 - ignore, colors 1 - 6
double e;
sscore_t s[7];
} move_t;
u8 rSQ[7] = {0, 0, 0, 0, 0, 0, 0};
u8 maxOCSquares = 0;
inline bool inBoard(int r, int c) {
return (r >= 0 && r < 16 && c >= 0 && c < 20);
}
inline bool hasOverlap(int r, int c, u8 d) {
return inBoard(r, c) && cells[r][c].o[d].count() > 0;
}
int findValidMoves(move_t moves[512]) {
int nMoves = 0;
for (u8 d = 0; d < 2; d++) {
u8 mr = (d == 0) ? 15 : 11;
u8 mc = (d == 0) ? 15 : 19;
for (u8 r = 0; r < mr; r++) {
for (u8 c = 0; c < mc; c++) {
u8 oc = cells[r][c].o[d].count();
if (oc == 0) {
// check adjacency
if (hasOverlap(r - 1, c, d) || hasOverlap(r + 1, c, d) || hasOverlap(r, c - 1, d) || hasOverlap(r, c + 1, d)) {
moves[nMoves++] = {r, c, (bool)d};
}
} else if (oc <= 4) {
moves[nMoves++] = {r, c, (bool)d};
}
}
}
}
return nMoves;
}
u8 nDMoves(u8 r, u8 c) {
u8 dMoves = 0;
for (u8 i = 0; i < cells[r][c].sc.size(); i++) {
u8 sr = cells[r][c].sc[i].a[0];
u8 sc = cells[r][c].sc[i].a[1];
u8 d = cells[r][c].sc[i].a[2];
if (cells[sr][sc].o[d].count() <= 4) {
dMoves++;
}
}
return dMoves;
}
u8 nDMoves(u8pair p) {
return nDMoves(p.first, p.second);
}
void addVBoxes(u8 r, u8 c, u8 color, u8 length, u8 wr, u8 wc) {
int rd = (wr - r) / length;
int cd = (wc - c) / length;
auto v = xMap[{rd, cd}];
for (u8 i = 0; i < v.size() / 4; i++) {
int r1 = r + v[i * 4] * length;
int c1 = c + v[i * 4 + 1] * length;
int r2 = r + v[i * 4 + 2] * length;
int c2 = c + v[i * 4 + 3] * length;
if (inBoard(r1, c1) && inBoard(r2, c2)) {
set <u8pair> vbox = {{r, c}, {wr, wc}, {r1, c1}, {r2, c2}};
if (cstate[color].vbox.find(vbox) == cstate[color].vbox.end()) {
cstate[color].vbox[vbox] = length;
}
}
}
}
void modifyColorCell(u8 r, u8 c, u8 color, int delta) {
if (color == 0) {
// update overlaps
for (size_t i = 0; i < cells[r][c].sc.size(); i++) {
u8 sr = cells[r][c].sc[i].a[0];
u8 sc = cells[r][c].sc[i].a[1];
u8 d = cells[r][c].sc[i].a[2];
u8 p = cells[r][c].sc[i].a[3];
if (delta == -1) {
cells[sr][sc].o[d].set(p);
} else {
cells[r][c].color = color;
cells[sr][sc].o[d].reset(p);
}
}
return;
}
if (color == 7) {
// temp transparent cell
cells[r][c].color = (delta == 1) ? 7 : 0;
return;
}
if (delta == 1) {
cells[r][c].color = color;
ccells[color].insert({r, c});
for (auto it = ccells[color].begin(); it != ccells[color].end(); it++) {
u8 r1 = it->first;
u8 c1 = it->second;
if (r == r1 && c == c1) {
continue;
}
if (r == r1 || c == c1 || abs(c - c1) == abs(r - r1)) {
u8 length = max(abs(r - r1), abs(c - c1));
if (length > 15) {
continue;
}
addVBoxes(r, c, color, length, r1, c1);
}
}
} else {
cells[r][c].color = 0;
ccells[color].erase({r, c});
}
}
inline void addColorCell(u8 r, u8 c, u8 color) {
modifyColorCell(r, c, color, 1);
}
inline void deleteColorCell(u8 r, u8 c, u8 color) {
modifyColorCell(r, c, color, -1);
}
inline void getCellVecs(u8 r, u8 c, u8 color, tilev_t &v, bool transparent = false) {
u8 ccolor = cells[r][c].color;
if (ccolor == color) {
return;
}
if (transparent && ccolor != 0) {
return;
}
v.a[0].push_back({r, c, ccolor});
v.a[1].push_back({r, c, color});
}
inline void getTileVecs(const char *tile, tilev_t &v, bool transparent = false) {
u8 r = tile[0] - 'A';
u8 c = tile[1] - 'a';
for (u8 i = 0; i < 6; i++) {
u8 color = tile[2 + i] - '0';
if (tile[8] == 'h') {
getCellVecs(r, c + i, color, v, transparent);
getCellVecs(r + 1, c + 5 - i, color, v, transparent);
} else {
getCellVecs(r + i, c + 1, color, v, transparent);
getCellVecs(r + 5 - i, c, color, v, transparent);
}
}
}
tilev_t placeTileInCells(const char *tile, bool transparent = false) { // Eg: Hh216534h
tilev_t v;
getTileVecs(tile, v, transparent);
vector <u8a3_t> del = v.a[0];
vector <u8a3_t> add = v.a[1];
for (size_t i = 0; i < del.size(); i++) {
deleteColorCell(del[i].a[0], del[i].a[1], del[i].a[2]);
}
for (size_t i = 0; i < add.size(); i++) {
addColorCell(add[i].a[0], add[i].a[1], add[i].a[2]);
}
return v;
}
void undoPlaceTileInCells(tilev_t v) {
vector <u8a3_t> del = v.a[1];
vector <u8a3_t> add = v.a[0];
for (size_t i = 0; i < del.size(); i++) {
deleteColorCell(del[i].a[0], del[i].a[1], del[i].a[2]);
}
for (size_t i = 0; i < add.size(); i++) {
addColorCell(add[i].a[0], add[i].a[1], add[i].a[2]);
}
}
#define DF(n, tn) ((tn == 0) ? 1.0 : (1.0 - ((double) n / (double) tn)))
inline sscore_t shapeScores(u8 color, int nNmoves) {
sscore_t scores = {0, 0, 0, 0, 0, 0};
vector <set <u8pair>> prune;
for (auto it = cstate[color].vbox.begin(); it != cstate[color].vbox.end(); it++) {
set <u8pair> vbox = it->first;
u8 length = it->second;
u8 count = 0;
double vscore = 0;
vector <double> sameDFs;
vector <double> missingDFs;
for (auto it1 = vbox.begin(); it1 != vbox.end(); it1++) {
u8 r = it1->first;
u8 c = it1->second;
u8 dMoves = nDMoves(r, c);
double df = DF(dMoves, nNmoves);
if (cells[r][c].color == color) {
vscore += length * df;
count++;
sameDFs.push_back(df);
} else {
missingDFs.push_back(df);
}
}
if (count == 4) {
if (sameDFs[0] == 1 && sameDFs[1] == 1 && sameDFs[2] == 1 && sameDFs[3] == 1) {
scores.sqScore += vscore * 2;
scores.nSquares++;
} else {
if (color == secret) {
} else {
scores.sqScore += vscore;
scores.nSquares++;
}
}
} else if (count == 3) {
if (missingDFs[0] != 1) {
if (sameDFs[0] == 1 && sameDFs[1] == 1 && sameDFs[2] == 1) {
scores.trScore += vscore * 2;
scores.nTriangles++;
} else {
if (color == secret) {
scores.trScore += vscore / 2;
scores.nTriangles++;
} else {
scores.trScore += vscore;
scores.nTriangles++;
}
}
}
} else if (count == 2) {
if (missingDFs[0] != 1 && missingDFs[1] != 1) {
if (sameDFs[0] == 1 && sameDFs[1] == 1) {
scores.liScore += vscore * 2;
scores.nLines++;
} else {
if (color == secret) {
scores.liScore += vscore / 2;
scores.nLines++;
} else {
scores.liScore += vscore;
scores.nLines++;
}
}
}
} else {
prune.push_back(vbox);
}
}
for (u8 i = 0; i < prune.size(); i++) {
cstate[color].vbox.erase(prune[i]);
}
return scores;
}
void evalMove(const char *tile, move_t *move) {
tilev_t v1 = placeTileInCells(tile);
move_t nextMoves[512];
int nNmoves = findValidMoves(nextMoves);
for (u8 color = 1; color <= 6; color++) {
sscore_t scores = shapeScores(color, nNmoves);
move->score[color] = (100 * scores.sqScore) + (10 * scores.trScore) + (1 * scores.liScore);
move->s[color] = scores;
}
move->e = 0;
undoPlaceTileInCells(v1);
}
void weightedScoresMove(move_t moves[512], int nMoves, const char *input) { // Eg: 364521
double mm[7] = {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX};
mm[secret] = INT_MIN;
int mmI[7] = {-1, -1, -1, -1, -1, -1, -1};
for (int i = 0; i < nMoves; i++) {
for (u8 c = 1; c <= 6; c++) {
if (c == secret) {
if (moves[i].score[c] > mm[c]) {
mm[c] = moves[i].score[c];
mmI[c] = i;
}
} else {
if (moves[i].score[c] < mm[c]) {
mm[c] = moves[i].score[c];
mmI[c] = i;
}
}
}
}
for (int c = 1; c <= 6; c++) {
move_t move = moves[mmI[c]];
LOG("c = %d, s = [%5.0f %5.0f %5.0f %5.0f %5.0f %5.0f], m = [%2d,%2d,%2d]", c, move.score[1], move.score[2], move.score[3], move.score[4], move.score[5], move.score[6], move.r, move.c, move.d);
}
bool inc[7] = {false, false, false, false, false, false, false};
inc[secret] = true;
if (maxOCSquares > 0) {
for (int c = 1; c <= 6; c++) {
if (rSQ[c] >= maxOCSquares) {
inc[c] = true;
}
}
} else {
for (int c = 1; c <= 6; c++) {
inc[c] = true;
}
}
LOG("inc = [%d %d %d %d %d %d]", inc[1], inc[2], inc[3], inc[4], inc[5], inc[6]);
double me = INT_MAX;
int meI = -1;
for (int i = 0; i < nMoves; i++) {
for (int c = 1; c <= 6; c++) {
if (!inc[c]) continue;
moves[i].e += (moves[i].score[c] - mm[c]) * (moves[i].score[c] - mm[c]);
}
if (moves[i].e < me) {
me = moves[i].e;
meI = i;
}
}
move_t move = moves[meI];
LOG("inc c, s = [%5.0f %5.0f %5.0f %5.0f %5.0f %5.0f], m = [%2d,%2d,%2d]", move.score[1], move.score[2], move.score[3], move.score[4], move.score[5], move.score[6], move.r, move.c, move.d);
char tile[10];
snprintf(tile, 10, "%c%c%s%c", move.r + 'A', move.c + 'a', input, move.d ? 'v' : 'h');
LOG("place my tile [%s]", tile);
placeTileInCells(tile);
char output[4];
snprintf(output, 4, "%c%c%c", move.r + 'A', move.c + 'a', move.d ? 'v' : 'h');
printf("%s\n", output); // output move
fflush(stdout);
}
void findMove(const char *input) { // Eg: 364521
move_t moves[512];
int nMoves = findValidMoves(moves);
if (nMoves == 0) {
LOG("no more moves");
return;
}
for (int i = 0; i < nMoves; i++) {
move_t *move = &moves[i];
char tile[10];
snprintf(tile, 10, "%c%c%s%c", move->r + 'A', move->c + 'a', input, move->d ? 'v' : 'h');
evalMove(tile, move);
}
return weightedScoresMove(moves, nMoves, input);
}
void addMove(const char *input) { // Eg: Hh216534h
placeTileInCells(input);
// update real squares for other colors
for (u8 color = 1; color <= 6; color++) {
sscore_t scores = shapeScores(color, 0);
if (color != secret && scores.nSquares > 0) {
rSQ[color] += scores.nSquares;
if (rSQ[color] > maxOCSquares) {
maxOCSquares = rSQ[color];
}
}
}
}
void init_cells() {
for (u8 r = 0; r < 16; r++) {
for (u8 c = 0; c < 20; c++) {
for (u8 d = 0; d < 2; d++) {
cells[r][c].o[d].reset();
}
cells[r][c].color = 0;
cells[r][c].sc.clear();
}
}
for (u8 d = 0; d < 2; d++) {
u8 mr = (d == 0) ? 15 : 11;
u8 mc = (d == 0) ? 15 : 19;
for (u8 r = 0; r < mr; r++) {
for (u8 c = 0; c < mc; c++) {
for (u8 i = 0; i < 6; i++) {
if (d == 0) {
cells[r][c + i].sc.push_back({r, c, 0, i});
cells[r + 1][c + 5 - i].sc.push_back({r, c, 0, (u8)(6 + i)});
} else{
cells[r + i][c + 1].sc.push_back({r, c, 1, i});
cells[r + 5 - i][c].sc.push_back({r, c, 1, (u8)(6 + i)});
}
}
}
}
}
}
int main(int argc, char *argv[]) {
init_cells();
if (scanf("%d", &secret)) {} // Eg: 3
LOG("secret = %d", secret);
char input[10];
int len = 0;
do {
if (scanf("%s", input)) {}
len = strlen(input);
if (len == 9) { // Eg: Hh216534h
LOG("place given tile [%s]", input);
addMove(input);
} else if (len == 6) { // Eg: 364521
LOG("find move for [%s]", input);
findMove(input);
} else if (len == 5) { // Start
player1 = true;
LOG("player 1");
} else if (len == 4) { // Quit
LOG("Quit");
break;
} else {
LOG("invalid input [%s]", input);
return 1;
}
} while (true);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment