9 x 9 Magic Square

(Top 9 submitted solutions Zimmermann contest)

1408 units retained

1401 units 2^nd best pattern

1400 units

1400

1398

1397

1394

1389

Question #1. How good are we at predicting the correct pattern for maximum water retention for the various orders of magic squares.

Answer – not very good. The top contestants did not find the best pattern for many orders

Question #2. If one has the correct pattern in hand … how good is the machinery in finding the best solution for that pattern?

Answer – computer assisted human ingenuity is probably better at this than #1 above.

Question #3. What volume of water can be exchanged between the lakes and the ponds?

Answer – Order 7 12 units

Order 8 25 units (? greater)

Lake capacities: 284 – 295 7x7 MS 418 units

Lake Base: 284 – 308 8x8 MS 797 units retained

For most orders the interior of the lake seems boring and amorphous. The enumeration of solutions for the order 7 magic square shows that the lake can have a base sum of 161 to 172. The spillway value of course is a constant. The lakes and ponds can exchange a fair amount of water. The Order 9 MS may require a more precise placement of numbers in the lake interior. Its solution was not turned in until the last day of the contest.

I imagine that a careful study was made of the 1407 solution. Improvements in number positioning were then made to achieve the 1408 retention. The dissection below may help to expose the thought process. The yellow cell with red font shows the auto sum of the 9x9 square to the left. Conditional formatting from excel spreadsheet shows duplicate numbers in both solutions in red for the outer border. When the sum of the 4 corner cells decreases by 1 the sum of the outer border increases by one.

			1408										1407
1	37	57	47	66	50	53	55	3		1	40	57	43	66	51	55	53	3
43	59	11	77	25	75	10	15	54		38	59	11	76	30	77	10	14	54
58	7	78	21	34	22	81	12	56		58	4	79	18	35	22	81	16	56
45	73	14	23	32	30	27	74	51		50	72	23	12	41	29	20	74	48
69	17	39	28	52	36	35	26	67	3321	69	17	33	45	52	28	31	26	68	3321
44	72	18	38	42	13	20	76	46		47	73	13	39	27	24	25	75	46
64	6	80	16	31	24	79	8	61		63	5	80	21	36	19	78	7	60
40	65	9	70	19	71	4	62	29		37	65	9	71	15	70	8	62	32
5	33	63	49	68	48	60	41	2		6	34	64	44	67	49	61	42	2
1	37	57	47	66	50	53	55	3		1	40	57	43	66	51	55	53	3
43								54		38								54
58								56		58								56
45								51		50								48
69								67	1465	69								68	1464
44								46		47								46
64								61		63								60
40								29		37								32
5	33	63	49	68	48	60	41	2		6	34	64	44	67	49	61	42	2
				25										30
			21		22								18		22
		14				27						23				20
	17						26		249		17						26		249
		18				20						13				25
			16		24								21		19
				19										15
				25										30
	17						26		87		17						26		88
				19										15
			23		30								12		29
				52					156					52					156
			38		13								39		24
	17								70		17								66
		18										13
			16										21
				19										15
				25										30
					22										22
						27										20
							26		100								26		98
				34										35
					30										29
						35			99							31			95
				66	50	53	55	3						66	51	55	53	3
				25	75	10	15	54						30	77	10	14	54
				34	22	81	12	56						35	22	81	16	56
				32	30	27	74	51						41	29	20	74	48
				52	36	35	26	67	1041					52	28	31	26	68	1040
					50	53	55	3							51	55	53	3
					75	10	15	54							77	10	14	54
					22	81	12	56							22	81	16	56
					30	27	74	51							29	20	74	48
									668										663
						53	55	3								55	53	3
						10	15	54								10	14	54
						81	12	56								81	16	56
									339										342
							55	3									53	3
							15	54									14	54
									127										124

For most orders the interior of the lake seems boring and amorphous. The enumeration of solutions for the order 7 magic square shows that the lake can have a base sum of 161 to 172. The spillway value of course is a constant. The lakes and ponds can exchange a fair amount of water. The Order 9 MS may require a more precise placement of numbers in the lake interior. Its solution was not turned in until the last day of the contest.

I find myself increasingly going to Harry White’s website to utilize the magic square tools he provides. The program below produces a 3d image of the square. The code allows easy modification of the RGB color scheme.

/*

* File: WaterRetention3D.cpp

* Author: S Harry White

* Created: 2011-03-01

* Updated: 2011-04-12

* visual studio 2008 compatability 2011-5-11 Andrew Knecht

* color change 2011-5-18 Craig Knecht

*/

#include "stdafx.h"

#include <assert.h>

#include <direct.h>

#include <errno.h>

#include <io.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#using <mscorlib.dll>

//------------------------------------------------------------------------------

#define max(A, B) ((A) > (B) ? (A) : (B))

#define Uint unsigned long int

int N; // The order of the square.

int N_1; // N - 1

int NN; // N * N

int NN_1; // NN - 1

Uint MagicConstant; // N * (NN + 1) / 2 for 1 base

const int maxN = 200; // browsers can't handle big squares

// and units retained may overflow anyway

int inputSquareNumber, smallestNumber, biggestNumber;

int **xSquare = NULL, **bSquare = NULL;

bool **isSpillWay = NULL;

bool *numberUsed = NULL; // Check that numbers 1..NN are in a magic square.

const int startSquaresSize = 28;

int allocatedSquaresSize = 0;

struct t_Cell {

int priority; // Smaller value has higher priority.

int row;

int col;

};

int allocatedQueueSize = 0;

t_Cell *Queue = NULL;

int qIndex = 0;

//---------------------------------------------------------------------------

char *storeAllocFail = "Storage allocation failed";

void reportError(char *msg)

// -----------

{

printf("\a\nError: %s.\n", msg);

} // reportError

//---------------------------------------------------------------------------

void freeSquare(int*** square, int size)

// ----------

{

if (*square != NULL) {

for(int i = 0; i < size; i++) {

free((*square)[i]);

}

free(*square); *square = NULL;

}

} // freeSquare

void freeIsSpillWay(int size)

// --------------

{

if (isSpillWay != NULL) {

for(int i = 0; i < size; i++) {

free(isSpillWay[i]);

}

free(isSpillWay); isSpillWay = NULL;

}

} // freeIsSpillWay

void freeUsed()

// --------

{

if (numberUsed != NULL) {

free(numberUsed); numberUsed = NULL;

}

} // freeUsed

void freeQueue()

// ---------

{

if (Queue != NULL) { free(Queue); Queue = NULL; }

}

void freeStore()

// ---------

{

freeSquare(&bSquare, allocatedSquaresSize);

freeSquare(&xSquare, allocatedSquaresSize);

freeIsSpillWay(allocatedSquaresSize);

allocatedSquaresSize = 0;

freeUsed(); freeQueue();

}

bool allocateSquare(int*** square, int size)

// --------------

{

bool ok;

*square = (int**) malloc(size * sizeof(int*));

ok = (*square != NULL);

if (ok) {

int numAllocated = 0;

for(int i = 0; i < size; i++) {

int* p = (int*) malloc(size * sizeof(int)); (*square)[i] = p;

if (p == NULL) { numAllocated = i; ok = false; break; }

}

if (!ok) freeSquare(square, numAllocated);

}

return ok;

} // allocateSquare

bool allocateIsSpillWay(int size)

// ------------------

{

bool ok;

isSpillWay = (bool**) malloc(size * sizeof(bool*));

ok = (isSpillWay != NULL);

if (ok) {

int numAllocated = 0;

for(int i = 0; i < size; i++) {

bool *p = (bool*) malloc(size * sizeof(bool)); isSpillWay[i] = p;

if (p == NULL) { numAllocated = i; ok = false; break; }

}

if (!ok) freeIsSpillWay(numAllocated);

}

return ok;

} // allocateIsSpillWay

bool allocateUsed(int size)

// ------------

{

return ( (numberUsed = (bool*) malloc(size * sizeof(bool))) != NULL);

} // allocateUsed

//---------------------------------------------------------------------------

bool allocateQueue(int size)

// -------------

{

bool ok = true;

if (allocatedQueueSize < size) {

freeQueue();

Queue = (t_Cell *) malloc(size * sizeof(t_Cell));

if (ok = (Queue != NULL)) allocatedQueueSize = size;

}

return ok;

} // allocateQueue

bool increaseQueue()

// -------------

{

int size = allocatedQueueSize + allocatedQueueSize;

t_Cell *tmp = (t_Cell *) malloc(size * sizeof(t_Cell));

if (tmp == NULL) { reportError(storeAllocFail); return false; }

for (int i = 0; i < qIndex; i++) tmp[i] = Queue[i];

freeQueue(); Queue = tmp; allocatedQueueSize = size;

return true;

} // increaseQueue;

bool allocateStore(int size)

// -------------

{

bool ok = true;

if (size < startSquaresSize) size = startSquaresSize;

if (size > allocatedSquaresSize) {

freeStore();

if (ok = allocateSquare(&xSquare, size))

if (ok = allocateSquare(&bSquare, size))

if (ok = allocateIsSpillWay(size))

if (ok = allocateQueue(size*size))

if (ok = allocateUsed(size*size+1))

allocatedSquaresSize = size;

if (!ok) freeStore();

}

return ok;

} // allocateStore

//---------------------------------------------------------------------------

//FILE *Qfp = NULL;

//void printQueue()

//// ----------

//{

//

// int i = 0;

// while (i < qIndex) {

// t_Cell *q = &Queue[i];

// fprintf(Qfp,"priority %d row %d col %d\n",

// q->priority, q->row, q->col);

// i++;

// }

// fprintf(Qfp,"\n");

//} // printQueue

//---------------------------------------------------------------------------

enum magicType {notMagic, notNormal, Normal};

magicType isMagic(bool checkZeroBased)

// -------

{

//if (N > maxNMagicConstant) return Normal; // Overflow, can't check.

Uint chkSum = 0;

Uint magicSum = checkZeroBased ? MagicConstant - N : MagicConstant;

int min = checkZeroBased ? 0 : 1, max = NN + min - 1;

Uint sumX, sumY, sumXY = 0, sumYX = 0;

for (int i = min; i <= max; i++) numberUsed[i] = false;

for (int i = 0; i < N; i++) {

sumX = 0; sumY = 0;

for (int j = 0; j < N; j++) {

int tmp = xSquare[i][j];

if ((min <= tmp) && (tmp <= max)) numberUsed[tmp] = true;

sumX += tmp;

sumY += xSquare[j][i];

}

if (i == 0) chkSum = sumX;

if ((sumX != chkSum) || (sumY != chkSum)) return notMagic;

sumXY += xSquare[i][N_1-i];

sumYX += xSquare[i][i];

}

if ((sumXY != chkSum) || (sumYX != chkSum)) return notMagic;

if (chkSum != magicSum) return notNormal;

for (int i = min; i <= max; i++) if (!numberUsed[i]) return notNormal;

return Normal;

} // isMagic

//--------------------------------------------------------------------------

void outputLocalTime()

// --------------

{

time_t startTime = time(NULL);

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 initBounds(int value)

// ----------

{

for (int r = 0; r < N; r++) {

bSquare[r][0] = xSquare[r][0];

bSquare[r][N_1] = xSquare[r][N_1];

}

for (int c = 1; c < N_1; c++) {

bSquare[0][c] = xSquare[0][c];

bSquare[N_1][c] = xSquare[N_1][c];

}

for (int r = 1; r < N_1; r++)

for (int c = 1; c < N_1; c++)

bSquare[r][c] = value;

qIndex = 0;

} // initBounds

//---------------------------------------------------------------------------

void pushQueue(int priority, int row, int col)

// ---------

{

assert (qIndex < allocatedQueueSize);

t_Cell cell;

cell.priority = priority; cell.row = row; cell.col = col;

Queue[qIndex++] = cell;

} // pushQueue

bool insertQueue(int priority, int row, int col)

// -----------

{

if ((qIndex >= allocatedQueueSize) && !increaseQueue()) return false;

t_Cell cell;

cell.priority = priority; cell.row = row; cell.col = col;

int i = qIndex-1;

while (Queue[i].priority < priority) {

Queue[i+1] = Queue[i]; if (--i < 0) break;

}

Queue[++i] = cell; ++qIndex;

//printQueue();

return true;

} // insertQueue

void popQueue(t_Cell *cell)

// --------

{

assert(qIndex > 0); *cell = Queue[--qIndex];

}

//---------------------------------------------------------------------------

bool queueBorder()

// -----------

{

pushQueue(bSquare[1][0], 1, 0);

if (!insertQueue(bSquare[1][N_1], 1, N_1)) return false;

for (int r = 2; r < N_1; r++) {

if (!insertQueue(bSquare[r][0], r, 0)) return false;

if (!insertQueue(bSquare[r][N_1], r, N_1)) return false;

}

for (int c = 1; c < N_1; c++) {

if (!insertQueue(bSquare[0][c], 0, c)) return false;

if (!insertQueue(bSquare[N_1][c], N_1, c)) return false;

}

return true;

} // queueBorder

//---------------------------------------------------------------------------

bool computeBounds(int p, int r, int c)

// -------------

{

if ( ( (0 < r) && (r < (N_1)) ) &&

( (0 < c) && (c < (N_1)) ) ) {

int *bp = &bSquare[r][c];

int tmp = max(xSquare[r][c],p);

if (tmp < *bp) {

*bp = tmp;

if (!insertQueue(tmp, r, c)) return false;

}

}

return true;

} // computeBounds

//---------------------------------------------------------------------------

void computeCapacity()

// ---------------

{

Uint count = 0, units = 0;

for (int r = 0; r < N; r++)

for (int c = 0; c < N; c++) {

int delta = bSquare[r][c] - xSquare[r][c];

if (delta != 0) { ++count; units += delta; }

}

if (units == 0)

printf("Square number %d: units retained 0\n\n", inputSquareNumber);

else

printf("Square number %d: units retained %u, cells retaining %u\n\n",

inputSquareNumber, units, count);

} // computeCapacity

//---------------------------------------------------------------------------

const int di[] = {1, 0, -1, 0}, dj[] = {0, 1, 0, -1};

void getSpillWays()

// ------------

{

for (int j = 0; j < N; ++j) for (int i = 0; i < N; ++i)

isSpillWay[j][i] = false;

int **x = xSquare, **b = bSquare;

for (int j = 1; j < N_1; ++j) for (int i = 1; i < N_1; ++i) {

if (b[j][i] > x[j][i]) {

for (int d = 0; d < 4; ++d) {

int li = di[d] + i, lj = dj[d] + j;

if (x[lj][li] == b[j][i]) isSpillWay[lj][li] = true;

}

}

}

} // getSpillWays

//---------------------------------------------------------------------------

/*

* Based on an algorithm of Gareth McCaughan supplied by Craig Knecht.

*/

bool getWater(int base1factor)

// --------

{

//fopen_s(&Qfp, "C:\\QueueTrace.txt", "w");

for (int j = 0; j < N; ++j) for (int i = 0; i < N; ++i)

xSquare[j][i] -= base1factor;

initBounds(biggestNumber-base1factor);

if (!queueBorder()) return false;

while (qIndex != 0) {

//printQueue();

t_Cell cell; popQueue(&cell);

int p = cell.priority, r = cell.row, c = cell.col;

if (!computeBounds(p, r-1, c)) return false;

if (!computeBounds(p, r+1, c)) return false;

if (!computeBounds(p, r, c-1)) return false;

if (!computeBounds(p, r, c+1)) return false;

}

computeCapacity();

getSpillWays();

//fclose(Qfp);

return true;

} // getWater

//==========================================================================

bool inputSquare(FILE *rfp)

// -----------

{

bool checkZeroBased = false;

smallestNumber = LONG_MAX; biggestNumber = LONG_MIN;

for (int r = 0; r < N; r++) {

for (int c = 0; c < N; c++) {

int rv, tmp;

if ( (rv = fscanf_s(rfp, "%d", &tmp)) != 1) {

if ( (rv != EOF) || (r != 0) || (c != 0) )

reportError("Reading square from file");

return false;

} else {

if (tmp == 0) checkZeroBased = true;

if (tmp > biggestNumber) biggestNumber = tmp;

if (tmp < smallestNumber) smallestNumber = tmp;

xSquare[r][c] = tmp;

}

}

}

++inputSquareNumber;

magicType t = isMagic(checkZeroBased);

if (t == notMagic) {

printf("Square number %d is not a magic square.\n",

inputSquareNumber);

} else if (t == notNormal) {

printf("Square number %d is not a normal magic square.\n",

inputSquareNumber);

}

return true;

} // inputSquare

//--------------------------------------------------------------------------

void initGlobals()

// -----------

{

N_1 = N - 1;

NN = N * N;

MagicConstant = N * (NN + 1) / 2;

} // initGlobals

//--------------------------------------------------------------------------

void get_rest_of_line(int c)

// ----------------

{

if (c != '\n') do { c = getchar(); } while (c != '\n');

}

bool getY()

// ----

{

int c; do { c = getchar(); }

while ((c == ' ') || (c == '\t') || (c == '\n'));

get_rest_of_line(c); return (c == 'Y') || (c == 'y');

}

// If user inputs size instead of 'y' or 'n', use it.

bool getYorOrder(int *n)

// -----------

{

bool result = false; int c; *n = 0;

do { c = getchar(); } while ((c == ' ') || (c == '\t') || (c == '\n') );

if ( (c == 'Y') || (c == 'y') )

result = true;

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 = true;

}

get_rest_of_line(c);

return result;

} // getYorOrder

int getSize()

// -------

{

int n = 0; int unused = scanf_s("%d", &n);

int c = getchar(); get_rest_of_line(c);

return n;

}

bool getFileName(char *buf, 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");

get_rest_of_line(*s);

return false;

}

while ( (*--s == ' ') || (*s == '\t') ); // strip any trailing whitespace

*++s = '\0';

return true;

} // getFileName

//--------------------------------------------------------------------------

const int bufSize = 1024;

FILE *openInput(char *buf, int size) {

// ---------

char *rFname = NULL;

do {

printf("\nEnter the name of the squares file: ");

if (getFileName(buf, size - 4)) { // reserve 4 to add .txt if needed

rFname = buf; break;

} else {

printf("\a\nCan't read the file name. Try again? y (yes) or n (no) ");

if (!getY()) break;

}

} while (true);

FILE *rfp = NULL;

if (rFname != NULL) {

char *s = buf; bool txt = false; while (*s++ != '\0');

while (--s != buf)

if (*s == '.') {

txt = (*++s == 't') && (*++s == 'x') && (*++s == 't') && (*++s == '\0');

break;

}

if (!txt) strcat_s(buf, size, ".txt"); // no .txt, add it

if (fopen_s(&rfp, rFname, "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 int outSize = bufSize + 50;

void stripName(char *inFname, char *obuf)

// ---------

{

char *s = inFname;

while (*s++ != '\0');

while (--s != inFname)

if (*s == '.') *s = '\0'; // Remove .txt

else if (*s == '\\') { ++s; break; } // Remove any directory path

strcpy_s(obuf, outSize, s);

} // stripName

//--------------------------------------------------------------------------

bool openDir(char *dir) {

// -------

char baseName[bufSize];

sprintf_s(baseName, bufSize, "Water%d_3D", N);

strcpy_s(dir, bufSize, baseName);

int fd = -1, sub = 0;

do {

if ( (fd = _mkdir(dir)) != -1) break;

if (errno != EEXIST) {

sprintf_s(baseName, bufSize, "\a\nCan't make folder %s", dir);

perror(baseName); return false;

}

sprintf_s(dir, bufSize, "%s_%d", baseName, ++sub);

} while (true);

printf("Output file(s) are in folder %s\n", dir);

return true;

} // openDir

//--------------------------------------------------------------------------

FILE *openOutput(char *dir, char* inFname)

// ----------

{

const int baseSize = bufSize + 25;

char buf[outSize], baseName[baseSize];

sprintf_s(baseName, baseSize, "%s\\%sSquare%d",

dir, inFname, inputSquareNumber);

sprintf_s(buf, outSize, "%s.svg", baseName);

FILE *wfp = NULL; int sub = 0;

do {

if (_access_s(buf, 00) == ENOENT) {

break;

} else {

sprintf_s(buf, outSize, "%s%d.svg", baseName, ++sub);

}

} while (true);

if (fopen_s(&wfp, buf, "w") != 0) {

sprintf_s(baseName, outSize, "\a\nCan't open for write %s", buf);

perror(baseName);

}

return wfp;

} // openOutput

//--------------------------------------------------------------------------

bool checkSize()

// ---------

{

if (N <= 0) {

reportError("Order must be a positive integer"); return false;

} else if (N > maxN) {

char msg[100];

sprintf_s(msg, 100, "Order limit is set at %d", maxN);

reportError(msg); return false;

}

return true;

} // checkSize

//--------------------------------------------------------------------------

void reportElapsedTime(time_t startTime)

// -----------------

{

int et = (int)(time(NULL) - startTime);

if (et > 0)

printf("\nelapsed time %d:%02d:%02d\n", et/3600, et%3600/60, et%60);

} // reportElapsedTime

//--------------------------------------------------------------------------

bool doAnother(bool *inputSize, bool writeError)

// ---------

{

if (writeError) return false;

printf

("\nContinue? input y (yes) or n (no) or the order of the squares: ");

if (getYorOrder(&N)) {

*inputSize = (N == 0); return true;

} else {

freeStore(); return false;

}

} // doAnother

//--------------------------------------------------------------------------

double dim3D()

// -----

{

return N < 20 ? 300.0 * log((double)N)

: N < 32 ? 42.0*N : N < 100 ? 45.0*N : 50.0*N;

} // dim3D

//-------------------------------------------------------------------------

int getMinMax(int *minDepth, int *maxDepth)

// ---------

{

int **x = xSquare, **b = bSquare;;

int min = LONG_MAX, max = 0, maxStep = 0;

for (int j = 0; j < N; ++j) for (int i = 0; i < N; ++i) {

int d = b[j][i] - x[j][i];

if (min > d) min = d; if (max < d) max = d;

}

*minDepth = min; *maxDepth = max;

for (int j = 0; j < N; ++j) for (int i = 0; i < N_1; ++i) {

int d = x[j][i+1] - x[j][i];

if (maxStep < d) maxStep = d;

d = x[i+1][j] - x[j][i];

if (maxStep < d) maxStep = d;

}

return maxStep;

} // getMinMax

//-------------------------------------------------------------------------

bool writeHead(FILE *sfp, double dim)

// ------------

{

return

fprintf(sfp,

"<?xml version=\"1.0\" encoding=\"UTF-8\" "

"standalone=\"no\"?>\n<svg\n"

"xmlns:svg=\"http://www.w3.org/2000/svg\"\n"

"xmlns=\"http://www.w3.org/2000/svg\"\n"

"xmlns:xlink=\"http://www.w3.org/1999/xlink\"\n"

"version=\"1.0\"\nwidth=\"%g\"\nheight=\"%g\"\n"

"id=\"magic_s\"\n>\n", dim, dim) > 0;

} // writeHead

//-------------------------------------------------------------------------

const char black[] = "000000", white[] = "ffffff", blue[] = "000fff";

void getColors

// ---------

(int j, int i, int minDepth, int maxDepth,

int *r, int *g, int *b, const char **textColor)

{

if (bSquare[j][i] == xSquare[j][i]) {

*textColor = black;

if (isSpillWay[j][i]) { // yellow

*r = 224; *g = 224; *b = 50;

} else { // green

int xji = xSquare[j][i]; if (xji > NN) xji = NN;

*r = 222; *g = 128 + xji*127/NN; *b = 0;

}

} else { // blue

int d = bSquare[j][i] - xSquare[j][i];

*r = 0; *g = 0;

*b = 200 - (d - minDepth)*128/(maxDepth - minDepth);

*textColor = black;

}

} // getColors

//-------------------------------------------------------------------------

/*

* Adapted from code written in 2010 by Claudio Rocchini supplied

* by Craig Knecht.

*

* Changes:

* . code the water retention calculations using an algorithm

* of Gareth McCaughan, (handles repeated square numbers)

* . normalize the cell numbers wrt the smallest number

* . adjust the green color calculation for large relative numbers

*/

bool drawRetained(FILE *sfp, bool *writeError)

// ------------

{

const bool view3D = true;

int **x = xSquare;

int base1Factor = smallestNumber - 1;

if (!getWater(base1Factor)) { *writeError = false; return false; }

int minDepth = NN, maxDepth = 0,

maxStep = getMinMax(&minDepth, &maxDepth);

double dim = dim3D(); // drawing size

if (!writeHead(sfp, dim)) return false;

const double B = 64; // white border

const double S = (dim - B*2)/N; // tile size

const double fontSize = S/3;

const double DZ = view3D ? (S/3)/maxStep : 0; // deltaz

*writeError = true;

for (int j = 0; j < N; ++j) for (int i = 0; i < N; ++i) {

int red, green, blue; const char *textColor;

getColors(j, i, minDepth, maxDepth, &red, &green, &blue, &textColor);

double z = DZ * (x[j][i] - 1);

if (fprintf(sfp,

"<path d=\"M %5.1lf,%5.1lf L %5.1lf,%5.1lf "

"L %5.1lf,%5.1lf L %5.1lf,%5.1lf Z\" "

"style=\"fill:#%02X%02X%02X;stroke:#000000;"

"stroke-width:1;stroke-opacity:1\" />\n",

B+(i+0)*S-z, B+(j+0)*S-z,

B+(i+1)*S-z, B+(j+0)*S-z,

B+(i+1)*S-z, B+(j+1)*S-z,

B+(i+0)*S-z, B+(j+1)*S-z,

red, green, blue) < 0) return false;

int xji = x[j][i] + base1Factor;

if (fprintf(sfp,

"<text x=\"%5.1f\" y=\"%5.1f\" font-size=\"%gpx\" "

"text-anchor=\"middle\" fill=\"#%s\">%d</text>\n",

B+(i+0.5)*S-z, B+(j+0.5)*S-z+fontSize/2,

fontSize, textColor, xji) < 0) return false;

double zr = DZ * (i == N_1 ? 0 : x[j][i+1] - 1);

if (view3D && zr < z)

if (fprintf(sfp,

"<path d=\"M %5.1f,%5.1f L %5.1f,%5.1f "

"L %5.1f,%5.1f L %5.1f,%5.1f Z\" "

"style=\"fill:#808080;stroke:#000000;"

"stroke-width:1;stroke-opacity:1\" />\n",

B+(i+1)*S-z, B+(j+0)*S-z,

B+(i+1)*S-zr, B+(j+0)*S-zr,

B+(i+1)*S-zr, B+(j+1)*S-zr,

B+(i+1)*S-z, B+(j+1)*S-z) < 0) return false;

double zb = DZ * (j == N_1 ? 0 : x[j+1][i]-1);

if (view3D && zb < z)

if (fprintf(sfp,

"<path d=\"M %5.1f,%5.1f L %5.1f,%5.1f "

"L %5.1f,%5.1f L %5.1f,%5.1f Z\" "

"style=\"fill:#404040;stroke:#000000;"

"stroke-width:1;stroke-opacity:1\" />\n",

B+(i+1)*S-z, B+(j+1)*S-z,

B+(i+1)*S-zb, B+(j+1)*S-zb,

B+(i+0)*S-zb, B+(j+1)*S-zb,

B+(i+0)*S-z, B+(j+1)*S-z) < 0) return false;

if (view3D && (x[j][i] < bSquare[j][i])) {

double z = DZ * (bSquare[j][i] - 1);

if (fprintf(sfp,

"<path d=\"M %5.1f,%5.1f L %5.1f,%5.1f "

"L %5.1f,%5.1f L %5.1f,%5.1f Z\" "

"style=\"fill:#0080FF;stroke:none;fill-opacity:0.4\" />\n",

B+(i+0)*S-z, B+(j+0)*S-z,

B+(i+1)*S-z, B+(j+0)*S-z,

B+(i+1)*S-z, B+(j+1)*S-z,

B+(i+0)*S-z, B+(j+1)*S-z) < 0) return false;

}

}

*writeError = false;

return fprintf(sfp, "</svg>\n") > 0;

} // drawRetained

//------------------------------------------------------------------------------

bool make3D(FILE *sfp, bool *writeError)

// ------

{

if (drawRetained(sfp, writeError)) {

return true;

} else {

if (*writeError) reportError("problem writing svg file");

return false;

}

} // make3D

//------------------------------------------------------------------------------

bool make3Dsquare(char *dir, char *inFname, bool *writeError)

// ------------

{

FILE *wfp = openOutput(dir, inFname);

if (wfp == NULL) return false;

bool ok = make3D(wfp, writeError); fclose(wfp);

return ok;

} // make3Dsquare

//--------------------------------------------------------------------------

using namespace System;

using namespace System::Threading;

int main() {

// ----

outputLocalTime();

bool another = true, inputSize = true;

do { // for each input file

bool writeError = false;

if (inputSize)

{ printf("\nInput the order of the squares: "); N = getSize(); }

if (checkSize()) {

initGlobals();

if (allocateStore(N)) {

char dir[bufSize];

if (openDir(dir)) {

const int inSize = bufSize + 4; // +4 to add .txt if needed

char ibuf[inSize], obuf[outSize];

FILE *rfp = openInput(ibuf, inSize);

stripName(ibuf, obuf);

if (rfp != NULL) {

time_t startTime = time(NULL);

inputSquareNumber = 0;

while (inputSquare(rfp)) { // for each square in file

if (!make3Dsquare(dir, obuf, &writeError)) break;

}

fclose(rfp);

reportElapsedTime(startTime);

} // (rfp != NULL

} // if (openDir

} // (allocateStore

} // (checkSize

another = doAnother(&inputSize, writeError);

} while (another);

printf("\n\nPress a key to close the console.");

while (!Console::KeyAvailable) Thread::Sleep(250);

return 0;

} // main