/*
 *  File:    GetTransversals.cpp
 *  Author:  S Harry White
 *  Created: 2020-10-05
 *  Updated: 2021-05-08
 *    Remove function that found transversals with at most 1 element on each main diagonal.
 *  Updated: 2021-05-12
 *    Allocate tranversal counts store with increase capability.
 *  Updated: 2021-08-06
 *    Change count to unsigned and check for overflow of 32-bit. Also build 64-bit executable.
 *  Updated: 2022-01-04
 *    Replace & with && where necessary.
 * Updated: 2023-01-27
 *   Change outputFile from bufSize to outSize.
 *  Updated: 2023-01-28
 *    Change to compile with g++ for macOS.
 */

/*
 *  Counts transversals of Latin squares:
 *      all transversals, or
 *      diagonal transversals, (having exactly 1 element from each main diagonal)
 */

//#include <ctype.h>
#include <curses.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
//#include <sys/types.h>
#include <time.h>
#include <unistd.h>

typedef unsigned long Uint;

int N, Nd2, M, /* BM, */ A; // (1<<N)-1
const int maxN=32, transStartSize=1000000, maxTrans=INT_MAX/sizeof(int), //trn=100000,
          B[]={ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,
                16384, 32768, 1<<16, 1<<17, 1<<18, 1<<19, 1<<20, 1<<21, 1<<22,
                1<<23, 1<<24, 1<<25, 1<<26, 1<<27, 1<<28, 1<<29, 1<<30, 1<<31 };

int Q[maxN][maxN], R[maxN][maxN], cU[maxN], bU, fU, smallRead, bigRead, lsNumber, transAllocated;
Uint *trans=NULL;

//typedef struct { Uint c[maxN]; } t_tr;
//t_tr tr[maxN][trn];      // transversals
//int  ltr[maxN];          // tr lengths
bool odd, writeError, zeroBase, bell; const bool F=false, T=true;

//int P(const int b) {
////  -
//  if (b<(1<<Nd2)) { for (int i=0; i<Nd2; ++i) if ((1<<i)==b) return i; }
//  else for (int i=Nd2; i<N; ++i) if ((1<<i)==b) return i; return -1;
//} // P

void initGlobals() {
//   -----------
  M=N-1; Nd2=N/2; A=(N==32)?-1:B[N]-1; // BM=B[M];
  odd=N&1; writeError=F; zeroBase=F; lsNumber=0; transAllocated=0;
} // initGlobals
//================================================= store =============================================

const char *storeAllocFail="Storage allocation failed";
bool reportError(const char *s) { printf("%sError: %s.\n", bell?"\a\n":"", s); return bell=F; }
//   -----------

void freeTrans() { if (trans!=NULL) { free(trans); trans=NULL; } }
//   ---------

void freeStore() { freeTrans(); }
//   ---------

bool allocateStore(const int size) {
//   -------------
  bool ok=T;
  if (transAllocated<size) {
	  freeTrans(); trans=(Uint *) malloc(size*sizeof(Uint)); if ((ok=(trans!=NULL))) transAllocated=size;
  }
  return ok;
} // allocateStore

bool increaseTrans() {
//   -------------
  const int size=transAllocated+transStartSize; bool ok=F;
  if (size<=maxTrans) {
    Uint *tmp=(Uint *) malloc(size*sizeof(Uint)); ok=(tmp!=NULL);
    if (ok) {
      for (int i=0; i<lsNumber; i++) tmp[i]=trans[i]; freeTrans(); trans=tmp; transAllocated=size;
    }
  }
  if (!ok) reportError(storeAllocFail); return ok;
} // increaseQueue;
//============================================== input =================================================

void clearLine(int c) { while (c!='\n') c=getchar(); }
//   ---------

int getInt() { int n=0; scanf("%d", &n); clearLine(getchar()); return n; }
//  ------

bool getY() {
//   ----
  int c; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n'));
  clearLine(c); return (c=='Y')|(c=='y');
} // getY

bool getYorOrder(int *n) {
//   -----------
  bool result=F; int c; *n=0; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) result=T;
  else if ( (c!='N')&(c!='n') )
    if ( ('1'<=c)&(c<='9') ) {
      int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; *n=i; result=T;
    }   
  clearLine(c); return result;
} // getYorOrder

bool getFileName(char *buf, const int size) {
//   -----------
  int c, i=0; char *s=buf; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') ); *s=c;
  while (i++<size) if ( (*++s=getchar())=='\n') break;
  if (*s!='\n') { printf("\nFile name too long.\n"); clearLine(*s); return F; }
  *s='\0'; return T;
} // getFileName

const int bufSize=1024;
void adjustName(char *buf) {
//   ----------
  char *s=buf; bool txt=F;
  if ((*s!='.')&(*s!='/')) { // Assume in current folder.
    char tmp[bufSize]; snprintf(tmp, bufSize, "./%s", buf); strcpy(buf, tmp);
  }
  if (access(buf, R_OK)!=0) {
    while (*s++!='\0')
      ; --s;  if ((strlen(buf)>6)&&(*s--=='t')&&(*s--=='x')&&(*s--=='t')&&(*s=='.')) txt=T;
    if (!txt) strcat(buf, ".txt"); // no .txt entered, add it
  }
} // adjustName

FILE *openInput() {
//    ---------
  FILE *rfp=NULL; char buf[bufSize]; printf("File name? ");
  if (getFileName(buf, bufSize-6)) {
    adjustName(buf);
    if ((rfp=fopen(buf, "r"))==NULL) {
      const int msgSize=bufSize+50; char msg[msgSize];
      snprintf(msg, msgSize, "\a\nCan't open for read %s", buf); perror(msg);
    }
  }
  return rfp;
} // openInput

bool errRead() { printf("\nError reading square.\n"); return F; }
//   -------

bool readLS(FILE *rfp) {
//   -------
  int smallest=INT_MAX, biggest=INT_MIN; int c=fgetc(rfp), d; if (c==EOF) return F;
  while ((c==' ')|(c=='\t')|(c=='\r')|(c=='\n')) c=fgetc(rfp);
  if (c=='[') { while ((c!=']')&(c!=EOF)) c=fgetc(rfp); if (c==EOF) return F; c=fgetc(rfp); }
  for (int i=0; i<N; i++) for (int j=0; j<N; j++) {
    bool ceqd=F; while ((c==' ')|(c=='\t')|(c=='\r')|(c=='\n')) c=fgetc(rfp);
    if (c==EOF) { if (c>0) errRead(); return F; }
    if ((c>='a')&(c<='f')) c+=10-'a'; else if ((c>='A')&(c<='F')) c+=10-'A';
    else {
      if ((c<'0')|(c>'9')) return errRead(); c-='0'; d=fgetc(rfp); 
      while (('0'<=d)&(d<='9')) { c=c*10+d-'0'; d=fgetc(rfp); } ceqd=T;
    }
    if (c<smallest) smallest=c; if (c>biggest) biggest=c; Q[i][j]=c; if (ceqd) c=d; else c=fgetc(rfp);
  }
  smallRead=smallest; bigRead=biggest; zeroBase=(smallRead==0); ++lsNumber; return T;
} // readLS
//============================================== output ================================================

const int outSize=bufSize+50; char outputFile[outSize];
FILE *openOutput() {
//    ----------
  FILE *wfp=NULL; int sub=0; const int baseSize=bufSize+25; char baseName[baseSize], buf[outSize];
  snprintf(baseName, baseSize, "./%dTransversals", N); snprintf(buf, outSize, "%s.txt", baseName);
  do {
    if (access(buf, F_OK)!=0) break;
    snprintf(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if ((wfp=fopen(buf, "w"))==NULL) {
    char msg[outSize+50]; snprintf(msg, outSize+50, "\a\nCan't open for write %s", buf); perror(msg); }
  else { printf(".. writing counts to file %s\n", buf); snprintf(outputFile, outSize, "%s", buf); }
  return wfp;
} // openOutput

//bool printLS1(int Q[maxN][maxN], FILE *wfp) {
////   ---------
//  for (int i=0; i<N; i++) {
//    if (Q[i][0]<0) { if (!fprintf(wfp, " .")) return F; }
//    else { if (!fprintf(wfp, "%2d", Q[i][0])) return F; }
//    for (int j=1; j<N; j++)
//      if (Q[i][j]<0) { if (!fprintf(wfp, "  .")) return F; }
//      else { if (!fprintf(wfp, " %2d", Q[i][j])) return F; }
//      if (fputc('\n', wfp)==EOF) return F;
//  }
//  bool ok=fputc('\n', wfp)!=EOF; fflush(wfp); return ok;
//} // printLS1
//
//bool printLS(int Q[maxN][maxN], FILE *wfp) {
////   -------
//  if (N>10) return printLS1(Q, wfp);
//  for (int i=0; i<N; i++) {
//    if (Q[i][0]<0) { if (!fprintf(wfp, ".")) return F; }
//    else { if (!fprintf(wfp, "%d", Q[i][0])) return F; }
//    for (int j=1; j<N; j++)
//      if (Q[i][j]<0) { if (!fprintf(wfp, " .")) return F; }
//      else { if (!fprintf(wfp, " %d", Q[i][j])) return F; }
//      if (fputc('\n', wfp)==EOF) return F;
//  }
//  bool ok=fputc('\n', wfp)!=EOF; fflush(wfp); return ok;
//} // printLS
//=========================================== get transversals ===========================================

bool isLS() { // a Latin square?
//   ----
  if (!(((smallRead==0)&(bigRead==M))|((smallRead==1)&(bigRead==N)))) {
    printf("Error: Numbers must be in the range 0..%d or 1..%d.\n", M, N); return F;
  }
  if (!zeroBase) for(int i=0; i<N; i++) for (int j=0; j<N; j++) --Q[i][j]; zeroBase=T; 
  for (int i=0, b; i<N; i++) { b=0;
	 	for (int j=0, t; j<N; j++) {
      if (b&(t=(1<<Q[i][j])))
        { printf("Error: Duplicate %d in row %d.\n", Q[i][j], i+1); return F; } b|=t;
	  	}
	 }
 	for (int i=0, b; i<N; i++) { b=0;
	  for (int j=0, t; j<N; j++) {
	  	if (b&(t=(1<<Q[j][i])))
        { printf("Error: Duplicate %d in column %d.\n", Q[i][j], i+1); return F; } b|=t;
	  }
 	}
 	return T;
} // isLS

bool isDLS() { // a diagonal Latin square?
//   -----
  if (!isLS()) return F;
  for (int i=0, b=0, t; i<N; i++) {
    if (b&(t=(1<<Q[i][i]))) {
      printf("Error: Duplicate %d in \\diagonal.\n", Q[i][i]); return F; }	b|=t;
  }
  for (int i=0, b=0, t; i<N; i++) {
	  if (b&(t=(1<<Q[i][M-i]))) {
      printf("Error: Duplicate %d in /diagonal.\n", Q[i][M-i]); return F; }	b|=t;
  }
  return T;
} // isDLS

Uint getTransAny() { // All transversals.
//  ------------
  Uint total=0;
  for (int t=0; t<N; ++t) { // search for transversals starting at col t
    int c[maxN], r=1, vU=B[Q[0][t]], cU=B[t]; bool next=T; //ltr[t]=0;
    Uint count=0; c[0]=t; c[1]=(t==0)?1:0;
    do {
      if (next) {
        if (r==M) { int x=A^cU; for (int i=0; i<N; ++i) if ((1<<i)==x) { c[r]=i; break; }
          if (vU&B[Q[r][c[r]]]) { if (r==1) break; --r; next=F;
          } else {
            //if (count==trn) { printf("Transversals overflow.\n");
            //ltr[t]=count; return total; }
            //t_tr *p=&tr[t][count]; for (int i=1; i<N; ++i) p->c[i]=B[c[i]];
            count++; --r; next=F;
          }
        } else {
          
          while ((cU&B[c[r]])|(vU&B[Q[r][c[r]]])) { ++c[r]; if (c[r]==N) break; }
          if (c[r]<N) { cU|=B[c[r]]; vU|=B[Q[r][c[r]]]; ++r; c[r]=0; }
          else { if (r==1) break; --r; next=F; }
        }
      } else { // back
        cU^=B[c[r]]; vU^=B[Q[r][c[r]]]; ++c[r]; if (c[r]==N) { if (r==1) break; --r; } else next=T;
      }
    } while (T);
    Uint prev=total; total+=count;
    if (total<prev) { printf("\aError: unsigned integer overflow.\n"); return ULONG_MAX; }
  }
  //for (int t=0; t<N; ++t) {
  //  for (int i=0; i<ltr[t]; ++i) {
  //    t_tr *p=&tr[t][i]; printf("%d", t);
  //    for (int j=1; j<N; ++j) printf(" %d", P(p->c[j])); putchar('\n');
  //  }
  //}
  return total;
} // getTransAny

Uint getTransDiag() { // Transversals with exactly 1 element from each main diagonal.
//  -------------
  Uint total=0;
  for (int t=0; t<N; ++t) { // search for transversals starting at col t
    int c[maxN], r=1, vU=B[Q[0][t]], cU=B[t]; //ltr[t]=0;
    Uint count=0; bool next=T, b=t==0?T:F, f=t==M?T:F, clrb=T, clrf=T; c[0]=t; c[1]=(t==0)?1:0;
    do {
      if (next) {
        if (r==M) { int x=A^cU; for (int i=0; i<N; ++i) if ((1<<i)==x) { c[r]=i; break; }
          if (vU&B[Q[r][c[r]]]) { if (r==1) break; --r; next=F; clrb=T; clrf=T;
          } else { 
            bool saveb=b, savef=f;
            //if (count==trn) { printf("Transversals overflow.\n");
            //ltr[t]=count; return total; }
            if (c[r]==M) b=!b; if (c[r]==0) f=!f;
            if (b&f) { 
              //t_tr *p=&tr[t][count]; for (int i=1; i<N; ++i) p->c[i]=B[c[i]];
              count++;
            }
            b=saveb; f=savef; --r; next=F; clrb=T; clrf=T;
          }
        } else {  
          while ((cU&B[c[r]])|(vU&B[Q[r][c[r]]])) { ++c[r]; if (c[r]==N) break; }
          if (c[r]<N) {
            cU|=B[c[r]]; vU|=B[Q[r][c[r]]]; if (c[r]==r) { if (b) { next=F; clrb=F; } else b=T; }
            if (c[r]==(M-r)) { if (f) { next=F; clrf=F; } else f=T; } if (next) { ++r; c[r]=0; }
          } else { if (r==1) break; --r; next=F; clrb=T; clrf=T; }
        }
      } else { // back
        if (clrb&(c[r]==r)) b=t==0?T:F; if (clrf&(c[r]==(M-r))) f=t==M?T:F;
        cU^=B[c[r]]; vU^=B[Q[r][c[r]]]; ++c[r]; if (c[r]==N) { if (r==1) break; --r; } else next=T;
      }
    } while (T);
    Uint prev=total; total+=count;
    if (total<prev) { printf("\aError: unsigned integer overflow.\n"); return ULONG_MAX; }
    //ltr[t]=count;
  }
  //for (int t=0; t<N; ++t) {
  //  for (int i=0; i<ltr[t]; ++i) {
  //    t_tr *p=&tr[t][i]; printf("%d", t);
  //    for (int j=1; j<N; ++j) printf(" %d", P(p->c[j])); putchar('\n');
  //  }
  //}
  return total;
} // getTransDiag

bool putTransCount(const int lsNumber, const Uint count) {
//   -------------
  if ((lsNumber>=transAllocated)&&!increaseTrans()) return F; trans[lsNumber]=count; return T;
} // putTransCount
//============================================= main ================================================

const int tall=1, tdiag=2;
bool checkLS(const int kind) { return kind==tdiag?isDLS():isLS(); }
//   -------

//void outputLocalTime() {
////   ---------------
//  time_t startTime=time(NULL); struct tm *local=localtime(&startTime);
//  if (local!=NULL) {
//    char dateTime[100];
//    size_t slen=strftime(dateTime, 100, "%A %Y-%m-%d %X %Z\n\0", local); printf("\n%s", dateTime);
//  }
//} // outputLocalTime

void printElapsedTime(time_t startTime) {
//   ---------------- 
  const int et=(int)difftime(time(NULL), startTime);
  if (et>0) printf("\nelapsed time %d:%02d:%02d\n", et/3600, et%3600/60, et%60);
} // printElapsedTime

int main() {
//  ----
  bool ok=F, inputSize=T; //outputLocalTime();
  //printf("INT_MAX %d ULONG_MAX %lu\n", INT_MAX, ULONG_MAX);
  do {
    if (inputSize) { printf("order? "); N=getInt(); } initGlobals();
    if ((N>0)&(N<=maxN)) {
      if (allocateStore(transStartSize)) {
        printf("Type of transversals, %d all or %d diagonal? ", tall, tdiag); int kind=getInt();
        if (kind<tall) kind=tall; if (kind>tdiag) kind=tdiag; FILE *rfp=openInput();
        if (rfp!=NULL) {
          time_t startTime=time(NULL); Uint maxt=0;
          while (readLS(rfp)) {
            if (checkLS(kind)) {
              Uint count=(kind==tall) ? getTransAny() : getTransDiag();
              if (!putTransCount(lsNumber, count)) { --lsNumber; break; }
              if (count>maxt) maxt=count; if ((lsNumber&0x3ff)==0) printf("%d\n", lsNumber);
            }
          }
          FILE *wfp=openOutput();
          if (wfp!=NULL) {
            for (int i=1; i<=lsNumber; ++i) { 
              fprintf(wfp, "%10d %15lu\n", i, trans[i]);
              if ((i%10)==0) fputc('\n', wfp);
            }
            ok=T; fclose(wfp);
          }
          for (int i=1; i<=lsNumber; ++i) 
            if (trans[i]==maxt) printf("square %d max transversals %lu\n", i, trans[i]); putchar('\n');
          fclose(rfp); printElapsedTime(startTime);
        }
        freeStore();
      }
    } else printf("\aError: order limited to 1..%d\n\n", maxN);
    printf("Continue? input Y or the square order for yes, N for no: ");
    if (getYorOrder(&N)) inputSize=(N==0); else break;
  } while (T);
  printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main