/*
 *  File:    Hurkens.cpp
 *  Author:  S Harry White
 *  Created: 2013-11-18
 *  Updated: 2022-01-07
 *    Tidy code.
 * Updated: 2023-02-20
 *   Improve openInput and openOutput.
 */

/*
 *  Transforms Franklin squares to a standard format.
 *  See: Hurkens, C.A.J. "Plenty of Franklin Magic Squares, but none of order 12"
 *    http://www.win.tue.nl/bs/spor/2007-06.pdf
 */

#include "stdafx.h"
#include <conio.h>
#include <direct.h>
#include <errno.h>
#include <io.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <Windows.h>

const bool F=false, T=true;
bool zeroBase, *numberUsed=NULL, firstSquareOneBased; // write all squares in same base as the first

const int startSize=32;
int N,                      // The order of the square.
    Nm1,                    // N-1
    Nm2,                    // N-2
    Nd2,                    // N/2
    Nd2m1,                  // N/2-1
    Nd2m2,                  // N/2-2
    Nd2p1,                  // N/2+1
    NN,                     // N*N
    NNm1,                   // NN-1
    **iSquare=NULL, **oSquare=NULL, allocatedSize, squareNum;

typedef unsigned int Uint;
Uint magicConstant,
     halfMagicConstant; // 1 base,
                        // (halfMagicConstant valid only for N doubly even).
Uint magicSum,
     halfMagicSum,      // Use for 0 or 1 base,
                        // (halfMagicSum valid only for N doubly even).
     Sum2, Sum4;

enum magicType { notMagic, normalSemiMagic, otherSemiMagic, normalMagic, otherMagic };
magicType squareType;
//================================================ store ================================================

void freeSquare(int*** square, const int allocated) {
//   ----------
  if (*square!=NULL) { for(int i=0; i<allocated; i++) free((*square)[i]); free(*square); *square=NULL; }
} // freeSquare

void freeUsed() { if (numberUsed!=NULL) {	free(numberUsed); numberUsed=NULL; }}
//   --------

void freeStore() {
//   --------- 
  freeSquare(&iSquare, allocatedSize); freeSquare(&oSquare, allocatedSize); freeUsed(); allocatedSize=0;
} // freeStore

bool allocateSquare(int*** square, const int size) {
//   --------------
  bool ok; *square=(int**) malloc(size*sizeof(int*)); ok=(*square!=NULL);
  if (ok) {
    int numAllocated=size;
    for(int i=0; i<size; i++) {
      int* p=(int*) malloc(size*sizeof(int));
      (*square)[i]=p; if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeSquare(square, numAllocated);
  }
  return ok;
} // allocateSquare 

bool allocateUsed(const int size) { return ((numberUsed=(bool*) malloc(size*sizeof(bool)))!=NULL); }
//   ------------

bool allocateStore(int size) {
//   -------------
  bool ok=T; if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeStore();
    if (ok=allocateSquare(&oSquare, size))
      if (ok=allocateSquare(&iSquare, size))
        if (ok=allocateUsed(size*size+1)) allocatedSize=size;
     if (!ok) freeStore();
  }
  return ok;
} //allocateStore
//=============================================== input =================================================

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

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

bool getYorInt(int *n) { // Yes or No or integer
//   ---------
  bool result=F; int c; *n=-1; do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) result=T;
  else if ( (c!='N')&(c!='n') )
    if ( ('0'<=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;
} // getYorInt

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

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 check_txt(char *buf) {
//   ---------
  char *s=buf; bool txt=F; while (*s++!='\0');
  while (--s!=buf) if (*s=='.') { txt=(*++s=='t')&&(*++s=='x')&&(*++s=='t')&&(*++s=='\0'); break; }
  if (!txt) strcat_s(buf, bufSize, ".txt");
} // check_txt

FILE *openInput(char buf[bufSize]) {
//    ---------
  char *rFname=NULL; FILE *rfp=NULL;
  do {
    printf("\nEnter the name of the squares file: ");
    if (getFileName(buf, bufSize-4)) { rFname=buf; break; }
    printf("\a\nCan't read the file name. Try again? y (yes) or n (no) "); if (!getY()) break;
  } while (T);
  if (rFname!=NULL) {
    check_txt(buf); 
    if (fopen_s(&rfp, buf, "r")!=0) {
      const int msgSize=bufSize+50; char msg[msgSize];
      sprintf_s(msg, msgSize, "\a\nCan't open for read %s", buf); perror(msg);
    }
  }
  return rfp;
} // openInput

const magicType basicType[2][2]= { {otherSemiMagic, normalSemiMagic}, {otherMagic, normalMagic} };

magicType isMagic(int **x) {
//        -------
  int sumX, sumY, sumXY=0, sumYX=0, chkSum=0, n=N, nm1=Nm1;
  for (int i=0; i<n; i++) {
    sumX=0; sumY=0;
    for (int j=0; j<n; j++) { sumX+=x[i][j]; sumY+=x[j][i]; } if (i==0) chkSum=sumX;
    if ((sumX!=chkSum)|(sumY!=chkSum)) return notMagic; sumXY+=x[i][nm1-i]; sumYX+=x[i][i];
  }
  return basicType[(sumXY==chkSum)&(sumYX==chkSum)][F];
} // isMagic

magicType isNormal(int **x) {
//        --------
  const int min=zeroBase ? 0 : 1, max=NN+min-1, n=N, nm1=Nm1; Uint sumX, sumY, sumXY=0, sumYX=0, chkSum;
  for (int i=min; i<=max; i++) numberUsed[i]=F;
  for (int i=0; i<n; i++) {
    sumX=0; sumY=0;
    for (int j=0; j<n; j++) { const int tmp=x[i][j]; numberUsed[tmp]=T; sumX+=tmp; sumY+=x[j][i]; }
    if (i==0) chkSum=sumX; if ((sumX!=chkSum)|(sumY!=chkSum)) return notMagic; sumXY+=x[i][nm1-i]; sumYX+=x[i][i];
  }
  bool allNumbersUsed=T; for (int i=min; i<=max; i++) if (!numberUsed[i]) { allNumbersUsed=F; break; }
  return basicType[(sumXY==chkSum)&(sumYX==chkSum)][allNumbersUsed&(chkSum==magicSum)];
} // isNormal

void baseZero(int **x, const int n) { for (int r=0; r<n; r++) for (int c=0; c<n; c++) --x[r][c]; zeroBase=T; }
//   --------

void baseOne(int **x, const int n) { for (int r=0; r<n; r++) for (int c=0; c<n; c++) ++x[r][c]; }
//   -------

bool readError;
bool readSquare(FILE *rfp) {
//   ----------
  const int n=N, nd2=Nd2, nn=NN, nnm1=NNm1; int smallest=LONG_MAX, biggest=LONG_MIN;
  for (int r=0; r<n; r++) {
    for (int c=0; c<n; c++) {
	    int tmp, rv;
      if ( (rv=fscanf_s(rfp, "%d", &tmp))==1) {
        if (tmp<smallest) smallest=tmp; if (tmp>biggest) biggest=tmp; iSquare[r][c]=tmp;
      } else {
        if ( (rv!=EOF)|(r!=0)|(c!=0) ) { readError=T; printf("\a\nError reading square from file.\n"); }
        return F;
      }
    }
  }
  zeroBase=smallest==0; if (++squareNum==1) firstSquareOneBased=!zeroBase;
  if (!zeroBase) baseZero(iSquare, n); magicSum=magicConstant-n;
  halfMagicSum=halfMagicConstant-nd2; Sum2=nnm1; Sum4=Sum2+Sum2;
  if ( (smallest<0)|(biggest>nn) ) squareType=isMagic(iSquare); else squareType=isNormal(iSquare); return T;
} // readSquare
//================================================== output =================================================

const int outSize=bufSize+50;
void stripName(char *inFname, char *obuf) {
//   ---------
  char *s=inFname; while (*s++!='\0');
  while (--s!=inFname) // Remove .txt and any directory path.
    if (*s=='.') *s='\0';  else if ((*s=='\\')|(*s=='/')) { ++s; break; }
  strcpy_s(obuf, outSize, s); 
} // stripName

FILE *openOutput(char *inFname) {
//    ----------
  const int baseSize=bufSize+25; char baseName[baseSize], buf[outSize]; FILE *wfp=NULL; int sub=0;
  sprintf_s(baseName, baseSize, "%sHurkens", inFname); sprintf_s(buf, outSize, "%s.txt", baseName);
  do {
    if (_access_s(buf, 00)==ENOENT) break; else sprintf_s(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if (fopen_s(&wfp, buf, "w")!=0) {
    char msg[outSize+50];
    sprintf_s(msg, outSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  }
  return wfp;
} // openOutput

int fieldWidth;
int getWidth(int number) { int width=1, i=number; while ((i=i/10)!=0) ++width; return width; }
//  --------

typedef bool (*t_fprintFW)(FILE *fp, const int i);

bool fprintFW1(FILE *fp, const int i) { return fprintf(fp, "%1d",  i)>0; }
bool fprintFW2(FILE *fp, const int i) { return fprintf(fp, "%2d",  i)>0; }
bool fprintFW3(FILE *fp, const int i) { return fprintf(fp, "%3d",  i)>0; }
bool fprintFW4(FILE *fp, const int i) { return fprintf(fp, "%4d",  i)>0; }
bool fprintFW5(FILE *fp, const int i) { return fprintf(fp, "%5d",  i)>0; }
bool fprintFW6(FILE *fp, const int i) { return fprintf(fp, "%6d",  i)>0; }
bool fprintFW7(FILE *fp, const int i) { return fprintf(fp, "%7d",  i)>0; }
bool fprintFW8(FILE *fp, const int i) { return fprintf(fp, "%8d",  i)>0; }
bool fprintFW9(FILE *fp, const int i) { return fprintf(fp, "%9d",  i)>0; }
bool fprintFWa(FILE *fp, const int i) { return fprintf(fp, "%10d", i)>0; }

static t_fprintFW fprintFW[]={ NULL,
  fprintFW1, fprintFW2, fprintFW3, fprintFW4, fprintFW5,
  fprintFW6, fprintFW7, fprintFW8, fprintFW9, fprintFWa
};
const int maxFieldWidth=10;

bool writeSquare(FILE *wfp, int **x) {
//   -----------
  const int n=N, fw0=fieldWidth, fw=fw0+1; if (fw>maxFieldWidth) return F;
  for (int r=0; r<n; r++) {
    if (!fprintFW[fw0](wfp, x[r][0])) return F;
    for (int c=1; c<n; c++)    if (!fprintFW[fw](wfp, x[r][c])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // writeSquare
//================================================ xForm ====================================================

bool isBentDiagonal(int **x) {
//   --------------
  const int n=N, nm1=Nm1, nd2=Nd2, nd2p1=Nd2p1; int waysBent=0;
  bool odd=(n&1)==1, bentL=T, bentR=T, bentU=T, bentD=T;

  for (int i=n-1; i>=0; --i) { // bent left ?
    int sum=0;
    for (int r=0, c=i; r<nd2; ++r, --c) { const int cModn=c<0 ? c+n : c; sum+=x[r][cModn]+x[nm1-r][cModn]; }
    if (odd) { int j=i+nd2p1; j=j<n ? j : j-n; sum+=x[nd2][j]; } if (sum!=magicSum) { bentL=F; break; }
  }
  if (bentL) ++waysBent;

  for (int i=0; i<n; ++i) {  // bent right ?
    int sum=0;
    for (int r=0, c=i; r<nd2; ++r, ++c) { const int cModn=c<n ? c : c-n; sum+=x[r][cModn]+x[nm1-r][cModn]; }
    if (odd) { int j=i+nd2; j=j<n ? j : j-n; sum+=x[nd2][j]; } if (sum!=magicSum) { bentR=F; break; }
  }
  if (bentR) ++waysBent;

  for (int i=n-1; i>=0; --i) { // bent up ?
    int sum=0;
    for (int c=0, r=i; c<nd2; ++c, --r) { const int rModn=r<0 ? r+n : r; sum+=x[rModn][c]+x[rModn][nm1-c]; }
    if (odd) { int j=i+nd2p1; j=j<n ? j : j-n; sum+=x[j][nd2]; } if (sum!=magicSum) { bentU=F; break; }
  }
  if (bentU) ++waysBent;

  for (int i=0; i<n; ++i) { // bent down ?
    int sum=0;
    for (int c=0, r=i; c<nd2; ++c, ++r) { const int rModn=r<n ? r : r-n; sum+=x[rModn][c]+x[rModn][nm1-c]; }
    if (odd) { int j=i+nd2; j=j<n ? j : j-n; sum+=x[j][nd2]; } if (sum!=magicSum) { bentD=F; break; }
  }
  if (bentD) ++waysBent; return waysBent==4;
} // isBentDiagonal

bool isCompact(int **x) {
//   ---------
  if ((N&3)!=0) return F; /* only doubly even */ const int n=N, nm1=Nm1, nn=NN, S4=Sum4;
  for (int r=0; r<nm1; ++r) {
    for (int c=0; c<nm1; ++c) { if ((x[r][c]+x[r][c+1]+x[r+1][c]+x[r+1][c+1])!=S4) return F; }
    if ((x[r][nm1]+x[r][0]+x[r+1][nm1]+x[r+1][0])!=S4) return F;
    if ((x[nm1][r]+x[0][r]+x[nm1][r+1]+x[0][r+1])!=S4) return F;
  }
  return T;
} // isCompact

bool isFranklin(int **x) {
//   ----------
  if ((squareType==normalMagic)|(squareType==normalSemiMagic)) {
    if (isCompact(x)&&isBentDiagonal(x)) {
      const int n=N, nd2=Nd2; 
      for (int i=0; i<n; ++i) {
        int rowH=0, colH=0; for (int j=0; j<nd2; ++j) { rowH+=x[i][j]; colH+=x[j][i]; }
        if ((rowH!=halfMagicSum)|(colH!=halfMagicSum)) return F;
      }
      return T;
    }
  }
  return F;
} // isFranklin

bool checkSquare(int **x) {
//   -----------
  if (!isFranklin(x)) { printf("\nSquare number %d is not Franklin.\n", squareNum); return F; } return T;
} // checkInSquare

typedef void (*t_Rotate)(const int, const int, const int);
void rotate_Y  (const int n, const int i, const int j) { oSquare[i][n-j]=iSquare[i][j]; };
void rotate_X  (const int n, const int i, const int j) { oSquare[n-i][j]=iSquare[i][j]; };
void rotate_YX (const int n, const int i, const int j) { oSquare[j][i]=iSquare[i][j]; };
static t_Rotate rotateCell[]={
  rotate_Y, // about vertical axis,   (mirror)
  rotate_X, // about horizontal axis, (mirror+rotate_180)
  rotate_YX // about back diagonal,   (mirror+rotate_270)
};

void rotateSquare(t_Rotate rotate) {
//   ------------
  const int n=N, nm1=Nm1;
  for (int r=0; r<n; ++r) for (int c=0; c<n; ++c) rotate(nm1, r, c);
  for (int r=0; r<n; ++r) for (int c=0; c<n; ++c) iSquare[r][c]=oSquare[r][c];
} //rotateSquare

void swapRows(int **x, const int a, const int b) { if (a!=b) { int *tmp=x[a]; x[a]=x[b]; x[b]=tmp; }}
//   --------

void swapCols(int **x, const int a, const int b) {
//   --------
  if (a!=b) { for (int r=0; r<N; ++r) { const int tmp=x[r][a]; x[r][a]=x[r][b]; x[r][b]=tmp; }}
} // swapCols

void swapSideRows(int **x, int a) {
//   ------------
  const int n=N; int b=Nd2+a, loop=N/4; while(loop--) { int *tmp=x[a]; x[a]=x[b]; x[b]=tmp; a+=2; b+=2; }
} // swapSideRows

void swapSideCols(int **x, int a) {
//   ------------
  const int n=N; int b=Nd2+a, loop=N/4;
  while(loop--) {
    for (int r=0; r<n; ++r) { const int tmp=x[r][a]; x[r][a]=x[r][b]; x[r][b]=tmp; } a+=2; b+=2;
  }
} // swapSideCols

void locateZero(int **x, int *row, int *col) {
//   ----------
  const int n=N; bool found=F;
  for (int r=0; r<n; ++r) { for (int c=0; c<n; ++c) {
    if (x[r][c]==0) { *row=r; *col=c; found=T; break; }} if (found) break;
  }
} // locateZero

void move0ToRow0(int **x, int zeroRow) {
//   -----------
  const int nd2=Nd2;
  if (zeroRow&1) {
    const int n=N; if (zeroRow<nd2) { swapSideRows(x, 1); zeroRow+=nd2; }
    swapRows(x, zeroRow, n-1); rotateSquare(rotate_X);
  } else {
    if (zeroRow>=nd2) { swapSideRows(x, 0); zeroRow-=nd2; } swapRows(x, zeroRow, 0);
  }
} // move0ToRow0

void move0ToCol0(int **x, int zeroCol) {
//   -----------
  const int nd2=Nd2;
  if (zeroCol&1) {
    const int n=N; if (zeroCol<nd2) { swapSideCols(x, 1); zeroCol+=nd2; }
    swapCols(x, zeroCol, n-1); rotateSquare(rotate_Y);
  } else {
    if (zeroCol>=nd2) { swapSideCols(x, 0); zeroCol-=nd2; } swapCols(x, zeroCol, 0);
  }
} // move0ToCol0

void alignRows(int **x, const int first, const int last) {
//   ---------
  for (int r=first; r<last; r+=2) {
    int minv=MAXINT, minr=MAXINT;
    for (int i=r; i<=last; i+=2) { if (x[i][0]<minv) { minv=x[i][0]; minr=i; }} swapRows(x, r, minr);
  }
} // alignRows

void alignCols(int **x, const int first, const int last) {
//   ---------
  for (int c=first; c<last; c+=2) {
    int minv=MAXINT, minc=MAXINT;
    for (int i=c; i<=last; i+=2) { if (x[0][i]<minv) { minv=x[0][i]; minc=i; }} swapCols(x, c, minc);
  }
} // alignCols

void complementAlternateCells(int **x) {
//   ------------------------
  for (int r=0; r<N; r+=2) for (int c=1; c<N; c+=2) { x[r][c]=Sum2-x[r][c]; x[r+1][c-1]=Sum2-x[r+1][c-1]; }
} // complementAlternateCells

void xformSquare(int **x) {
//   -----------
  const int n=N, nm1=Nm1, nm2=Nm2, nd2=Nd2, nd2p1=Nd2p1, nd2m1=Nd2m1, nd2m2=Nd2m2; int zeroRow=0, zeroCol=0;
  locateZero(x, &zeroRow, &zeroCol); move0ToRow0(x, zeroRow); move0ToCol0(x, zeroCol);
  alignRows(x, 0, nd2m2); alignRows(x, nd2, nm2); alignCols(x, 0, nd2m2); alignCols(x, nd2, nm2);
  complementAlternateCells(x);
  alignRows(x, 1, nd2m1); alignRows(x, nd2p1, nm1); alignCols(x, 1, nd2m1); alignCols(x, nd2p1, nm1);
  if (x[1][0]>x[nd2p1][0]) swapSideRows(x, 1); if (x[0][1]>x[0][nd2p1]) swapSideCols(x, 1);
  if (max(x[0][nd2m2], x[0][nm2])>max(x[nd2m2][0], x[nm2][0])) rotateSquare(rotate_YX);
  complementAlternateCells(x); /* restore */ if (firstSquareOneBased) baseOne(x, n);
}  // xformSquare

bool xformWrite(FILE *wfp) {
//   ----------
  if (checkSquare(iSquare)) {
    xformSquare(iSquare);
    if (!writeSquare(wfp, iSquare)) { perror("\a\nError writing file"); return F; }
    if ((squareNum & 0x7fff)==0) printf("... %d\n", squareNum);
  }
  return T;
} // xformWrite
//=================================================== main ===============================================

void initGlobals() {
//  -----------
  Nm1=N-1; Nm2=Nm1-1; Nd2=N/2; Nd2m1=Nd2-1; Nd2m2=Nd2m1-1; Nd2p1=Nd2+1; NN=N*N; NNm1=NN-1;
  halfMagicConstant=(NN+1)*(N/4); magicConstant=halfMagicConstant+halfMagicConstant;
  fieldWidth=getWidth(NNm1); squareNum=0;
} // initGlobals

void reportElapsedTime(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);
} // reportElapsedTime

bool checkN() {
//   ------
  if ((N<=0)|((N&3)!=0)) { printf("\aOrder %d is not a positive doubly even order.\n\n", N); return F; }
  return T;
} // checkN

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

bool doAnother(bool writeError, bool *inputSize) {
//   ---------
  if (!writeError) {
    printf("\nContinue? input y (yes) or n (no) or the order of the squares: ");
    if (getYorInt(&N)) { *inputSize=(N<0); return T; }
  }
  freeStore(); return F;
} // doAnother

int main() {
//  ----
  outputLocalTime();
  bool another=T, inputSize=T, writeError=F, ok=F;
  do { // for each input file
    if (inputSize)
      { printf("\nInput the order of the squares: "); N=getInt(); }
    if (checkN()) {
      initGlobals();
      if (allocateStore(N)) {
        char ibuf[bufSize], obuf[bufSize];
        FILE *rfp=openInput(ibuf); time_t startTime=time(NULL);
        if (rfp!=NULL) {
          stripName(ibuf, obuf); FILE *wfp=openOutput(obuf); 
          if (wfp!=NULL) {
            squareNum=0;
            while (readSquare(rfp)) { if (writeError=!xformWrite(wfp)) break; }
            if (!writeError) ok=T; printf("Number of squares: %d\n", squareNum); fclose(wfp);
          } // (wfp!=NULL) 
          fclose(rfp);
        } // (rfp!=NULL)
        reportElapsedTime(startTime);
      } // (allocateStore())
    } // (checkN
    another=doAnother(writeError, &inputSize);
  } while (another);

  printf("\nPress a key to close the console.");
  while (!_kbhit()) Sleep(250); return ok ? EXIT_SUCCESS : EXIT_FAILURE;
  return 0;
} // main