|
|
261920 |
|
|
|
261920 |
#include <ctime></ctime>
|
|
|
261920 |
#include <cstdio></cstdio>
|
|
|
261920 |
#include <cstring></cstring>
|
|
|
261920 |
#include <algorithm></algorithm>
|
|
|
261920 |
#include <list></list>
|
|
|
261920 |
#include <vector></vector>
|
|
|
261920 |
|
|
|
261920 |
#include <helianthus.h></helianthus.h>
|
|
|
261920 |
|
|
|
261920 |
#define CELLSIZE 64
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
int baseItems[][5][5] = {
|
|
|
261920 |
{
|
|
|
261920 |
{ 1, 1, 1, 1, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1, 1 },
|
|
|
261920 |
{ 1, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1, 1 },
|
|
|
261920 |
{ 0, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1 },
|
|
|
261920 |
{ 1, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 0, 1, 1, 1 },
|
|
|
261920 |
{ 1, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 1, 0, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 0, 0, 1 },
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 1, 0, 0 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 1, 1, 0 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 0, 1, 0 },
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 1, 0, 0 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 0, 1, 0 },
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 0, 1, 0 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 0, 0, 1, 1 },
|
|
|
261920 |
{ 0, 1, 1 },
|
|
|
261920 |
{ 1, 1 }
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 0, 1 },
|
|
|
261920 |
}, {
|
|
|
261920 |
{ 1, 1, 1 },
|
|
|
261920 |
{ 1 },
|
|
|
261920 |
}
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
const char *colors[] = {
|
|
|
261920 |
"red",
|
|
|
261920 |
"green",
|
|
|
261920 |
"yellow",
|
|
|
261920 |
"white",
|
|
|
261920 |
"green",
|
|
|
261920 |
"blue",
|
|
|
261920 |
"blue",
|
|
|
261920 |
"red",
|
|
|
261920 |
"green",
|
|
|
261920 |
"red",
|
|
|
261920 |
"yellow",
|
|
|
261920 |
"blue",
|
|
|
261920 |
"yellow"
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
const int itemCount = sizeof(baseItems)/sizeof(*baseItems);
|
|
|
261920 |
|
|
|
261920 |
struct Variant {
|
|
|
261920 |
int h, w;
|
|
|
261920 |
int dc;
|
|
|
261920 |
int map[5][5];
|
|
|
261920 |
Variant() { memset(this, 0, sizeof(*this)); }
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
struct Item {
|
|
|
261920 |
int id;
|
|
|
261920 |
int count;
|
|
|
261920 |
Variant variants[8];
|
|
|
261920 |
Item **prev, *next;
|
|
|
261920 |
Item(): id(), count(), prev(), next() { }
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
struct Cell {
|
|
|
261920 |
int value;
|
|
|
261920 |
int r, c;
|
|
|
261920 |
Cell **prev, *next;
|
|
|
261920 |
Cell(): value(), r(), c(), prev(), next() { }
|
|
|
261920 |
operator int() { return value; }
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
struct Board {
|
|
|
261920 |
Cell *first;
|
|
|
261920 |
Cell map[8][8];
|
|
|
261920 |
|
|
|
261920 |
Board() { init(); }
|
|
|
261920 |
|
|
|
261920 |
void init() {
|
|
|
261920 |
first = &map[0][0];
|
|
|
261920 |
Cell **prev = &first;
|
|
|
261920 |
for(int i = 0; i < 8*8; ++i) {
|
|
|
261920 |
int r = i/8, c = i%8;
|
|
|
261920 |
Cell &cell = map[r][c];
|
|
|
261920 |
cell.value = 0;
|
|
|
261920 |
cell.r = r;
|
|
|
261920 |
cell.c = c;
|
|
|
261920 |
*prev = &cell;
|
|
|
261920 |
cell.prev = prev;
|
|
|
261920 |
prev = &cell.next;
|
|
|
261920 |
cell.next = NULL;
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
bool put(int r, int c, int id) {
|
|
|
261920 |
if (!id) return false;
|
|
|
261920 |
Cell &cell = map[r][c];
|
|
|
261920 |
if (cell) return false;
|
|
|
261920 |
cell.value = id;
|
|
|
261920 |
*cell.prev = cell.next;
|
|
|
261920 |
if (cell.next) cell.next->prev = cell.prev;
|
|
|
261920 |
return true;
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
bool reset(int r, int c) {
|
|
|
261920 |
Cell &cell = map[r][c];
|
|
|
261920 |
if (!cell) return false;
|
|
|
261920 |
cell.value = 0;
|
|
|
261920 |
*cell.prev = &cell;
|
|
|
261920 |
if (cell.next) cell.next->prev = &cell.next;
|
|
|
261920 |
return true;
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
void print() {
|
|
|
261920 |
printf("--------------------------\n");
|
|
|
261920 |
for(int r = 0; r < 8; ++r) {
|
|
|
261920 |
printf(" ");
|
|
|
261920 |
for(int c = 0; c < 8; ++c)
|
|
|
261920 |
printf("%3d", map[r][c].value);
|
|
|
261920 |
printf("\n");
|
|
|
261920 |
}
|
|
|
261920 |
printf("--------------------------\n");
|
|
|
261920 |
fflush(stdout);
|
|
|
261920 |
}
|
|
|
261920 |
};
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
void prepareItems(std::list<item> &items, std::vector<item*> &pointers, Item **prev) {</item*></item>
|
|
|
261920 |
for(int i = 0; i < itemCount; ++i) {
|
|
|
261920 |
int h = 0, w = 0;
|
|
|
261920 |
for(int r = 0; r < 5; ++r)
|
|
|
261920 |
for(int c = 0; c < 5; ++c)
|
|
|
261920 |
if (baseItems[i][r][c])
|
|
|
261920 |
{ h = std::max(h, r+1); w = std::max(w, c+1); }
|
|
|
261920 |
|
|
|
261920 |
items.push_back(Item());
|
|
|
261920 |
Item &ii = items.back();
|
|
|
261920 |
pointers.push_back(&ii);
|
|
|
261920 |
ii.id = (int)items.size();
|
|
|
261920 |
ii.prev = prev;
|
|
|
261920 |
*prev = â…ˆ
|
|
|
261920 |
prev = &ii.next;
|
|
|
261920 |
for(int fv = 0; fv <= 1; ++fv) {
|
|
|
261920 |
for(int fh = 0; fh <= 1; ++fh) {
|
|
|
261920 |
for(int t = 0; t <= 1; ++t) {
|
|
|
261920 |
Variant &v = ii.variants[ ii.count ];
|
|
|
261920 |
v.h = t ? w : h;
|
|
|
261920 |
v.w = t ? h : w;
|
|
|
261920 |
v.dc = v.w-1;
|
|
|
261920 |
for(int r = 0; r < h; ++r) {
|
|
|
261920 |
for(int c = 0; c < w; ++c) {
|
|
|
261920 |
int rr = fv ? h-r-1 : r;
|
|
|
261920 |
int cc = fh ? w-c-1 : c;
|
|
|
261920 |
if (t) std::swap(rr, cc);
|
|
|
261920 |
v.map[rr][cc] = baseItems[i][r][c];
|
|
|
261920 |
if (rr == 0 && v.map[rr][cc] && v.dc > cc) v.dc = cc;
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
bool duplicate = false;
|
|
|
261920 |
for(int vi = 0; vi < ii.count; ++vi) {
|
|
|
261920 |
bool d = (v.h == ii.variants[vi].h && v.w == ii.variants[vi].w);
|
|
|
261920 |
for(int r = 0; r < v.h; ++r)
|
|
|
261920 |
for(int c = 0; c < v.w; ++c)
|
|
|
261920 |
if (v.map[r][c] != ii.variants[vi].map[r][c]) d = false;
|
|
|
261920 |
if (d) duplicate = true;
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
if (!duplicate) {
|
|
|
261920 |
++ii.count;
|
|
|
261920 |
//for(int r = 0; r < v.h; ++r) {
|
|
|
261920 |
// for(int c = 0; c < v.w; ++c)
|
|
|
261920 |
// printf(v.map[r][c] ? "#" : " ");
|
|
|
261920 |
// printf("\n");
|
|
|
261920 |
//}
|
|
|
261920 |
//printf("\n");
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
Item *first = NULL;
|
|
|
261920 |
std::list<item> items;</item>
|
|
|
261920 |
std::vector<item*> pointers;</item*>
|
|
|
261920 |
Board board;
|
|
|
261920 |
int levels[10000000];
|
|
|
261920 |
int sublevels[10000000];
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
long long iteration = 0;
|
|
|
261920 |
long long variants = 0;
|
|
|
261920 |
void nextIteration() {
|
|
|
261920 |
if (((++iteration) % 1000000) == 0) {
|
|
|
261920 |
printf("%lld / %lld:", variants, iteration);
|
|
|
261920 |
for(int i = 0; levels[i]; ++i)
|
|
|
261920 |
printf(" %d%c", levels[i], 'a' + (char)sublevels[i]);
|
|
|
261920 |
printf("\n");
|
|
|
261920 |
fflush(stdout);
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
void restart(bool shuffle = false) {
|
|
|
261920 |
iteration = 0;
|
|
|
261920 |
variants = 0;
|
|
|
261920 |
memset(levels, 0, sizeof(levels));
|
|
|
261920 |
memset(sublevels, 0, sizeof(levels));
|
|
|
261920 |
first = NULL;
|
|
|
261920 |
if (shuffle) {
|
|
|
261920 |
for(int i = 0; i < 2*(int)pointers.size(); ++i)
|
|
|
261920 |
std::swap(pointers[rand()%pointers.size()], pointers[rand()%pointers.size()]);
|
|
|
261920 |
for(std::list<item>::iterator i = items.begin(); i != items.end(); ++i)</item>
|
|
|
261920 |
for(int j = 0; j < 2*i->count; ++j)
|
|
|
261920 |
std::swap(i->variants[rand() % i->count], i->variants[rand() % i->count]);
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
board.init();
|
|
|
261920 |
Item **prev = &first;
|
|
|
261920 |
for(std::vector<item*>::iterator i = pointers.begin(); i != pointers.end(); ++i) {</item*>
|
|
|
261920 |
(*i)->prev = prev;
|
|
|
261920 |
*prev = *i;
|
|
|
261920 |
prev = &((*i)->next);
|
|
|
261920 |
(*i)->next = NULL;
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
void process(int level = 0, int id = 0, int row = 0, int col = 0) {
|
|
|
261920 |
if (!first || !board.first) {
|
|
|
261920 |
++variants;
|
|
|
261920 |
//board.print(); fgetc(stdin);
|
|
|
261920 |
}
|
|
|
261920 |
//nextIteration();
|
|
|
261920 |
|
|
|
261920 |
for(Item *i = first; i; i = i->next) {
|
|
|
261920 |
if (id && i->id != id) continue;
|
|
|
261920 |
|
|
|
261920 |
*(i->prev) = i->next;
|
|
|
261920 |
if (i->next) i->next->prev = i->prev;
|
|
|
261920 |
levels[level] = i->id;
|
|
|
261920 |
|
|
|
261920 |
for(int vi = 0; vi < i->count; ++vi) {
|
|
|
261920 |
Variant &v = i->variants[vi];
|
|
|
261920 |
sublevels[level] = vi;
|
|
|
261920 |
int rr = id ? row : board.first->r;
|
|
|
261920 |
int cc = id ? col : board.first->c - v.dc;
|
|
|
261920 |
if (cc < 0 || rr + v.h > 8 || cc + v.w > 8) continue;
|
|
|
261920 |
|
|
|
261920 |
bool success = true;
|
|
|
261920 |
int placed = 0;
|
|
|
261920 |
for(int r = 0; r < v.h && success; ++r)
|
|
|
261920 |
for(int c = 0; c < v.w; ++c, ++placed)
|
|
|
261920 |
if (v.map[r][c] && !board.put(rr+r, cc+c, i->id))
|
|
|
261920 |
{ success = false; break; }
|
|
|
261920 |
|
|
|
261920 |
if (success) {
|
|
|
261920 |
//printf("level %d item %d variant %d\n", level, i->id, vi);
|
|
|
261920 |
//board.print();
|
|
|
261920 |
//fgetc(stdin);
|
|
|
261920 |
process(level + 1);
|
|
|
261920 |
if (variants) return;
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
for(int r = 0; r < v.h && placed > 0; ++r)
|
|
|
261920 |
for(int c = 0; c < v.w && placed > 0; ++c, --placed)
|
|
|
261920 |
if (v.map[r][c]) board.reset(rr+r, cc+c);
|
|
|
261920 |
//if (!level) break;
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
levels[level] = 0;
|
|
|
261920 |
*(i->prev) = i;
|
|
|
261920 |
if (i->next) i->next->prev = &i->next;
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
int sqr = 3, sqc = 3;
|
|
|
261920 |
void generateRandom(bool center = false) {
|
|
|
261920 |
restart(true);
|
|
|
261920 |
process(0, (center ? 4 : 0), sqr, sqc);
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
void init() {
|
|
|
261920 |
srand(time(NULL));
|
|
|
261920 |
prepareItems(items, pointers, &first);
|
|
|
261920 |
generateRandom(true);
|
|
|
261920 |
background(colorByName("black"));
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
void draw() {
|
|
|
261920 |
saveState();
|
|
|
261920 |
zoom(CELLSIZE);
|
|
|
261920 |
noStroke();
|
|
|
261920 |
|
|
|
261920 |
if (keyWentDown("space")) {
|
|
|
261920 |
sqr = randomNumber(0, 6);
|
|
|
261920 |
sqc = randomNumber(0, 6);
|
|
|
261920 |
generateRandom(true);
|
|
|
261920 |
}
|
|
|
261920 |
if (keyWentDown("enter")) generateRandom(true);
|
|
|
261920 |
if (keyWentDown("up") && sqr > 0) { --sqr; generateRandom(true); }
|
|
|
261920 |
if (keyWentDown("down") && sqr < 6) { ++sqr; generateRandom(true); }
|
|
|
261920 |
if (keyWentDown("left") && sqc > 0) { --sqc; generateRandom(true); }
|
|
|
261920 |
if (keyWentDown("right") && sqc < 6) { ++sqc; generateRandom(true); }
|
|
|
261920 |
|
|
|
261920 |
double b = 2.0/CELLSIZE;
|
|
|
261920 |
for(int r = 0; r < 8; ++r) {
|
|
|
261920 |
for(int c = 0; c < 8; ++c) {
|
|
|
261920 |
int id = board.map[r][c].value;
|
|
|
261920 |
if (id) {
|
|
|
261920 |
fill(colorByName(colors[id-1]));
|
|
|
261920 |
rect(c+b, r+b, 1-b-b, 1-b-b);
|
|
|
261920 |
bool t = r > 0 && board.map[r-1][c].value == id;
|
|
|
261920 |
bool l = c > 0 && board.map[r][c-1].value == id;
|
|
|
261920 |
|
|
|
261920 |
if (t) rect(c+b, r-0.5+b, 1-b-b, 1-b-b);
|
|
|
261920 |
if (l) rect(c-0.5+b, r+b, 1-b-b, 1-b-b);
|
|
|
261920 |
if (t && l && board.map[r-1][c-1].value == id)
|
|
|
261920 |
rect(c-0.5+b, r-0.5+b, 1-b-b, 1-b-b);
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
restoreState();
|
|
|
261920 |
}
|
|
|
261920 |
|
|
|
261920 |
|
|
|
261920 |
int main() {
|
|
|
261920 |
windowSetTitle("Press Enter, Space or arrows");
|
|
|
261920 |
windowSetVariableFrameRate();
|
|
|
261920 |
windowSetSize(CELLSIZE*8, CELLSIZE*8);
|
|
|
261920 |
windowSetInit(&init);
|
|
|
261920 |
windowSetDraw(&draw);
|
|
|
261920 |
windowRun();
|
|
|
261920 |
return 0;
|
|
|
261920 |
}
|