/*
 *  File:    BorderedSquare.cpp
 *  Author:  S Harry White
 *  Created: 2013-07-26
 *  Updated: 2021-12-14
 *    Tidy code.
 */

/*
 *  Makes bordered magic squares of order n.
 */

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

const bool F=false, T=true; const int startSize=25, bufSize=1024;
int **xSquare=NULL, allocatedSize, biggestValue;

void reportError(char *what) { printf("\a\nERROR!!! Square is NOT %s! Please report by email\n", what); }
//   -----------
//================================================= store ================================================

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

void freeSquares() { freeSquare(&xSquare, allocatedSize); allocatedSize=0; }
//   -----------

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 allocateSquares(int size) {
//   ---------------
  bool ok=T; if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeSquare(&xSquare, allocatedSize);
    if (ok=allocateSquare(&xSquare, size)) allocatedSize=size; else allocatedSize=0;
  }
  return ok;
} // allocateSquares
//============================================== 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 getYorOrder(int *n) { // 'y' or 'n' or the order
//   -----------
  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;
}

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

int fieldWidth(int n) { if (n==1) return 1; int i=n*n, w=1; while ((i=i/10)!=0) ++w; return w; }
//  ----------

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 printSquare(FILE *wfp, const int n) {
//   -----------
  const int fw0=fieldWidth(n), fw=fw0+1; if (fw>maxFieldWidth) return F;
  for (int i=0; i<n; i++) {
    if (!fprintFW[fw0](wfp, xSquare[i][0])) return F;
    for (int j=1; j<n; j++) if (!fprintFW[fw](wfp, xSquare[i][j])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // printSquare

bool openDir() {
//   -------
  char buf[bufSize], msg[bufSize]; int sub=0;
  const char *baseName="BorderedSquare"; strcpy_s(buf, bufSize, baseName);
  do {
    if (_mkdir(buf)==0) break;
    if (errno!=EEXIST) { sprintf_s(msg, bufSize, "Can't make folder %s", buf); perror(msg); return F; }
    sprintf_s(buf, bufSize, "%s_%d", baseName, ++sub);
  } while (T);
  if ( _chdir(buf)!=0) { sprintf_s(msg, bufSize, "Can't open folder %s", buf); perror(msg); return F; }
  printf("Output files are in folder %s\n\n", buf); return T;
} // openDir

FILE *open_File(const int n) {
//    ---------
  char buf[bufSize]; FILE *wfp=NULL; sprintf_s(buf, bufSize, "Order%d.txt", n);
  if (fopen_s(&wfp, buf, "a")!=0) {
    char msg[bufSize]; sprintf_s(msg, bufSize, "\a\nCan't open for write %s", buf); perror(msg);
  }
  return wfp; 
} // open_File
//================================================ check =================================================

bool isContiguous(int **x, const int n, const int m, int *first) {
//   ------------
  const int low=*first, high=low+m+m-3, o=(n-m)/2, l=o+m-1; int lo=LONG_MAX, hi=LONG_MIN, tmp=0;

  // Corners
  tmp=min(x[o][o], x[l][l]); if (tmp<lo) lo=tmp; if (tmp>hi) hi=tmp;
  tmp=min(x[o][l], x[l][o]); if (tmp<lo) lo=tmp; if (tmp>hi) hi=tmp;

  // Top, bottom
  for (int c=o+1; c<l; ++c) { tmp=min(x[o][c], x[l][c]); if (tmp<lo) lo=tmp; if (tmp>hi) hi=tmp; }

  // Left, right
  for (int r=o+1; r<l; ++r) { tmp=min(x[r][o], x[r][l]); if (tmp<lo) lo=tmp; if (tmp>hi) hi=tmp; }
  if ((lo!=low)|(hi!=high) ) return F; *first=hi+1; return T;
} // isContiguous

bool isBordered(int **x, const int n) {
//   ----------
  int first=1; const int end=((n&1)==1) ? 3 : 6;
  for (int m=n; m>=end; m-=2) if (!isContiguous(x, n, m, &first)) return F; return T;
} // isBordered

bool isConcentric(int **x, const int n, const int m, const int S2) {
//   ------------
  const int o=(n-m)/2, l=o+m-1; 
  if ((x[o][o]+x[l][l])!=S2) return F; if ((x[o][l]+x[l][o])!=S2) return F; // Corners
  for (int c=o+1; c<l; ++c) if ((x[o][c]+x[l][c])!=S2) return F; // Top, bottomt
  for (int r=o+1; r<l; ++r) if ((x[r][o]+x[r][l])!=S2) return F; // Left, right
  return T;
} // isConcentric

bool checkBordered(int **x, const int n) {
//   -------------
  if (n>4) {
    bool bordered=T; const int S2=n*n+1, start=((n&1)==1) ? 5 : 6;
    for (int m=start; m<=n; m+=2) if (!isConcentric(x, n, m, S2)) { bordered=F; break; }
    if (bordered) bordered=isBordered(x, n);
    if (!bordered) { reportError("bordered"); return F; }
  }
  return T;
} // checkBorderedrn;

void checkDry(int **x, const int n) {
//   --------
  const int m=n-1;
  for (int r=1; r<m; r++) for (int c=1; c<m; c++) {
    const int v=x[r][c];
    if (!((x[r-1][c]<v)||(x[r+1][c]<v)||(x[r][c-1]<v)||(x[r][c+1]<v))) {
      reportError("zero retention"); return;
    }
  }
} // checkDry

void checkCorrect(int **x, const int n) {
//   ------------
  const int nn=n*n, nnp1=nn+1, big=n%2==0 ? nn/2 : (nn-1)/2; bool magic=T;
  if (biggestValue==big) {
    const int chkSum=n%2==0 ? n/2*nnp1 : n*(nnp1/2); int sumX, sumY, sumXY=0, sumYX=0;
    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 ((sumX!=chkSum)|(sumY!=chkSum)) { magic=F; break; } sumXY+=x[i][n-i-1]; sumYX+=x[i][i];
    }
    if (magic) magic=(sumXY==chkSum)&(sumYX==chkSum);
  } else magic=F;

  if (magic) { if (checkBordered(x, n)) checkDry(x, n);
  } else reportError("magic");
} // checkCorrect
//================================================ make =================================================

void makeActual(int **x, const int n) {
//   ----------
  const int nn=n*n;
  
  if ((n%2)==0) {
    const int pPlus=nn/2, mPlus=pPlus+1;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) x[i][j]+=x[i][j]>0 ? pPlus : mPlus;
  } else {
    const int midc=(nn+1)/2; for (int i=0; i<n; i++) for (int j=0; j<n; j++) x[i][j]+=midc;
  }
} // makeActual

bool makeEven(int **x, const int size, FILE *wfp) {
//   --------
  int j, o=(size-4)/2, k=o+1, n=o+3, m=o+2, v=1; // 0.5;

  // fill center 4x4
  x[m][k]=-v; x[m][m]=v++; x[n][m]=-v; x[n][k]=v++; x[n][n]=-v; x[n][o]=v++; x[m][o]=-v; x[m][n]=v++;
  x[o][m]=-v; x[o][k]=v++; x[k][k]=-v; x[k][m]=v++; x[k][o]=-v; x[k][n]=v++; x[o][n]=-v; x[o][o]=v++;
   
  for (int i=6; i<=size; i+=2) {
    o=(size-i)/2; n=o+i-1; k=(o+n-1)/2; m=k+1; int tm=m-1, tp=o+1, lm=o+1, lp=m;
    if (i % 4!=0) { //------------------------------   // singly even     
      j=(k-o+1)/2; while (j--) { x[o][tm]=-v; x[n][tm++]=v++; x[n][tp]=-v; x[o][tp++]=v++; }
        x[o][tm]=-v; x[n][tm++]=v++; x[lm][o]=-v; x[lm++][n]=v++; 
      j=(k-o-1)/2; while (j--) { x[lp][n]=-v; x[lp++][o]=v++; x[lm][o]=-v; x[lm++][n]=v++; }
        x[n][n]=-v; x[o][o]=v++; /* NW */ x[n][o]=-v; x[o][n]=v++; /* NE */ x[lp][n]=-v; x[lp++][o]=v++;
      j=(n-m-1)/2; while (j--) { x[lm][o]=-v; x[lm++][n]=v++; x[lp][n]=-v; x[lp++][o]=v++; }
        x[lp][n]=-v; x[lp++][o]=v++; x[o][tm]=-v; x[n][tm++]=v++;
      j=(n-m-1)/2; while (j--) { x[n][tp]=-v; x[o][tp++]=v++; x[o][tm]=-v; x[n][tm++]=v++; }
        x[lm][o]=-v; x[lm][n]=v++;
    } else { //---------------------------------------   // doubly even
        x[o][tm]=-v; x[n][tm++]=v++;
      j=(k-o)/2; while (j--) { x[n][tp]=-v; x[o][tp++]=v++; x[o][tm]=-v; x[n][tm++]=v++; }
      if (i==8) { x[lp][n]=-v; x[lp++][o]=v++; }
      else { x[lm][o]=-v; x[lm++][n]=v++; x[lp][n]=-v; x[lp++][o]=v++;
        j=(k-o-5)/2; while (j--) { x[lm][o]=-v; x[lm++][n]=v++; x[lp][n]=-v; x[lp++][o]=v++; }
        x[lp][n]=-v; x[lp++][o]=v++;
      } 
        x[lm][o]=-v; x[lm++][n]=v++; x[lm][o]=-v; x[lm++][n]=v++;
        x[n][n] =-v; x[o][o]=v++; /* NW */ x[n][o]=-v; x[o][n]=v++; /* NE */
        x[lp][n]=-v; x[lp++][o]=v++; x[lp][n]=-v; x[lp++][o]=v++;
      j=(n-m-2)/2; while (j--) { x[lm][o]=-v; x[lm++][n]=v++; x[lp][n]=-v; x[lp++][o]=v++; }
        x[k][o]=-v; x[k][n]=v++;
      j=(n-m)/2; while (j--) { x[o][tm]=-v; x[n][tm++]=v++; x[n][tp]=-v; x[o][tp++]=v++; }
        x[o][tm]=-v; x[n][tm]=v++;
    }
  }
  biggestValue=v-1; makeActual(xSquare, size); return printSquare(wfp, size);
}  // makeEven

bool makeOdd(int **x, const int size, FILE *wfp) {
//   -------
  int j, o, n, m=(size-1)/2, v=1; x[m][m]=0;

  for (int i=3; i<=size; i+=2) {
    o=(size-i)/2; n=o+i-1; m=(o+n)/2;

    for (j=o+1; j<m; j++) { x[n][j]=-v; x[o][j]=v++; /* NNW */ x[j][o]=-v; x[j][n]=v++; /* ENE */ }
    x[n][o]=-v; x[o][n]=v++; /* NE */ x[m][o]=-v; x[m][n]=v++; /* E */
    x[n][n]=-v; x[o][o]=v++; /* NW */ x[o][m]=-v; x[n][m]=v++; /* S */
    for (j=m+1; j<n; j++) { x[o][j]=-v; x[n][j]=v++; /* SSE */ x[j][n]=-v; x[j][o]=v++; /* WSW */ }
  }
  biggestValue=v-1; makeActual(xSquare, size); return printSquare(wfp, size);
} // makeOdd
//============================================ main ==========================================

bool validOrder(const int n) {
//   ----------
  if (n==2) { printf("\aERROR: There is no magic square of order 2.\n"); return F; }
  else if ((n==1)|(n==4)) {
    printf("There is no bordered magic square of order %i.\n"
           "Making a normal magic square.\n", n); return T; }
  else if (n<=0) { printf("\aERROR: N must be a positive integer.\n"); return F; }
  return T;
}// validOrder

int main() {
//  ----
  bool ok=F;
  if (openDir()) {
    int n=0; bool another=T, inputSize=T, noWriteError=T;
    do {
      if (inputSize) { printf("\nInput the order of the square: "); n=getSize(); }
      if (validOrder(n)) {
	       if (allocateSquares(n)) {
	         FILE *wfp=wfp=open_File(n);
	         if (wfp!=NULL) {
             noWriteError=n%2 ? makeOdd(xSquare, n, wfp) : makeEven(xSquare, n, wfp);
	           fclose(wfp); checkCorrect(xSquare, n);
	         }
	       } else printf("\a\nERROR: Storage allocation failed.\n");
      }
      if (noWriteError) { ok=T;
        printf("\nMake another square? "
          "input y (yes) or n (no) or the order of the square: ");
        if (getYorOrder(&n)) inputSize=(n==0); else another=F;
      } else { perror("\a\nError writing file"); another=F; }
    } while (another);
    freeSquares();
  }
  printf("\nPress a key to close the console");
  while (!_kbhit()) Sleep(250); return ok?EXIT_SUCCESS:EXIT_FAILURE;
} // main