Did you know that the signature of a band can be used to quickly determine:
1) the gangster class (1-44), and
2) the number 3-row permutations that have the given signature?
The "signature" of a band is a 9-long array of digits which appear in each column. For convenience, the three digits in each column are concatenated in ascending order and listed as a single quantity. For example:
- Code: Select all
2 6 9 5 4 3 8 1 7
3 4 7 8 1 2 6 9 5 Signature = { 238, 146, 579, 568, 147, 239, 468, 139, 257 }
8 1 5 6 7 9 4 3 2
This is how it is done: 1) an inexpensive statistic is computed, and 2) the statistic is then correlated to the known answer. The trick is to find a statistic which correlates 100% of the time. Of course, the statistic should be invariant to chute swaps and column swaps within a chute.
In one attempt, the statistic took on 41 different values, and these values correlated with 100% accuracy to the 16 grid completion choices. See routine SignatureTriples(), below. The statistic failed to predict the gangster class.
Later, a modified statistic took on 44 values and correlated precisely to 44 gangster class values. See routine Signature44(), also below.
In each case a statistic is accumulated over triples of columns (one from each chute), afterwhich pairs of columns are compared and "hits" are counted. The modified statistic also uses the count of the unique digits in the three chosen columns.
- Code: Select all
/*******************************************************************************
Compute Population Count Table for 9-bit Quantities
PopCount[i], i=0,...,511 will be the number of bit 1-bits in integer 'i'.
*******************************************************************************/
int PopCount[512] = {-1};
void PopCount_Init ()
{
int i;
if ( PopCount[0] == 0 ) return; // Already done!
PopCount[0] = 0;
for ( i=1; i < 512; i++ )
PopCount[i] = (i & 1) + PopCount[i >> 1];
}
/*******************************************************************************
Purpose:
Given the signature of a band:
1) Compute the "class44" number [1,44].
2) Compute the number of permutation configurations for this band, given
that column-1 digits are in ascending order. This value is returned.
Note:
In array "signature", exactly three of the nine low-order bits of each
value are set to 1, one bit for each value in the column.
*******************************************************************************/
int Signature44 (int signature[9], int *class44)
{
// Binary search list, given "stat" computation.
int SigStatList[44] = {
189000, 705240, 963360,1083040,1152260,1242243,1243330,1261060, // 7
1341160,1343220,1432240,1441040,1503520,1511360,1520160,1530050, // 15
1530060,1602421,1611240,1620040,1620043,1620060,1620151,1631021, // 23
1701220,1710150,1721040,1800000,1800009,1800330,1801221,1802203, // 31
1802220,1810021,1820000,1900023,1900131,2000005,2000022,2100003, // 39
2101002,2103000,2200002,2400000 }; // 43
// Class44 Number, given SigStatList index in [0,43].
int SigStatClass[44] = {
41,17,31,24, 4,38, 9,32,16,18,14, 8,19,15, 7, 1,26,20, 3, 0, 6, 5,
33, 2,11,10,21,25,42,37,22,23,28,13,36,12,27,34,35,29,30,40,39,43 };
// Number of Permutation Triples, given "kat44" in [0,43].
int SigStatTriples[44] = {
46,48,48,28,26,38,28,36,38,32,32,44,24,48, 24,20,30,20,28,24,32, 28,
32,16,28,86,32,32,24,32,32,28,32,32,32,32,144,96,24,96,16,20,16,288 };
// Other declarations
static once = 1;
int f[82], pick[11] = { 0,6,7,10,12,15,20,32,40,48,81 };
int stat, kat44, i, j, k, n;
// Onetime code
if (once) { PopCount_Init(); once=0; }
// Compute statistic: only six elements (not 11)
// of "f" are needed to make the statistic unique.
for ( i=0; i < 6; i++ ) f[pick[i]] = 0;
for ( i=0; i < 3; i++ )
{ for ( j=3; j < 6; j++ )
{ for ( k=6; k < 9; k++ )
{ n = PopCount[ signature[i] & signature[j] ] *
PopCount[ signature[i] & signature[k] ] *
PopCount[ signature[j] & signature[k] ] *
PopCount[ signature[i] | signature[j] | signature[k] ];
f[n]++;
}
}
}
// Finish "stat" computation.
for ( stat=i=0; i < 6; i++ ) stat = (10*stat) + f[pick[i]];
// Find statistic in list (binary search).
for ( kat44 = i = -1, j = 44; j > i+1; )
{ k = (i+j)/2;
if ( SigStatList[k] == stat )
{ kat44 = SigStatClass[k]; break; }
if ( stat < SigStatList[k] ) j = k; else i = k;
}
// Error check
if ( kat44 == -1 )
{ fprintf(stderr,"*** SignatureTriples(): Fatal error.\n");
fprintf(stderr," Statistic \"%d\" not found in list.\n",stat);
exit(1);
}
// Debug
//fprintf(fp,"%2d %3d %7d ::",kat44,SigStatTriples[kat44],stat);
//for ( i=0; i < 6; i++ ) fprintf(fp,"%3d",f[pick[i]]);
//fprintf(fp,"\n");
// All is well!
(*class44) = kat44+1;
return( SigStatTriples[kat44] );
}
/*******************************************************************************
Purpose:
Given the signature of a band, return the number of permutation
configurations for the band, given that column-1 digits are in
ascending order. This is a bit faster than "Signature44".
Note:
In array "signature", exactly three of the nine low-order bits of each
value are set to 1, one bit for each value in the column.
*******************************************************************************/
int SignatureTriples (int signature[9])
{
int SigStatTriples[41] = {
20, 20, 28, 26, 24, 28, 30, 38, 32, 28, 36, 16, 38, 46, // 13
20, 24, 28, 28, 28, 24, 48, 44, 86, 24, 32, 16, 32, 16, // 27
48, 48, 32, 32, 32, 32, 32, 32, 32, 144, 96, 96, 288 }; // 40
int SigStatList[41] = {
54, 66, 72, 82, 84, 86, 92, 100, 102, 104, 106, 108, 114, 128, // 13
130, 138, 142, 150, 152, 160, 168, 178, 180, 192, 194, 196, 202, 222, // 27
248, 262, 280, 286, 336, 368, 372, 410, 504, 880, 936,1092,2268 }; // 40
// Other declarations
static int t[1108] = {0};
int stat, i, j, k, n;
// Onetime code: compute look-up table.
if ( t[0] == 0 )
{ PopCount_Init();
for ( i=1; i < 1108; i++ ) t[i] = 0;
for ( i=0; i < 41; i++ ) t[ (SigStatList[i]-54) >> 1 ] = SigStatTriples[i];
}
// Compute statistic
for ( stat=i=0; i < 3; i++ )
{ for ( j=3; j < 6; j++ )
{ for ( k=6; k < 9; k++ )
{ n = PopCount[ signature[i] & signature[j] ] *
PopCount[ signature[i] & signature[k] ] *
PopCount[ signature[j] & signature[k] ] ;
stat += n*(n+1);
}
}
}
// Error check
if ( stat < 54 || stat > 2268 || t[ n=(stat-54)>>1 ] == 0 )
{ fprintf(stderr,"*** SignatureTriples(): Fatal error.\n");
fprintf(stderr," Statistic \"%d\" not found in list.\n",stat);
exit(1);
}
// Return number of configurations
return( t[n] );
}
