#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 = ⅈ

    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;

}