(Not so surprising given that those guys come from Facebook who maintain the nice Facebook puzzles).
The challenge is pretty nice and basically consists of counting all the ways to connect node 2 with node 3 while visiting all the 0 once.
2-0-0 1
|
0-0-0 1
|
0-0-0-3
As usual I start solving some trivial cases with brute force, but given most nodes have basically 4 neighbors, the complexity is in 0(4^n) so it's pretty clear we're not gonna go anywhere for their base case of n=52. (Remember that king of Babylon who found out he couldn't put 2^64 gold coins on a chessboard)
Hopefully with some observations and some basic solutions pruning to fail earlier, it's not that difficult to get a program which completes pretty fast:
g++ -o quora quora.cpp
time ./quora < test2.txt
301716
real 0m18.034s
user 0m17.993s
sys 0m0.016s
g++ -O3 -o quora quora.cpp
time ./quora < test2.txt
301716
real 0m2.444s
user 0m2.408s
sys 0m0.036s
Cool so with optimizations turned on I was able to get results similar to what they advertise (5 seconds on a computer from the past century).
Now it had been some time since I wanted to write some code in Google GO so I decided to port that solutions to GO code. That was pretty easy after understanding how they deal with pointer and arrays, as writing GO code is straightforward. By the way they have an awesome documentation, including Effective GO, on par with a book, really.
8g quora.go
8l quora.8
time ./8.out < test2.txt
301716
real 0m7.452s
user 0m7.452s
sys 0m0.000s
Just 3 times slower than the C++ solution which is pretty good. I don't think they have optimizations to turn on so far. Also they have GCCGO, another GO compiler written as a frontend for GCC, which is supposed to produce faster code. I wonder how it would perform there (for now it seems like a pain to install ;) )
Anybody interested you can find the go code here : https://github.com/frenchietechie/Puzzles/blob/master/quora/quora.go
Oh and by the way that got me interested into registering a Quora account, and the service is great. Really like it so far.
