//---------------------------------------------------------------------------
#include <vcl\vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void  TForm1::main()
{
 char    *stime[30],*etime[30];
 __int64  tick1,tick2;

      tick1 = GetTickCount();

      Form1->Cursor = crHourGlass;

      fid    = fopen("log.txt","wt");

      time(&t1);
      *stime = ctime(&t1);
      fprintf(fid,"*** pazul started : %s \n",*stime);

      Edit1->Text = *stime;
      Edit3->Text = IntToStr(time(&t2)-t1);

      Form1->Refresh();

      exec();

      tick2 = GetTickCount();
      result = (int) (tick2 -tick1);

      time(&t2);
      *etime = ctime(&t2);
      fprintf(fid,"\n*** pazul  ended  time = %d ms  : %s \n",result,*etime);

      Edit2->Text = *etime;
      Edit3->Text = IntToStr(t2-t1);
      Edit4->Text = IntToStr(result);

      fclose(fid);

  // reset cursor mark
      Form1->Cursor = crDefault;

 }
//---------------------------------------------------------------------------
int    TForm1::bitcount(int n)
{
 int c,w;

       c = 0; w = n;
       while(w != 0) { c++; w &= w - 1; }
       return c;
  }
//---------------------------------------------------------------------------
void    TForm1::exec()
{
 int    k,n;

        tc = 0;

        for (k=1; k<=31; k++)  biton[k] = 1 << (k-1);
        biton[0] = 0x80000000;

        for (Color=2; Color<=10; Color++) {
            Count = 0;
            Pairing(1,Color,1);
         }

  }
//---------------------------------------------------------------------------
void    TForm1::Pairing(int lower,int upper,int m)
{
 int    i,j,k;

        pair[m].lower = lower;
        pair[m].upper = upper;
        pair[m].id    = biton[m] + biton[0];

        if (lower < upper) {
            Pairing(lower+1,upper,m+1);
            Pairing(lower,upper-1,m+1);
            Pairing(lower+1,upper-1,m+1);
            return;
         }
        L = m -1;
        S = (lower == upper)? m : m-1;
        U = L + S;

        for (k=1; k<=S; k++) {
            pair[S+k].lower = pair[L-k+1].upper;
            pair[S+k].upper = pair[L-k+1].lower;
            pair[S+k].id    = pair[L-k+1].id;
         }

        Count++;
        if ((Color >= 99) && (Color <= 4)) {
            fprintf(fid,"\n*** pairing (%d,%d,%d) ***\n",L,U,S);
            for (k=1; k<=U; k++) {
                fprintf(fid,"*** %2d     (%d,%d) \n",k,pair[k].lower,pair[k].upper);
                fflush(fid);
             }
         }

        Candidate();

 }
//---------------------------------------------------------------------------
void    TForm1::Candidate()
{
 int    i,j,k;

        for (k=0; k<1024; k++) {
            if (bitcount(k) != Color)  continue;

            j = 0;
            for (i=10; i>=1; i--) {
                if ((k & biton[i]) != 0)  cand[++j] = i-1;
             }
            cand[0] = j;
            for (i=1; i<=j; i++) if ((cand[j]-cand[1]+10) == cand[i]) break;
            if (i > j)      continue;

            matching();
         }

 }
//---------------------------------------------------------------------------
void    TForm1::matching()
{
 int    k;

        for (k=1; k<=U; k++) {
            if (k <= L) {
                pair[k].val = cand[pair[k].lower] - cand[pair[k].upper];
                continue;
             }
            if (k == S) {
                pair[k].val = 9;
                continue;
             }
                pair[k].val = cand[pair[k].lower] - cand[pair[k].upper] + 9;
                continue;
         }

      //modifiy
        pair[L].id  = biton[0];   pair[L].val--;
        pair[U].id  = biton[0];   pair[U].val++;

        pair[U+1].lower = pair[L].lower;
        pair[U+1].upper = pair[L].upper;
        pair[U+1].id    = biton[L];
        pair[U+1].val   = cand[pair[L].lower] - cand[pair[L].upper];

        pair[U+2].lower = pair[U].lower;
        pair[U+2].upper = pair[U].upper;
        pair[U+2].id    = biton[1];
        pair[U+2].val   = cand[pair[U].lower] - cand[pair[U].upper] + 9;

        pairSize = U + 2;

//        printPair("before equate");

        if (cand[pair[1].upper] == 0) {
            if (Color <= 2)    goto exit;
            for (k=2; k<=U; k++)  if (pair[k].upper != pair[1].upper) break;
            if (k >  L)  goto exit;
            if (k == L) {
                pair[U+3].lower = pair[L].lower;
                pair[U+3].upper = pair[L].upper;
                pair[U+3].id    = biton[0];
                pair[U+3].val   = cand[pair[L].lower] - cand[pair[L].upper];

                pair[U+4].lower = pair[L].upper;
                pair[U+4].upper = pair[L].lower;
                pair[U+4].id    = biton[0];
                pair[U+4].val   = cand[pair[U+4].lower] - cand[pair[U+4].upper] + 9;
                pairSize = U + 4;
                k        = U + 3;
             }
            xequate(k);
            goto exit;
         }
        equate();

   exit:
        pair[L].id  = biton[L] + biton[0];  // restore
        pair[U].id  = biton[1] + biton[0];

        return;
 }
//---------------------------------------------------------------------------
void    TForm1::xequate(int P)
{
 int    au,ai,av,pu,pi,pv;

        au = pair[1].upper;
        ai = pair[1].id;
        av = pair[1].val;

        pu = pair[P].upper;
        pi = pair[P].id;
        pv = pair[P].val;

        if (pair[1].id != biton[0]) {
            pairSize++;
            pair[pairSize].lower = pair[1].lower;
            pair[pairSize].upper = pair[1].upper;
            pair[pairSize].id    = biton[1];
            pair[pairSize].val   = pair[1].val;
         }
        pair[1].upper = pair[P].upper;
        pair[1].id    = biton[0];
        pair[1].val   = cand[pair[1].lower] - cand[pair[1].upper];

        if (pair[P].id != biton[0]) {
            pairSize++;
            pair[pairSize].lower = pair[P].lower;
            pair[pairSize].upper = pair[P].upper;
            pair[pairSize].id    = pair[P].id ^ biton[0];
            pair[pairSize].val   = pair[P].val;
         }
        pair[P].upper = Color;
        pair[P].id    = biton[0];
        pair[P].val   = cand[pair[P].lower];

        equate();

        pair[1].upper = au;
        pair[1].id    = ai;
        pair[1].val   = av;

        pair[P].upper = pu;
        pair[P].id    = pi;
        pair[P].val   = pv;

 }
//---------------------------------------------------------------------------
void    TForm1::equate()
{
 int    i,j,k,l,r;

    // goto skip;

        for (k=1; k<=U; k++) {
            for (i=1; i<=Color; i++) if (pair[k].val == cand[i]) break;
            if (i > Color) {
            //    sprintf(str,"\n**** matching failed %d ****",k);
            //    printPair(str);
                return;
             }
         }
        for (k=1; k<=Color; k++) {
            for (i=1; i<=pairSize; i++) if (pair[i].val == cand[k]) break;
            if (i > pairSize) {
            //    sprintf(str,"\n**** matching failed %d ****",k);
            //    printPair(str);
                return;
             }
         }
     //skip:

        for (i=1; i<=Color; i++)
        for (j=0; j<=S+1; j++)  CS[i][j] = 0;

        for (i=1; i<=Color; i++) {
            for (j=1; j<=pairSize; j++) {
                if (pair[j].lower == i      )  {
                    for (k=0; k<=S; k++) if (pair[j].id & biton[k])  CS[i][k]++;
                 }
                if (pair[j].val   == cand[i]) {
                    for (k=0; k<=S; k++) if (pair[j].id & biton[k])  CS[i][k]--;
                 }
             }
          }
        for (k=1; k<=Color; k++) CS[k][S+1] = CS[k][0];

   //     if (Color!=sColor)  {
   //         printPair("confirm");
   //         printCS("initial");
   //      }

      //check equation
        if (reduction() != 0)    return;

        tc++;
        sprintf(str,"\n*** maybe congratulation !!! tc=%d ****",tc);
        printPair(str);
        printCS("==== Equations ====");

 }
//---------------------------------------------------------------------------
int     TForm1::reduction()
{
 int    i,j,k,w,pvt,TC;

        TC = -1;
        if (tc == TC) {
            sprintf(str,"*** tc=%d  begin  %d %d ***",tc,Color,pairSize);
            printCS(str);
         }
        pvt = 1;
        for (i=1; i<=S; i++) {
            if (CS[pvt][i] == 0) {
                for (k=pvt+1; k<=Color; k++) if (CS[k][i] != 0) break;
                if (k > Color)   continue;
             //swap pvt
                for (j=i; j<=S+1; j++) {
                    w          = CS[pvt][j];
                    CS[pvt][j] = CS[k][j];
                    CS[k][j]   = w;
                 }
             }
            for (j=1; j<=Color; j++) {
                if (j == pvt)        continue;
                if (CS[j][i] == 0)   continue;
                w  = CS[j][i];
                for (k=1; k<=S+1; k++) CS[j][k] = CS[pvt][i]*CS[j][k] - w*CS[pvt][k];
             }
            if (tc == TC) {
                sprintf(str,"*** pvt=%d i=%d ***",pvt,i);
                printCS(str);
             }
            if (pvt++ >= Color)   break;
         }
        if (checkRule() != 0)  return -1;

        return 0;
 }
//---------------------------------------------------------------------------
int     TForm1::checkRule()
{
 int    i,j,k,plus,minus,w;

    //rule 1
        for (i=1; i<=Color; i++) {
            if (CS[i][S+1] > 0)  for (j=1; j<=S+1; j++) CS[i][j] = -CS[i][j];
            plus  = 0;
            minus = 0;
            for (j=1; j<=S; j++) {
                if (CS[i][j] > 0) plus++;
                if (CS[i][j] < 0) minus++;
             }
            if ((plus == 0) && (minus == 0) && (CS[i][S+1] != 0))    return -1;
            if ((plus == 0) && (minus != 0) && (CS[i][S+1] <  0))    return -1;
            if ((plus != 0) && (minus == 0) && (CS[i][S+1] >  0))    return -1;
         }
     //Rule 2
        for (i=1; i<=Color;i++)
        for (j=i+1; j<=Color; j++) {
            minus = 0;
            for (k=1; k<=S+1; k++) {
                w = CS[i][k] + CS[j][k];
                if (w < 0)  minus++;
                if (w > 0)  { minus = -1; break; }
             }
            if ((minus > 0) && (w < 0))   return -1;
         }

        return 0;
 }
//---------------------------------------------------------------------------
void    TForm1::printPair(char id[])
{
 int    k;
        fprintf(fid,"%s\n",id);
        for (k=1; k<=pairSize; k++) {
            fprintf(fid,"*** %2d     (%x,%x)  %d  %d    %d   %x\n",k,
                    pair[k].lower,pair[k].upper,cand[pair[k].lower],cand[pair[k].upper],pair[k].val,pair[k].id);
         }
        fflush(fid);
 }
//---------------------------------------------------------------------------
void    TForm1::printCS(char id[])
{
 int    i,j;
 char   varid[] = { '0','a','b','c','d','e','f','g','h','i','j','k','l','m',
                       'n','o','p','q','r','s','t','u','v','w','x','y','z' };

        fprintf(fid,"%s\n",id);
        for (i=1; i<=S; i++)  fprintf(fid,"  %c",varid[i]);
        fprintf(fid,"\n");
        for (i=1; i<=Color; i++) {
           // fprintf(fid,"  %d   %2d  ",cand[i],CS[i][0]);
            for (j=1; j<=S; j++)  fprintf(fid," %2d",CS[i][j]);
            fprintf(fid,"   %2d\n",CS[i][S+1]);
         }
        fflush(fid);
 }
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClick(TObject *Sender)
{
     main();
}
//---------------------------------------------------------------------------