Facebook Puzzles

Anyone interested in programming should try the Facebook puzzles.

Using graph theory and dynamic programming, I can solve the puzzles in 22ms. In fact, the Facebull problem is NP-hard. The most interesting thing is that the famous travelling salesman problem (TSP) can be transformed to the Facebull problem. The most efficient method to solve the TSP is linear programming: D. Applegate, R. Bixby, V. Chvátal, W. Cook, and K. Helsgaun solved the TSP of 24,978 cities in Sweden. More details can be found on their website. One may wonder that if we can develop a method to solve the Facebull problem efficiently. However, it is hard to improve the linear programming techniques applied in the work of Applegate-Bixby-Chvátal-Cook: On the solution of Travelling Salesman Problems. From the mathematical point of view, the Facebull problem or the Travelling Salesman problem in linear programming is purely a linear algebra problem. It is still unknown if one can develop a polynomial time algorithm.

Dinosaur Island:

To solve this puzzle, one needs to understand how Thrift works. From my point of view, Thrift is a very powerful machinery. In fact, the engineers in Facebook are currently using Thrift in their projects. One may also needs to understand how multi-threaded client works. I would recommend Boost if anyone is interested. The last thing is that one needs to make a program with certain degree of AI (Artificial Intelligence) . I have to say that the AI in my program is really a naive one but it still managed to get a top score (approximately 13,000,000,000) for the herbivore dinosaurs.