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;
}