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

Bitwise Ops and Its Applications

Bitwise Operations

Let's go over some basics. The most basic bitwise operations are |, &, ~, ^, and their respective assignment versions: |=, &=, ^=.

| is the OR operation. It will perform the OR of two (2) operands.
& is the AND operation. It will perform the AND of two (2) operands.
^ is the XOR operation. It will perform the XOR of two (2) operands.
~ is the "tilde" operation. It will flip the bits of a given integral type.

(Also, << and >> are left and right shifts)

Therefore, we can use integral types to perform these bitwise operations under.
I will assume everyone knows what the basic bitwise operations actually do.

Therefore, to go over why something like this would be useful. It is handy to keep track of lists without keeping bigger or larger datastructures, especially when the data is small. Meaning, that you just want to keep track of the indexes or numbers that are in or out of the list. With that said, using bitwise on integral types is ideal.

The basic knowledge is to look at the bits as indexes within an array for a given integral type. Then to include number i, you include bit i to the integral type. This is easy. To do that, you just bitwise-OR the integral type with the ith-bit being set. To do so, you would need to use the left shift (<<) operator. This is very useful. To unset or excludle a bit within a set you need a trick to take it from the list. There are many ways to do this; however, many of them need checks in order to not modify the actual integral type if that bit is NOT even in there. Therefore, an easy way to do this is the bitwise-AND the integral type with all bits set to 1 except the ith-bit. After this knowledge, now we know how to implement a bitset or set using an integral type without using a big datastructure. Since it is just overhead if you only are concerned with storing numbers. However, using integral types is limitd because currently the largest integral type is a uint64_t, which holds only 64 bits meaning the number range from 0 - 63. But the implementation follows:

uint64_t bitset = 0; // free all the bits within this integral type

// include the i-th bit
void include(int i)
{
   biset |= (1<<i);
}

// exclue the i-th bit
void exclude(int i)
{
   bitset &= ~(1<<i);
}

Bitwise operations are used heavily within orgranizing massive amounts of data - bitset tree structures. Also, with file systems and organizing data.

Doubly-Linked Lists

Doubly Linked Lists

I was reading this article the other day and thought I should share its contents. It's quite interesting. It has the notion of using one pointer to construct a doubly linked list of nodes. It copies the notion of the XOR-swap described in a previous article.

   x ^= y ^= x ^= y;

However, we don't need to swap, but only hold the XOR value of x and y, namely the value of

   x ^ y

Therefore, we can have one pointer hold the XOR of the prev and next nodes. And to extract the previous, you XOR the combination with the next node, and vice versa to extract the next node. This quite simple, but effecient. Also, when assigning a new value for this one pointer that holds the XOR-combination, you need to remove one of the two and replace it with a new value. The code below follows:

   #ifdef __BIT_32_REGISTER__
      #define XOR(a,b) ( (typeof((a))) ((unsigned)(a) ^ (unsigned)(b)) )
   #else  /*__BIT_64_REGISTER__*/
      #define XOR(a,b) ( (typeof((a))) \
       ((unsigned long long)(a) ^ (unsigned long long)(b)))
   #endif

   initial XOR setup:
   node->onePointer = XOR(prev,next);

   // since we know that onePointer always holds 
   // prev ^ next of the current node, we can just XOR
   // out the prev or next value:
   // 1.) let's replace the previous node with a new prev
   node->onePointer = XOR(node->onePointer,XOR(oldPrev,newPrev));

   // 2.) let's repalce the next node with a new next node
   node->onePointer = XOR(node->onePointer,XOR(oldNext,newNext));

Therefore, now we know what the single pointer should hold. And since it holds the XOR combination, we can XOR it with the prev (that's supposed to have been set with the next to come up with this XOR combination value, meaning onePointer ^ prev will remove prev, and will evaluate the value to just "next" within the XOR combination value) to remove it, and vice versa with the next pointer.

F-Question

Given a range [a,b], find out how many numbers within the range, have a prime number of bits set.
The brute force solution is too slow, especially if [a,b] are 64-bit unsigned integers, which in this case we'll assume.

Therefore, we need a way to count the bits. If perhaps we had a perfect range, meaning it was between 0 and a power of 2, then the number of bits that are prime, are the number of bits choose (prime number <= number of bits to choose from). The reason, being is that if we have n bits to choose from, and we want to pick p bits to be set to 1, then there are C(n,p) ways to choose the numbers., all of which are unique.

0000 - 0111 (where the power of 2 would be 1000 in this case)
So all we have to do is look at the bits that we can choose from, 3.
And we have two different prime number values to be chosen - 2 and 3.

Therefore, C(3,2) + C(3,3) is the total number of ways to do this.
This is the easy case. However, numbers aren't exactly given to us in such a perfect world. Multiple bits could be set for a given number x:
101011101

In this case we split the ranges into powers of 2 decreasing within MSB. Why am I doing this? Because it will be easier to calculate the number of bits within the given range. Because it basically reduces the problem to the initial power-of-2 solution we came up with earlier, except now we have a notion of fixed bits and free bits. The fixed bits have to be counted, however, the free bits have a choice. Therefore, the choose function will have to account that the free bits to choose from + fixed bits = prime number of bits. Therefore, we need to have the choose function to be C(n,k-fixed) such that k is prime, therefore, you are only going to choose k-fixed bits from the remaining n left. (It would be nice if k-fixed was >= 0)

The reason that these range values would be a power-of-2 solution is because the right most end of the range would be a "type" of power-of-2 - 1 value, meaning the difference between start and end is that you only have to look at the right most 1-bits that are set, and keep into consideration the remaining bits to the left that are "fixed" when computing the choose function. So, therein lies one last problem, generating all the powers-of-2 numbers starting from MSB and appending the new power-of-2 number. Also, there should be a function to count the number of bits that are set.

The following code shows the entire procedure: (C++)

#include <string>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

typedef unsigned long long uint64_t;

#define MAX_BITS 64

// decently quick way to count how many bits are set:
uint64_t MIT( uint64_t x ) {
    x = x - ((x>>1ULL)&0x7777777777777777ull)
          - ((x>>2ULL)&0x3333333333333333ull)
          - ((x>>3ULL)&0x1111111111111111ull);
    x = ((x+(x>>4ULL))&0x0f0f0f0f0f0f0f0full) % 255;
}

// memoiz the choose function
map<pair <uint64_t,uint64_t>, uint64_t> nck;

// keeps the list of ranges: 
vector<uint64_t> start, end;

uint64_t next( uint64_t z, uint64_t x, int &y) {
    if (y == -1) return 0;

    for (int i = y; i >= 0; --i) {
        if (x & (1ULL<<i)) {
            // next time y will start
            //  at next (lower) index
            y = i-1;
            return z | (1ULL<<i);
        }
    }
    y = -1;
    return 0;
}
void init(uint64_t x) {
    // always append zero (0) first
    start.push_back(0);

    uint64_t z = 0;

    // which bit do we set? 
    int y = MAX_BITS-1;
    while ((z=next(z,x,y)) != 0) {
        start.push_back(z);
    }
}
uint64_t nchoosek( uint64_t n, uint64_t k)
{
    if (k > n) return 0;
    if (n == k) return 1;
    if (n == 0) return 0;
    if (k == 0) return 1;

    // memoized solution? 
    if (nck.count(make_pair(n,k))) {
        return nck[make_pair(n,k)];
    }
    // memoiz the solution here:
    return nck[make_pair(n,k)] = 
            nchoosek(n-1,k-1) + nchoosek(n-1,k);
}

int isPrime( int x ){
    if (x < 2) {
        return 0;
    }

    // could optimize it for just odd's and 2
    for (int i = 2; i*i <= x; ++i) {
        if ((x % i) == 0) {
            return 0;
        }
    }
    return 1;
}

uint64_t R( uint64_t x1, uint64_t x2) {
    // get the digits that are free
    uint64_t n = MIT(x2 - x1); 

    // find the number of fixed digits
    int fixed = MIT(x2 - (x2-x1)); //MIT(x1 & ~(x2-x1));

    uint64_t sum = 0;    // sum up the diff prime(s)

    // go through all primes, starting with fixed+const
    for (int x = fixed + n; x - fixed >= 0; --x) {
        if (isPrime(x)) {
            sum += nchoosek(n,x-fixed);
        }
    }
    return sum;
}
uint64_t f( uint64_t x ) {
    // find all the ranges
    init(x);

    for (int i = 1; i < start.size(); ++i) {
        end.push_back(start[i]-1);
    }
    end.push_back(start[end.size()]);

    // go through each range, and calculate the sums
    uint64_t sum = 0;

    for (int i = 0; i < start.size(); ++i) {
        sum += R(start[i],end[i]);
    }

    return sum;
}

uint64_t bits_prime( uint64_t a, uint64_t b )
{
        uint64_t fb = f(b);

        // clear the range lists:
        start.clear(); end.clear();

        uint64_t fa = f(a);

        // inclusion exclusion rule:                                                                                                                                                                                                
        return (fb - fa + isPrime(MIT(a)));
}                                                                                                                                                            

Pointer Fun

Pointers

The term pointer is basically just another word for number. The only difference is that there is something unique about the pointer type. You are allowed to dereference it, meaning you are allowed to go to the actual (virtual) memory address and get its value located at that memory address.

Other than that, it can be addressed using an unsigned integer (if it's 32-bits) or an unsigned long long (if it's 64-bits).

Therefore, in C++, you can do something like the following.
char *c = (char *)malloc(32);

The same thing can be addressed using an unsigned int.
unsigned int i = (unsigned int)malloc(32);

The values of c and i are identical and equivalent. However, you cannot go to the memory address of c and dereference (without casts) using the variable i, type being unsigned int. However, with casts you can:

*((char *)i) = 'a';
*c = 'a'

The two expressions above yield the same exact semantics. The syntax is a bit different, but they *mean* the same thing. This is probably the hardest concept for beginner programmers of the C/C++ language to understand and fully grasp. If you understand this, then malloc() and free()ing are completely understandable. They are after all using number values, and an unsigned int is a 32-bit number value, which is the same type for a pointer on a 32-bit machine.

Casting between ints and pointers is done a lot, especially within OS/network specific applications. Manipulating pointers is essential to get into deep OS-specific applications, and therefore, this is a good way to start that type of learning. Also, anytime you get confused, just think of a pointer as an integer. Anywhere you can modify an integer with it being legal, the same holds true of a pointer type. After all, they are the same thing.

The most humorous example is when you pass a struct in by pointer, and you change an attribute of that struct. In general terms, anything you change within the function becomes changed., even if it's a pointer attribute. Some get really confused about this because when you pass something by pointer and you try to assign it a different value, the value after function calls remains unchanged. However, this is a different example, because the attributes of the struct being passed in by pointer is the actual address of the attributes. So you are actually going to its (virtual) memory address and changing it literally.

Manipulating memory is very intoxicating and fun as well.
Let's say you have this:

   typedef struct A {
        int a;
        char b;
   } A_t;
   typedef struct B {
        int c;
        A_t *a;
        short d;
   } B_t;

And you want to allocate space for the entire struct of B as well as the pointer to type A_t. But you can only use one malloc() call. How would you do this? Well the answer is to allocate space for both of them; however, you are going to have to have both structures side by side in (virtual) memory. This is quite simple.

   char *c = (char *)malloc(sizeof B_t + sizeof A_t);
   B_t *b = (B_t *)c; // first part is B_t
   b->a = (A_t *)(c + sizeof B_t); // second part is A_t

Therefore, you allocated space for both pointers, initializing the entire struct B_t.

A-Question

Suppose you are trying to print out the mirror image of a tree, a binary tree to boot.
How would you go about doing this? Well, if you know anything about tree structures, you know they are heavily recursive. There are two ways to do this, either modify the tree to be its mirror image, or come up with a way to traverse it mirror-imagedly. The funny thing is, it's virtually the same concept. However, I'm going to show you the former way. (I'll leave it as an exercise to the do latter algorithm)

This is going to be very short and sweet. The only thing you have to do is, change the pointers from right to left, and left to right, assuming you are granted the root node of the tree. Just do it recursively, like so:

   void mirrorImage( Node *root )
   {
      Node *left = root->left;
      Node *right = root->right;
      root->right = left;
      root->left = right;

      // now recurse like a heathen
      if (left) {
         mirrorImage(left);
      }
      if (right) {
         mirrorImage(right);
      }
   }

So basically you update the pointers, and then do it recursively. After all of this is finished, the result will be the mirror image of the tree.

C++ Tricks: Part II

Another set of tricks.

I am going to outline a couple of more tricks that are used for interviews and overall cool things to know:

How to identify the endianness of a machine:
The easiest way to do this is using a pointer to a short, and figuring out if the low order is a certain value that you expect from a big endian or little endian byte order.

bool isBigEndian()
{
     short s = 1;

     // big Endian if MSB == 0
     return (*((char*)&s) == 0);
}

Another trick is to use an unsigned integer as a set data structure. However, it's limited to holding only 32 values. Usually this is enough, but sometimes it's not. In any event, here's the process that goes into it.

You can look at an unsigned integer as a 32-bit integer, where the ith bit (0-indexed) is set to one (1) if and only if it is within the set, and zero (0) otherwise. Therefore, to add something to a set, there is a trick to use:

          x |= (1<<(i));

This will get the ith bit for you and bitwise-OR it and store it in the variable x. Usually it can be used like this for computing set-type problems, like the TSP-related problems, permutation, backtracking problems, and the like. Of course, to remove the set, there is a similar trick:

         x &= ~(1<<(i));

This will flip all the bits to a one (1) except for the i-th bit and bitwise-AND it with x. Therefore, the only bits that are changed within x was the i-th bit, everything else stays the same. This technique is quite useful.

Tricky way to check if a string is a palindrome. It takes n/2 checks such that n is the length of the string in consideration. The algorithm to do so is to check the mirror image of the indices since they should be identical in a palindrome. (Front<->End) The code follows:

     int len = str.size();
     for (int i = 0; i < len/2; ++i) {
          if (str[i] != str[len-1-i]) {
               return false;
          }
     }
     return true;

Obtaining the offset of a data member from a structure. This is quite useful. The key to this idea is that it is based on the rule that if you ever take the address-of (&) operator on an element that is dereferenced, it does not evaluate what's being dereferenced. The code follows:

      typedef struct B {
           int x;
           char y;
      } B_t;
      typedef struct A {
           char a;
           int b;
           short c;
           B_t d;
           long long e;
      } A_t;
      To find the offset of member 'e' within
      type A_t, you need to know the padding infrastructure.
      This could get complicated, so this is a better way:

      unsigned int offset = (unsigned int)(&((A_t*)NULL)->e);

Because it does not evaluate the NULL dereferencing e, this just calculates where the variable e is within the A_t structure. This is quite useful in things such as the list-head problem, which will be shown in an upcoming article. And since NULL is actually ((void*)0), the starting address of the structure in this case would be zero (0), which is the reason why it would give us the actual offset of where 'e' is stored at.