Puzzle: Find Sophie

A friend told me the facebook puzzles page, so I started to work on some puzzles for fun. I started to work on "Find Sophie" which is at buffet level (hardest). This one is pretty interesting and it is not as hard as I thought.

http://www.facebook.com/careers/puzzles.php?puzzle_id=11

As usual I started with a recursive solution. The algorithm is simple:

1. starts with a node (first node) and find all the neighbors. Also calculate the current distance traveled so far.
2. for each neighbor, if it has not been visited yet, compute the current cost and call the recursive method with that node

// pseudo code

double minCost, curCost;

void backtrack (int node, double distSoFar)
{
    if (currentPath.size() == numberOfNodes) 
    {
        // this is a solution
        if (minCost > curCost) minCost = curCost;
        return;
    }

    foreach n in node's neighbors
    {
        if n has not been accessed
        {
            double p; // possibility
            double dist; // the distance to this neighbor
            curCost = curCost + (distSoFar + dist) * p;
 

// set the access flag of node n 

// backtrack
            backtrack(n, distSoFar + dist);

// restore curCost, accessflag of n
        }
    }
} 

So what is  the complexity of this puzzle? Obviously it is O(n!). For a 17 node example, it took several hours running on my server and still not finished. So how to improve it? Simple. Prune the search path.  A few simple techniques were used and all of a sudden, it took less than 1 second to run all the examples posted in this blog. http://www.facebook.com/topic.php?uid=15325934266&topic=7058

1. At any time, a minimal cost is maintained. In the search process, if we find the cost of the search is larger than the minimal cost, the current search can be terminated earlier
2. Which neighbor to try first? Simple math could show that if the node has higher probability and lower distance, that node should go first. So we can sort the neighbors for each node by "dist * (1-p)", where "dist" is the distance to current node and "p" is the probability of the current node. This is very important. The earlier we find a relative lower cost, the more search paths can be pruned.

Another critical point about this puzzle is not all nodes are connected, so we need to calculate a path for each pair of nodes (preferably the shortest path between each pair). This is a O(n3) operation and should be OK comparing to the O(n!) nature of the problem.


Puzzles are fun!

what's wrong with lakers?

I was glad that Lakers won 2010 playoff and hoped they can get the triple. But  now I am so mad that they played so badly this season - they trailed a lot from spurs; they are also behind heats, dallas and boston etc; they lost to almost every winning team.....

so why did it happen?

• they have won in the last two years, so right now they (both coaches and players) do not have strong desire as before. Kobe wants to win again, but how about his teammates?
• Bynum Bynum's injury has some impact. Now he is back and lakers is still losing
• Phil depends on the star players too much. Paul is exhausted. Bench players do not get enough play time and do not play to their expectations. Brown was good in the first a few games and now got lost. 
• Phil is not good at unearthing young talents.
• Worst of all: Kobe is OLD. He is only 32, but he already played 14 seasons more than Jordan did when he first retired in 98.  He has to realize that he can't lift this team alone and has to trust his teammates; otherwise Lakers has no chance to win this year. He's been my favorite player but I have to admit he is not in par with Jordan at all......

Lakers is always my favorite, so hopefully they can improve in the new year ;=)

Aloha!

Yes, we finally made the trip to Hawaii in Xmas!

We had been to Oahu for one week and had a lot of activities. During the first couple of days, it rained a lot, but overall the weather was perfect. It was between 70 and 80 all the time, but some person may feel a little bit humid. At the end of the trip, my daughter did not want to leave, nether did I ;=)

Fun places to visit:

• Waikiki (nice beaches, shopping and dining)
• Polynesian Cultural Center. 
• Hanauma beach.  Unfortunately I cut my foot while snorkeling ;=( and this was the only snorkeling I did in Oahu, so I did not see a lot of fishes
• Lanikai beach. The water is exceptionally clear and blue
• North shore beach. See turtle there
• Pearl Harbor (Arizona Memorial, Missouri etc). My wife and kids were not interested, so I went alone, but it was a nice visit.

Some photos we took there:
http://www.flickr.com/photos/9261638@N05/sets/72157625678938432/

cool new language features in visual c++ 10

In most of my careers, I worked in unix and linux platforms and recently I started to learn windows programming because I will join MSFT soon. I started to use Visual c++ express version and love it more and more as each day goes. No wonder Scott Meyers named visual c++ as the best tool in c++ history. No wonder a lot of programmers think c++ is visual c++.

I was impressed by some of new features introduced in vc++ 10. Those features are now only available in visual c++ (and maybe a few other compilers), but they are part of c++0x specification and should be available in other compilers soon. vc++ is just a pioneer effort among other vendors.  (Interesting enough, a lot of these new features were already implemented in Java.)

To list of some of the new features.

1. "lambda expressions support"

With "lambda expression" support, c++ programmers can now code unnamed functions/functors like Java.  When we use STL, we always need to define a lot of functors and it is always hard to manage them.  With lambda expression, programmers can always code functors and functions on the fly.  Also the code is now easier to understand. Check below sample to calculate the count of even numbers from a vector

 // use a functor
class Functor 
{
public:
       void operator() (int n) ......
private:
       int evenTotal_;

};


vector<int> vec;
Functor f;
foreach(vec.begin(), vec.end(), boost::bind (boost::ref(f), _1) );



// use lambda expression
int evenTotal =0;
foreach (vec.begin(), vec.end(), [&evenTotal](int n) 
     {
             if (n%2 ==0) evenTotal ++;
     }
);


BTW, boost has lambda expression support too.

2. Right value references and Move Constructors

I have not heard those concepts until recently I started to use vc++.  Move constructors are easy to understand. If the copy or assignment constructors need to allocate and de-allocate the memory, move constructors can be used to avoid the memory allocation and recycle. However this is only applicable when a right value is passed as the constructor parameter.  

See below example.  When we use move constructors, there is no need to allocate new memory in the copy constructor.

class MemoryBlock
{
public:

// Move copy constructor.
MemoryBlock(MemoryBlock&& other)
   : _data(NULL)
   , _length(0)
{
   std::cout << "In MemoryBlock(MemoryBlock&&). length = " 
             << other._length << ". Moving resource." << std::endl;

   // Copy the data pointer and its length from the 
   // source object.
   _data = other._data;
   _length = other._length;

   // Release the data pointer from the source object so that
   // the destructor does not free the memory multiple times.
   other._data = NULL;
   other._length = 0;
}

private:

    unsigned _length;

    char * _data;

};


When will the move constructor be used? A typical use case is in containers. In STL containers, a lot of "copy" operations are needed when adding new elements or resizing the containers, if "move" copy can be used, it will save a lot of memory allocation.


vector<MemoryBlock> vec;
vec.push_back (MemoryBlock());
vec.push_back (MemoryBlock());



String concatenation 

C++ does not have a Java StringBuffer/StringBuilder class, so the "+" String operator is actually not very efficient. Developers always use ostringstream or sprintf for string concatenation.  Now this is changed in vc++ 10 as the std::string now has the move constructors. Check below sample, there will be a temporary string object created for every "+" operator in other c++ env. In vc++ 10,  operator "+" can now append the string to another, which will decrease a lot of dynamic memory allocations.

std::string s = std::string("y") + "a" + "h" + "oo";

3. Parallel Library


This is very helpful as concurrent support is built in language itself. In my current projects, we implemented a complicated framework to run tasks in parallel using boost. What a pain......   Now we have this support from the language itself.  Details will be given later.