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) / 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 *= 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;
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;
}