/*
TODO:
  - Omezit v LOOPu vše co jde a počítat pouze backtracking návraty
  - fprintf STDERR
  - bigger debug with more info levels
  - aplikovat posunutí jako operaci
*/

/* ---------------------------------------
ABOUT:
  - a program that gets predefined macros (compiled in) as an input and
    plays "Bejeweled" game in reverse. That means, it is given a final
    configuration, and it tries to determine original field, where was
    always only one possible move.
  - made by Michal Schorm, 2017
   ---------------------------------------
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include <stdbool.h>
//#include <time.h>    // time(NULL)


// ---------------------------------------
// Define height and width of the play field
#define HEIGHT 11
#define WIDTH 13
int SIZE = HEIGHT*WIDTH;

#define PLACEHOLDER '.'            // character that fills emtpy fields
#define COLOR_COUNT 5              // number of different gems

// Create structure for history operations
typedef struct history
{
 char field[HEIGHT][WIDTH];
 struct history * history_older;

 int orientation, position, combination, type;
 int x1, y1, x2, y2, x3, y3;

} history;

history * history_latest = NULL;

int history_stack = 0;

// ---------------------------------------

void print_field() // printf field, with newline and borders
{
 printf("\n");
 for( int x=0 ; x<HEIGHT ; x++)
  {
   printf("| ");
   for( int y=0 ; y<WIDTH ; y++) printf("%c ", history_latest->field[x][y]);
   printf("|\n");
  }

  // bottom border
  for( int x=0 ; x<=WIDTH ; x++) printf("--");
  printf("-\n");
}

// ---------------------------------------

void save_history()
{
 history * history_entry = malloc( sizeof(history) );
 memcpy(history_entry->field, history_latest->field, SIZE);
 history_entry->orientation = history_entry->position = history_entry->combination = history_entry->type = 0;
 history_entry->history_older = history_latest;
 history_latest = history_entry;
}

void load_history()
{
 memcpy(history_latest->field, history_latest->history_older->field, SIZE);
}

void delete_last_history_entry()
{
 if( history_latest == NULL || history_latest->history_older == NULL || history_latest->history_older->history_older == NULL )
   {
    fprintf(stderr, "\n\n\tFATAL ERROR: more LOAD than SAVE\n\n");
    exit(1);
   }
 history * history_entry = history_latest;
 history_latest = history_latest->history_older;
 history_stack++;
 free( history_entry );
}

void initialize_history()
{
 history * history_entry = malloc( sizeof(history) );
 // Fill the field with placeholder character
 for( int x=0 ; x<HEIGHT ; x++) for( int y=0 ; y<WIDTH ; y++) history_entry->field[x][y]=PLACEHOLDER;
 history_entry->history_older = NULL;
 history_entry->orientation = history_entry->position = history_entry->combination = history_entry->type = 0;
 history_latest = history_entry;

 // HERE is the place to set initial field pattern:

 history_entry->field[HEIGHT-1][WIDTH-5] = 'A';
 history_entry->field[HEIGHT-1][WIDTH-4] = 'A';
 history_entry->field[HEIGHT-1][WIDTH-2] = 'A';
 history_entry->field[HEIGHT-2][WIDTH-4] = 'A';
 history_entry->field[HEIGHT-1][WIDTH-1] = 'D';

 history_entry->field[HEIGHT-3][WIDTH-3] = 'B';
 history_entry->field[HEIGHT-2][WIDTH-3] = 'B';
 history_entry->field[HEIGHT-1][WIDTH-3] = 'B';

 history_entry->x1 = HEIGHT-3;
 history_entry->x2 = HEIGHT-2;
 history_entry->x3 = HEIGHT-1;
 history_entry->y1 = history_entry->y2 = history_entry->y3 = WIDTH-3;

 save_history();
}

// ---------------------------------------


int check_number_of_moves()
{
 int number = 0;

// check for:   O
//              O
//              O
 for( int x=0 ; x<HEIGHT-2 ; x++)
  {
   for( int y=0 ; y<WIDTH ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x+1][y] && history_latest->field[x+1][y] == history_latest->field[x+2][y]) number++;
    }
  } //-----------------

/*/ check for:   O      O       O
//               O        O       O
//                 O    O         O
 for( int x=0 ; x<HEIGHT-2 ; x++)
  {
   for( int y=0 ; y<WIDTH-1 ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x+1][y] && history_latest->field[x+1][y] == history_latest->field[x+2][y+1]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y+1] && history_latest->field[x+1][y+1] == history_latest->field[x+2][y+1]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y+1] && history_latest->field[x+1][y+1] == history_latest->field[x+2][y]) number++;
    }
  } //-----------------

// check for:   O      O       O
//              O    O       O
//            O        O     O
 for( int x=0 ; x<HEIGHT-2 ; x++)
  {
   for( int y=1 ; y<WIDTH ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x+1][y] && history_latest->field[x+1][y] == history_latest->field[x+2][y-1]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y-1] && history_latest->field[x+1][y-1] == history_latest->field[x+2][y-1]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y-1] && history_latest->field[x+1][y-1] == history_latest->field[x+2][y]) number++;
    }
  } //-----------------

*/
// check for:
//               OOO
//
 for( int x=0 ; x<HEIGHT ; x++)
  {
   for( int y=0 ; y<WIDTH-2 ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x][y+1] && history_latest->field[x][y+1] == history_latest->field[x][y+2]) number++;
    }
  } //-----------------

/*/ check for:
//             OO      O   O    O
//                O      O        OO
 for( int x=0 ; x<HEIGHT-1 ; x++)
  {
   for( int y=0 ; y<WIDTH-2 ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x][y+1] && history_latest->field[x][y+1] == history_latest->field[x+1][y+2]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y+1] && history_latest->field[x+1][y+1] == history_latest->field[x+1][y+2]) number++;
     if(history_latest->field[x][y] == history_latest->field[x+1][y+1] && history_latest->field[x+1][y+1] == history_latest->field[x][y+2]) number++;
    }
  } //-----------------

// check for:     0      0        00
//             0O      O   0    O
//
 for( int x=1 ; x<HEIGHT ; x++)
  {
   for( int y=0 ; y<WIDTH-2 ; y++)
    {
     if(history_latest->field[x][y]==PLACEHOLDER) continue;
     if(history_latest->field[x][y] == history_latest->field[x][y+1] && history_latest->field[x][y+1] == history_latest->field[x-1][y+2]) number++;
     if(history_latest->field[x][y] == history_latest->field[x-1][y+1] && history_latest->field[x-1][y+1] == history_latest->field[x-1][y+2]) number++;
     if(history_latest->field[x][y] == history_latest->field[x-1][y+1] && history_latest->field[x-1][y+1] == history_latest->field[x][y+2]) number++;
    }
  } //-----------------
/*/

 return number;
}

// ---------------------------------------

void generate_step()
{

 int starting_field_x, starting_field_y;

 POSITION:
 COMBINATION:
 if( history_latest->position == 0)
   {
    starting_field_x = history_latest->history_older->x1;
    starting_field_y = history_latest->history_older->y1;
    if( history_latest->combination == 0 ) history_latest->combination++;
   }
 else if( history_latest->position == 1)
   {
    starting_field_x = history_latest->history_older->x2;
    starting_field_y = history_latest->history_older->y2;
   }
 else
   {
    starting_field_x = history_latest->history_older->x3;
    starting_field_y = history_latest->history_older->y3;
   }

/*
printf("\n-----------------------------------------------------------------------");
printf("\ntype:\t%d\ncombination:\t%d\nposition:\t%d", history_latest->type, history_latest->combination, history_latest->position);

int i=0;
history * h = history_latest;
while(h->history_older != NULL )
{
h = h->history_older;
i++;
}

printf("\nStack depth:\t%d\n", i);
*/
//print_field();



 switch( history_latest->combination )
   {
    // Fallthrough is expected here

    case 0: // bot bot
         starting_field_x++;
    case 1: // mid vertical
         starting_field_x++;
    case 2: // top top

         // check ALL constraints
         if( !( starting_field_x < HEIGHT &&
                starting_field_x-3 >= 0 &&
                history_latest->field[2][starting_field_y] == PLACEHOLDER
              ) ) goto NEXT;

         // make space for the elements
         for(int x=3 ; x<=starting_field_x ; x++ )
           history_latest->field[x-3][starting_field_y] = history_latest->field[x][starting_field_y];

         // insert new triplet into field
         history_latest->x1 = starting_field_x-2;
         history_latest->x2 = starting_field_x-1;
         history_latest->x3 = starting_field_x;
         history_latest->y1 = history_latest->y2 = history_latest->y3 = starting_field_y;
         TYPE_1:
         history_latest->field[history_latest->x1][history_latest->y1] = history_latest->field[history_latest->x2][history_latest->y2] = history_latest->field[history_latest->x3][history_latest->y3] = history_latest->type+'A';

         break;

    case 3: // left left
         starting_field_y--;
    case 4: // mid left
         starting_field_y--;
    case 5: // right right

         // check ALL constraints
         if( !( starting_field_y >= 0 &&
                starting_field_y+3 < WIDTH &&
                history_latest->field[0][starting_field_y] == PLACEHOLDER &&
                history_latest->field[0][starting_field_y+1] == PLACEHOLDER &&
                history_latest->field[0][starting_field_y+2] == PLACEHOLDER
              ) ) goto NEXT;
         if( starting_field_x != HEIGHT-1 &&
             ( history_latest->field[starting_field_x+1][starting_field_y] == PLACEHOLDER ||
               history_latest->field[starting_field_x+1][starting_field_y+1] == PLACEHOLDER ||
               history_latest->field[starting_field_x+1][starting_field_y+2] == PLACEHOLDER
             ) ) goto NEXT;

         // make space for the elements
         for(int y=starting_field_y ; y<=starting_field_y+2 ; y++)
           for(int x=1 ; x<=starting_field_x ; x++ )
              history_latest->field[x-1][y] = history_latest->field[x][y];

         // insert new triplet into field
         history_latest->y1 = starting_field_y;
         history_latest->y2 = starting_field_y+1;
         history_latest->y3 = starting_field_y+2;
         history_latest->x1 = history_latest->x2 = history_latest->x3 = starting_field_x;
         TYPE_2:
         history_latest->field[starting_field_x][starting_field_y] = history_latest->field[starting_field_x][starting_field_y+1] = history_latest->field[starting_field_x][starting_field_y+2] = history_latest->type+'A';

         break;

   } // switch





         // check, if there is really only one move to UNDO, what I did.
         if( check_number_of_moves() != 1 )
           {
            if(history_latest->type < COLOR_COUNT-1)
              {
               history_latest->type++;
               if(history_latest->combination < 3 ) goto TYPE_1;
               else goto TYPE_2;
              }
            NEXT:
            if( history_latest->combination == 5 &&
                history_latest->position == 2 )
              {
               delete_last_history_entry();
//printf("\nDELETE\n");
               goto POSITION;
              }
            else if(history_latest->combination < 5)
              {
               load_history();
               history_latest->type = 0;
               history_latest->combination++;
               goto COMBINATION;
              }
            else if(history_latest->position < 2)
              {
               load_history();
               history_latest->type = 0;
               history_latest->combination = 0;
               history_latest->position++;
               goto POSITION;
              }
           }
         else if( history_stack != 0 )
           {
            history_stack--;
            save_history();
            goto POSITION;
           }
         else save_history();


}

// ---------------------------------------

int main()
{
 initialize_history();

 print_field();
 printf("\n %d", check_number_of_moves());

 for(int i=0; i<12; i++)
   {
    generate_step();
   }


 printf("\n FINAL: ------------------------\n");
 print_field();
 printf("\n %d\n", check_number_of_moves());


}