Random Code Post

Facebook Puzzle for Korn Shell.

The code follows:

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;

#define isA(x) ( ('a'<= (x) && (x) <= 'z') || \
   ('A' <= (x) && (x) <= 'Z') )
#define isL(x) ( ('a' <= (x) && (x) <= 'z') )
#define toL(x) ( (x) + 'a' - 'A' )

// Is the sum of the bits that are set
//  less than or equal to 26?
int LESS_THANEQ_26(int x) {
 int count = 0;
 for( int i = 0; i < 26; ++i ) 
  if( x & (1<<i) )
   count += (i+1);
 return !!(count <= 26);
}


// Returns how many bits are set in *nearly* constant time.
inline int COUNT(int x) { 
 x = x - ((x>>1)&033333333333) - ((x>>2)&011111111111);
 return (((x+(x>>3)) & 030707070707) % 63);
}

// gcd(a,b,c) = gcd(a,gcd(b,c)) = gcd(gcd(a,b),c))
// lcm(a,b,c) = lcm(a,lcm(b,c)) = lcm(lcm(a,b),c))
// lcm(a,b) = a*b/gcd(a,b)
unsigned long long gcd( unsigned long long a, unsigned long long b ) {
 if( a == 0 ) { 
  return b;
 }
 return gcd( b % a, a );
}
unsigned long long lcm(unsigned long long a, unsigned long long b)
{ 
 return a * b / gcd(a,b);
}
// Main LCM method to call.
// It will actually call lcm().  This method
// chains all the lcm() calls together.
int LCM(int x) {
 // nothing within the set
 if( x == 0 )  {
  return 0;
 }
 
 unsigned long long a = 1;
 
 for( int i = 0; i < 26; ++i ) {
  if( x & (1<<i) ) { 
   a = lcm(a,i+1);
  }
 }
  
 return (int)(a);
}

// Memoiz keeps the max values of rotations.
int memoiz[27];

// Keeps masks of the bits that are set.
// If a bit is set, then that describes how many
// numbers are in that swap cycle.
int poss[500000];

 
int go() {

 int totalPossValidEntries = 0;

 for( int j = 0; j < (1<<26); ++j ) {
  // At most 6 bits can be set.
  int c = COUNT(j);

  if( c > 6) {
   continue;
  }
   
  poss[totalPossValidEntries++] = j;
 }
 
 // Now the total count is doable for calculating
 // the lcm.
 for (int i = 0; i < totalPossValidEntries; ++i )
  if( LESS_THANEQ_26(poss[i]) )
   memoiz[COUNT(poss[i])] >?= LCM(poss[i]);
   
 // now dp the results.
 for( int i = 0; i <= 26; ++i )
  for( int j = 0; j < i; ++j )
   memoiz[i] >?= memoiz[j];
 
 return 0;
}

int main(int argc, char **argv) {
 go();
 unsigned uniqueElem = 0;
 for( int i = 1; i < argc; ++i ) {        
  for( int j = 0; j < strlen(argv[i]); ++j) {
   if(isA(argv[i][j])) {
    if(isL(argv[i][j])) {
     uniqueElem |= 
      1<<(argv[i][j] - 'a');
    } else {     
     uniqueElem |= 
      1<<(toL(argv[i][j]) - 'a');
    }   
   } 
  }
 }
 cout << memoiz[COUNT(uniqueElem)] << endl;

 return 0;
}