Square Tile Pattern Counter (Eternity II Puzzle)

char* title = "Pieces";

char* help[] = { "Program to determine how many unique square tiles can be ",

"generated from a given number of possible edge patterns." };

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define debugprint(p) printf(#p ": %d" EOL, p);

#define dimensionof(p) (sizeof(p)/sizeof(p[0]))

#define EOL "\r\n"

#define putEOL() printf(EOL);

#define writeln(p) printf("%s" EOL, p)

int ipower10(int p)

{

int result = 1;

while(p--)

result *= 10;

return result;

}

int printnc(char c, int n)

{

int result = 0;

while (n--)

result +=putchar(c);

return result;

}

int encommulate(int n, int fieldwidth) // Print a number with comma separaters

{

int m;

int tenx;

int digits;

char dummy = ' ';

char spacer = ' ';

digits = fieldwidth - (fieldwidth / 4);

digits = max(1, digits);

tenx = ipower10(digits);

// check for overflow

if (n / tenx) return printnc('*', fieldwidth);

if (fieldwidth > 13) printnc(' ', fieldwidth - 13);

while(digits--)

{

tenx /= 10;

m = n / tenx;

n -= m * tenx;

if (m || (tenx==1))

{

putchar('0' + m);

dummy = '0';

spacer = ',';

}

else

putchar(dummy);

if (digits && ((digits % 3)==0))

putchar(spacer);

}

return fieldwidth;

}

void getenter(void)

{

printf("Press ENTER to continue/exit.");

while (getchar()!=0xa)

continue;

}

void showhelp(void)

{

int index;

for (index=0; index<dimensionof(help); index++)

writeln(help[index]);

}

int icalculate(int N)

{

// Original formula

return N // All four edges are the same

+ (N * (N-1)) // One edge is different

+ (N * (N-1) / 2)

+ (N * (N-1) * (N-2)) // Two edges are different, two same edges are adjacent

+ (N * (N-1) * (N-2) / 2)

+ (N * (N-1) * (N-2) * (N-3) / 4); // All four edges are different

}

int fcalculate(int n)

{

/* Combining like terms

return ( N )

+ (2 * N * (N-1) )

+ (3 * N * (N-1) * (N-2) / 2 )

+ ( N * (N-1) * (N-2) * (N-3) / 4 );

// Factoring works, but only if N is made a floating point number.

float N;

N = (float)n;

return (int)(N * (1 + ((N-1) * (2 + ((N-2) * (1.5 + ((N-3)/4)))))));

}

int compare_integers(const void* p1, const void* p2)

{

#ifndef invertsort

#define invertsort 0

#endif

#define n1 *(int*)p1

#define n2 *(int*)p2

if (n1==n2) return 0;

if (invertsort)

{

if (n1< n2) return 1;

else return -1;

}

else

{

if (n1< n2) return -1;

else return 1;

}

int main(int argc, char** argv)

{

#define FIELDWIDTH 9

#define MAXCOLORS 24

int number;

int duplicates;

int ix;

int jx;

int kx;

int mx;

int index;

int limit;

int n0; // original number

int n4; // n0 to the 4th power

int n5; // number under test

int* array; // where we store all possible tile arrangements

int* doubles;

int* result;

char* indent = " | ";

char* column_labels[] =

{

"Number of edge patterns/colors set to",

"Number of possible combinations",

"Number of duplicates",

"Number of unique pieces",

"Calculated Number (integer)",

"Calculated Number (float)"

};

writeln(title);

showhelp();

// Display column labels

for (ix=0; ix<dimensionof(column_labels); ix++)

{

for (jx=0; jx<ix; jx++)

printf(indent);

printf(" %s" EOL, column_labels[ix]);

}

for (ix=0; ix<dimensionof(column_labels); ix++)

{

printnc(' ', 1);

printnc('-', FIELDWIDTH-1);

}

putEOL();

limit = MAXCOLORS;

limit *= MAXCOLORS;

limit *= sizeof(*array);

array = (int*)malloc(limit);

doubles = (int*)malloc(limit);

for (number=1; number<=MAXCOLORS; number++)

{

n0 = number;

n4 = number;

n4 *= n4;

encommulate(number, FIELDWIDTH);

encommulate(n4, FIELDWIDTH);

memset(array, 0, limit);

memset(doubles, 0, limit);

index = 0;

for (ix=0; ix<n0; ix++)

for (jx=0; jx<n0; jx++)

for (kx=0; kx<n0; kx++)

for (mx=0; mx<n0; mx++)

array[index++] = (ix << 24) + (jx << 16) + (kx << 8) + mx;

assert((int)index==n4);

duplicates = 0;

for (ix=0; ix<n4; ix++)

{

if (doubles[ix]) // Verify that we haven't already eliminated this one.

continue;

n5 = array[ix];

for (jx = 0; jx<3; jx++) // rotate each piece to the other three positions

{

kx = (n5 & 0xff) << 24;

n5 = kx | (n5 >> 8);

result = bsearch((void*)&n5, (void*)array, (size_t)n4, sizeof(int), compare_integers);

// result==array[ix] does not happen often, but it does happen occasionally

// It happens when we only have one color, then all four sides match, no

// matter which way you rotate it, or when both sets of opposite sides match,

// which only happens when you are only using two of the available colors, and

// you have rotated two positions.

if (result && (result!=&array[ix]))

{

kx = result - array; // Subtract two pointers and the

// difference is index units, not bytes.

if (doubles[kx]==0) // Verify that we haven't already counted this one.

{

doubles[kx] = 1;

duplicates++;

}

encommulate( duplicates, FIELDWIDTH);

encommulate(n4 - duplicates, FIELDWIDTH);

encommulate(icalculate(number), FIELDWIDTH);

encommulate(fcalculate(number), FIELDWIDTH);

if ( ((n4 - duplicates) != icalculate(number))

|| ((n4 - duplicates) != fcalculate(number))

)

printf(" ERROR!");

putEOL();

}

putEOL();

getenter();

return 0;

}