#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#include <vector>

#include <helianthus.h>

#define CELLSIZE 64


int baseItems[][5][5] = {
  {
    { 1, 1, 1, 1, 1 }
  }, {
    { 1, 1, 1, 1 },
    { 1, 1 }
  }, {
    { 1, 1, 1, 1 },
    { 0, 1 }
  }, {
    { 1, 1 },
    { 1, 1 }
  }, {
    { 0, 1, 1, 1 },
    { 1, 1 }
  }, {
    { 1, 1, 1 },
    { 1, 0, 1 }
  }, {
    { 0, 0, 1 },
    { 1, 1, 1 },
    { 1, 0, 0 }
  }, {
    { 1, 1, 1 },
    { 1, 1, 0 }
  }, {
    { 0, 1, 0 },
    { 1, 1, 1 },
    { 1, 0, 0 }
  }, {
    { 0, 1, 0 },
    { 1, 1, 1 },
    { 0, 1, 0 }
  }, {
    { 0, 0, 1, 1 },
    { 0, 1, 1 },
    { 1, 1 }
  }, {
    { 1, 1, 1 },
    { 0, 1 },
  }, {
    { 1, 1, 1 },
    { 1 },
  }
};

const char *colors[] = {
  "red",
  "green",
  "yellow",
  "white",
  "green",
  "blue",
  "blue",
  "red",
  "green",
  "red",
  "yellow",
  "blue",
  "yellow"
};

const int itemCount = sizeof(baseItems)/sizeof(*baseItems);

struct Variant {
  int h, w;
  int dc;
  int map[5][5];
  Variant() { memset(this, 0, sizeof(*this)); }
};

struct Item {
  int id;
  int count;
  Variant variants[8];
  Item **prev, *next;
  Item(): id(), count(), prev(), next() { }
};

struct Cell {
  int value;
  int r, c;
  Cell **prev, *next;
  Cell(): value(), r(), c(), prev(), next() { }
  operator int() { return value; }
};

struct Board {
  Cell *first;
  Cell map[8][8];

  Board() { init(); }

  void init() {
    first = &map[0][0];
    Cell **prev = &first;
    for(int i = 0; i < 8*8; ++i) {
      int r = i/8, c = i%8;
      Cell &cell = map[r][c];
      cell.value = 0;
      cell.r = r;
      cell.c = c;
      *prev = &cell;
      cell.prev = prev;
      prev = &cell.next;
      cell.next = NULL;
    }
  }

  bool put(int r, int c, int id) {
    if (!id) return false;
    Cell &cell = map[r][c];
    if (cell) return false;
    cell.value = id;
    *cell.prev = cell.next;
    if (cell.next) cell.next->prev = cell.prev;
    return true;
  }

  bool reset(int r, int c) {
    Cell &cell = map[r][c];
    if (!cell) return false;
    cell.value = 0;
    *cell.prev = &cell;
    if (cell.next) cell.next->prev = &cell.next;
    return true;
  }

  void print() {
    printf("--------------------------\n");
    for(int r = 0; r < 8; ++r) {
      printf("  ");
      for(int c = 0; c < 8; ++c)
        printf("%3d", map[r][c].value);
      printf("\n");
    }
    printf("--------------------------\n");
    fflush(stdout);
  }
};


void prepareItems(std::list<Item> &items, std::vector<Item*> &pointers, Item **prev) {
  for(int i = 0; i < itemCount; ++i) {
    int h = 0, w = 0;
    for(int r = 0; r < 5; ++r)
      for(int c = 0; c < 5; ++c)
        if (baseItems[i][r][c])
          { h = std::max(h, r+1); w = std::max(w, c+1); }

    items.push_back(Item());
    Item &ii = items.back();
    pointers.push_back(&ii);
    ii.id = (int)items.size();
    ii.prev = prev;
    *prev = &ii;
    prev = &ii.next;
    for(int fv = 0; fv <= 1; ++fv) {
      for(int fh = 0; fh <= 1; ++fh) {
        for(int t = 0; t <= 1; ++t) {
          Variant &v = ii.variants[ ii.count ];
          v.h = t ? w : h;
          v.w = t ? h : w;
          v.dc = v.w-1;
          for(int r = 0; r < h; ++r) {
            for(int c = 0; c < w; ++c) {
              int rr = fv ? h-r-1 : r;
              int cc = fh ? w-c-1 : c;
              if (t) std::swap(rr, cc);
              v.map[rr][cc] = baseItems[i][r][c];
              if (rr == 0 && v.map[rr][cc] && v.dc > cc) v.dc = cc;
            }
          }

          bool duplicate = false;
          for(int vi = 0; vi < ii.count; ++vi) {
            bool d = (v.h == ii.variants[vi].h && v.w == ii.variants[vi].w);
            for(int r = 0; r < v.h; ++r)
              for(int c = 0; c < v.w; ++c)
                if (v.map[r][c] != ii.variants[vi].map[r][c]) d = false;
            if (d) duplicate = true;
          }

          if (!duplicate) {
            ++ii.count;
            //for(int r = 0; r < v.h; ++r) {
            //  for(int c = 0; c < v.w; ++c)
            //    printf(v.map[r][c] ? "#" : " ");
            //  printf("\n");
            //}
            //printf("\n");
          }
        }
      }
    }
  }
}


Item *first = NULL;
std::list<Item> items;
std::vector<Item*> pointers;
Board board;
int levels[10000000];
int sublevels[10000000];


long long iteration = 0;
long long variants = 0;
void nextIteration() {
  if (((++iteration) % 1000000) == 0) {
    printf("%lld / %lld:", variants, iteration);
    for(int i = 0; levels[i]; ++i)
      printf(" %d%c", levels[i], 'a' + (char)sublevels[i]);
    printf("\n");
    fflush(stdout);
  }
}


void restart(bool shuffle = false) {
  iteration = 0;
  variants = 0;
  memset(levels, 0, sizeof(levels));
  memset(sublevels, 0, sizeof(levels));
  first = NULL;
  if (shuffle) {
    for(int i = 0; i < 2*(int)pointers.size(); ++i)
      std::swap(pointers[rand()%pointers.size()], pointers[rand()%pointers.size()]);
    for(std::list<Item>::iterator i = items.begin(); i != items.end(); ++i)
      for(int j = 0; j < 2*i->count; ++j)
        std::swap(i->variants[rand() % i->count], i->variants[rand() % i->count]);
  }

  board.init();
  Item **prev = &first;
  for(std::vector<Item*>::iterator i = pointers.begin(); i != pointers.end(); ++i) {
    (*i)->prev = prev;
    *prev = *i;
    prev = &((*i)->next);
    (*i)->next = NULL;
  }
}


void process(int level = 0, int id = 0, int row = 0, int col = 0) {
  if (!first || !board.first) {
    ++variants;
    //board.print(); fgetc(stdin);
  }
  //nextIteration();

  for(Item *i = first; i; i = i->next) {
    if (id && i->id != id) continue;

    *(i->prev) = i->next;
    if (i->next) i->next->prev = i->prev;
    levels[level] = i->id;

    for(int vi = 0; vi < i->count; ++vi) {
      Variant &v = i->variants[vi];
      sublevels[level] = vi;
      int rr = id ? row : board.first->r;
      int cc = id ? col : board.first->c - v.dc;
      if (cc < 0 || rr + v.h > 8 || cc + v.w > 8) continue;

      bool success = true;
      int placed = 0;
      for(int r = 0; r < v.h && success; ++r)
        for(int c = 0; c < v.w; ++c, ++placed)
          if (v.map[r][c] && !board.put(rr+r, cc+c, i->id))
            { success = false; break; }

      if (success) {
        //printf("level %d item %d variant %d\n", level, i->id, vi);
        //board.print();
        //fgetc(stdin);
        process(level + 1);
        if (variants) return;
      }

      for(int r = 0; r < v.h && placed > 0; ++r)
        for(int c = 0; c < v.w && placed > 0; ++c, --placed)
          if (v.map[r][c]) board.reset(rr+r, cc+c);
      //if (!level) break;
    }


    levels[level] = 0;
    *(i->prev) = i;
    if (i->next) i->next->prev = &i->next;
  }
}


int sqr = 3, sqc = 3;
void generateRandom(bool center = false) {
  restart(true);
  process(0, (center ? 4 : 0), sqr, sqc);
}


void init() {
  srand(time(NULL));
  prepareItems(items, pointers, &first);
  generateRandom(true);
  background(colorByName("black"));
}


void draw() {
  saveState();
  zoom(CELLSIZE);
  noStroke();

  if (keyWentDown("space")) {
    sqr = randomNumber(0, 6);
    sqc = randomNumber(0, 6);
    generateRandom(true);
  }
  if (keyWentDown("enter")) generateRandom(true);
  if (keyWentDown("up")    && sqr > 0) { --sqr; generateRandom(true); }
  if (keyWentDown("down")  && sqr < 6) { ++sqr; generateRandom(true); }
  if (keyWentDown("left")  && sqc > 0) { --sqc; generateRandom(true); }
  if (keyWentDown("right") && sqc < 6) { ++sqc; generateRandom(true); }

  double b = 2.0/CELLSIZE;
  for(int r = 0; r < 8; ++r) {
    for(int c = 0; c < 8; ++c) {
      int id = board.map[r][c].value;
      if (id) {
        fill(colorByName(colors[id-1]));
        rect(c+b, r+b, 1-b-b, 1-b-b);
        bool t = r > 0 && board.map[r-1][c].value == id;
        bool l = c > 0 && board.map[r][c-1].value == id;

        if (t) rect(c+b, r-0.5+b, 1-b-b, 1-b-b);
        if (l) rect(c-0.5+b, r+b, 1-b-b, 1-b-b);
        if (t && l && board.map[r-1][c-1].value == id)
            rect(c-0.5+b, r-0.5+b, 1-b-b, 1-b-b);
      }
    }
  }

  restoreState();
}


int main() {
  windowSetTitle("Press Enter, Space or arrows");
  windowSetVariableFrameRate();
  windowSetSize(CELLSIZE*8, CELLSIZE*8);
  windowSetInit(&init);
  windowSetDraw(&draw);
  windowRun();
  return 0;
}