/*
 *  File:    Most-perfectToFranklin.cpp
 *  Author:  S Harry White
 *  Created: 2012-01-23
 *  Updated: 2022-01-12
 *    Tidy code.
 * Updated: 2023-02-21
 *   Improve openInput and openOutput.
 */

#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 int startSize=32;
int N,             // The order of the square.
    Nm1,           // N-1
    Nm2,           // N-2
    Nd2,           // N/2
    Nd2m1,         // N/2-1 
    N3d4,          // 3*N/4
    N3m2d2,        // (3*N-2)/2
    NN,            // N*N
    NNm1,          // NN-1
    NNp1,          // NN+1

    magicConstant, // 1 .. NN
    magicSum,      // 0 .. NN-1 or 1 .. NN
    Sum2,          //           "
    Sum4,          //           "
    **xSquare=NULL, **tSquare=NULL, allocatedSize, squareNum;
const bool F=false, T=true; bool zeroBase, *numberUsed=NULL;

const int bufSize=1024; bool bell=T; char fmt[bufSize];
bool programError(char *s) {
//   ------------
  sprintf_s(fmt, bufSize, "%sProgram error: %s.\nPlease report by e-mail.\n", bell ? "\a" : "", s); 
  printf(fmt, squareNum); return bell=F;
} // programError

void initGlobals() {
//  -----------
  Nm1=N-1; Nm2=N-2; Nd2=N/2; Nd2m1=Nd2-1; N3d4=3*N/4; N3m2d2=(3*N-2)/2;
  NN=N*N; NNm1=NN-1; NNp1=NN+1; magicConstant=Nd2*(NN+1); squareNum=0;
} // initGlobals

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

void assignGlobals() {
//   -------------
  if (zeroBase) { fieldWidth=getWidth(NNm1); magicSum=magicConstant-N; Sum2=NNm1; }
  else { fieldWidth=getWidth(NN); magicSum=magicConstant; Sum2=NNp1; } Sum4=Sum2+Sum2;
} // assignGlobals
//============================================== 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(&xSquare, allocatedSize); freeSquare(&tSquare, 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(&tSquare, size))
      if (ok=allocateSquare(&xSquare, 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 the order
//   ---------
  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

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

bool allNumbersUsed(int **x) {
//   --------------
  for (int i=0; i<=NN; ++i) numberUsed[i]=F;
  for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) {
    const int t=x[r][c]; if ((t >= 0)&(t<=NN)) numberUsed[t]=T;
  }
  for (int i=1; i<NN; ++i) if (!numberUsed[i]) return F;
  if (numberUsed[0]==numberUsed[NN]) return F;return T;
} // allNumbersUsed

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

magicType isNormal(int **x) {
//        --------
  int sumX, sumY, sumXY=0, sumYX=0, chkSum;
  for (int r=0; r<N; ++r) {
    sumX=0; sumY=0; for (int c=0; c<N; ++c) { sumX+=x[r][c]; sumY+=x[c][r]; }
    if (r==0) chkSum=sumX; if ((sumX!=chkSum)|(sumY!=chkSum)) return notMagic;
    sumXY+=x[r][Nm1-r]; sumYX+=x[r][r];
  }
  return basicType[(sumXY==chkSum)&(sumYX==chkSum)][allNumbersUsed(x)&(chkSum==magicSum)];
} // isNormal

bool isCompact(int **x) {
//   ---------
  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])!=Sum4) return F; }
    if ((x[r][Nm1]+x[r][0]+x[r+1][Nm1]+x[r+1][0])!=Sum4) return F;
    if ((x[Nm1][r]+x[0][r]+x[Nm1][r+1]+x[0][r+1])!=Sum4) return F;
  }
  return T;
} // isCompact

bool isComplete(int **x) {
//   ----------
  for (int r=0; r<Nd2m1; ++r) { // no need to check last pair in each diag
    const int i=r+Nd2;
    for (int c=0; c<N; ++c) { int j=c+Nd2; j=j<N ? j : j-N; if ((x[r][c]+x[i][j])!=Sum2) return F; }
  }
  return T;
} // isComplete

bool isPandiagonal(int **x) {
//   -------------
  // Main diagonals already checked in isNormal.
  for (int i=1; i<N; ++i) {
    int sumYX=0, sumXY=0;
    for (int r=0, c=i; r<N; ++r, ++c) {
      const int cModn=c<N ? c : c-N; sumYX+=x[r][cModn]; sumXY+=x[r][Nm1-cModn];
    }
    if ( (sumYX!=magicSum)|(sumXY!=magicSum) ) return F;
  }
  return T;
} // isPandiagonal

bool isMostPerfect(int **x) {
//   ---------------
  return (isNormal(x)==normalMagic)&&isPandiagonal(x)&&isComplete(x)&&isCompact(x);
} // isMostPerfect

bool checkSquare(const int smallest, const int biggest) {
//   -----------
  if ((smallest<0)|(biggest>NN)) {
    printf("\a\nError: Invalid number %d in square %d.\n\n",
            (smallest<0) ? smallest : biggest, squareNum); return F;
  } else {
    if (!isMostPerfect(xSquare)) {
      printf("\a\nError: Square %d is not most-perfect.\n\n", squareNum); return F;
    }
  }
  return T;
} // checkSquare

bool readSquare(FILE *rfp) {
//   ----------
  const int n=N; 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; xSquare[r][c]=tmp;
    } else {
      if ( (rv!=EOF)|(r!=0)|(c!=0) ) printf("\a\nError reading square %d from file.\n", squareNum+1);
      return F;
    }
  }
  ++squareNum; zeroBase=(smallest==0); assignGlobals(); return checkSquare(smallest, biggest);
} // 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, "%sF", inFname); sprintf_s(buf, outSize, "%s.txt", baseName);
  do {
    if (_access_s(buf, 00)==ENOENT) break;
    sprintf_s(buf, outSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if (fopen_s(&wfp, buf, "w")==0) printf("Output file is %s.\n", buf);
  else {
    char mag[outSize+50]; sprintf_s(mag, outSize+50, "\a\nCan't open for write %s", buf); perror(mag);
  }
  return wfp;
} // openOutput

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
//==================================================== make ===================================================

bool isHalfMagic(int **x) {
//   -----------
  const int halfSum=magicSum/2;
  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!=halfSum)|(colH!=halfSum)) return F;
  }
  return T;
} // isHalfMagic

bool isBentDiagonal(int **x) {
//   --------------
  for (int i=Nm1; 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 (sum!=magicSum) return F;
  }
  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 (sum!=magicSum) return F;
  }
  for (int i=Nm1; 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 (sum!=magicSum) return F;
  }
  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 (sum!=magicSum) return F;
  }
  return T;
} // isBentDiagonal

bool isFranklinMagic(int **x) {
//   ---------------
  return (isNormal(x)==normalMagic)&&isHalfMagic(x)&&isBentDiagonal(x)&&isCompact(x);
} // isFranklinMagic

bool checkSquareF(int **x) {
//   ------------
  if (!isFranklinMagic(x)) return programError("Output square %d is not Franklin magic"); return T;
} // checkSquareF

#define xForm(iX, jX) for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) t[iX][jX]=x[i][j]
#define xCopy() for (int i=0; i<N; ++i) for (int j=0; j<N; ++j) x[i][j]=t[i][j]

void swapRowsCols(int **x, const int i, const int j) {
//   ------------
  const int k=Nm1-i, l=Nm1-j; int *tmp; tmp=x[i]; x[i]=x[j]; x[j]=tmp; tmp=x[k]; x[k]=x[l]; x[l]=tmp;
  for (int r=0; r<N; ++r) {
    int tmp; tmp=x[r][i]; x[r][i]=x[r][j]; x[r][j]=tmp; tmp=x[r][k]; x[r][k]=x[r][l]; x[r][l]=tmp;
  }
} // swapRowsCols

void applyTransform(int **x) { for (int i=2, j=Nd2; i<Nd2; i+=4, j+=4) swapRowsCols(x, i, j); }
//   --------------

void putInFrenicleForm(int **x) {
//   -----------------
  bool inFrenicleForm=F; int **t=tSquare,
       minC=min(min(x[0][0], x[0][Nm1]), min(x[Nm1][0], x[Nm1][Nm1]));
  if (x[0][0]==minC) {
    if (x[0][1]<x[1][0]) inFrenicleForm=T; else xForm(j,i); // YX
  } else if (x[0][Nm1]==minC) {
    if (x[1][Nm1]<x[0][Nm2]) xForm(Nm1-j,i); /* -90 */ else xForm(i,Nm1-j); // Y   
  } else if (x[Nm1][Nm1]==minC) {
    if (x[Nm1][Nm2]<x[Nm2][Nm1]) xForm(Nm1-i,Nm1-j); /* 180 */ else xForm(Nm1-j,Nm1-i); // XY
  } else { // x[Nm1][0]==minC
    if (x[Nm2][0]<x[Nm1][1]) xForm(j,Nm1-i); /* 90 */ else xForm(Nm1-i,j); // X
  }
  if (!inFrenicleForm) xCopy();
} // putInFrenicleForm

bool getFranklin(FILE *wfp) {
//   -----------
  int **x=xSquare; bool good=F, write=F; applyTransform(x); putInFrenicleForm(x);  
  good=checkSquareF(x); write=writeSquare(wfp, x); return good&write;
} // getFranklin
//================================================== main ==================================================

bool checkN() {
//   ------
   if ((N<=0)|(N%8!=0)) {
    printf("\aERROR: Order %d is not a positive integral multiple of 8.\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

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 doAnother(const bool getError, bool *inputSize) {
//   ---------
  if (!getError) {
    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, getError=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);
        if (rfp!=NULL) {
          time_t startTime=time(NULL); stripName(ibuf, obuf); FILE *wfp=openOutput(obuf);
          if (wfp!=NULL) {
            squareNum=0; bell=T; while (readSquare(rfp)) { if (getError=!getFranklin(wfp)) break; }
            if (!getError) ok=T; fclose(wfp); 
          } // if (wfp!=NULL)       
          reportElapsedTime(startTime); fclose(rfp);
        } // (rfp!=NULL)
      } // (allocateStore())
    } // (checkN
    another=doAnother(getError, &inputSize);
  } while (another);
  printf("\nPress a key to close the console.");
  while (!_kbhit()) Sleep(250); return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main