Saturday, January 23, 2010

Facebook puzzles

Some notes about how to pass the current Facebook puzzles with the least amount of effort. I don't try to be verbose, but needless to say, SPOILERS AHEAD.

#7 hoppity: It's a FizzBuzz test, basically.
#3 meepmeep: I have absolutely no idea why this is even here. Actually, now that I think about it... Nah, even if the input file (that you're instructed to open but then ignore) contains some usable information, there's no easy way to retrieve it.
#20 liarliar: Straightforward UF.
#17 breathalyzer: The O(nm) L-d algorithm is fine. The dictionary is known in advance, but there's no need to preprocess it. No need for a fancy data structure to represent it either.
#15 gattaca: Straightforward wIS.
#13 simonsays: The hardest part is setting up the Thrift framework.
#12 dancebattle: Despite the warning, nothing insightful is necessary. Go ahead, code that obvious brute force algorithm and send it. It'll pass.
#6 smallworld: Use double precision (remember that Infinity * 0 is not 0, etc). No need to batch the k-NN retrieval.
#2 usrbincrash: Straightforward is fine.
#18 rushhour: I think this puzzle is broken, actually. Funny story: I crashed the server once. / Dear god! This puzzle is even more broken than I initially thought!
#14 battleship: Just create 2 dumb clients and have them play against each other.
#10 fridgemadness: Straightforward G-S implementation is fine.
#8 peaktraffic: Straightforward B-K implementation is fine.
#5 swarm: A layer of obnoxiously concocted math obfuscates a straightforward combinatorial problem.
#19 dinoisland: (not yet) This requires lots of investment, and honestly, I'm not sure if it's worth it. I'm not even sure if they guarantee that sufficient intelligence yields survivability. Who knows what lives on that island right now. This one time I hatched and someone ate me right away.
#11 sophie: Brute force is fine, apparently... Nope, it just got harder...
#1 facebull: (not yet) This is the Minimum Spanning Strong Subdigraph problem. <- No it's not! Anyway, somewhat surprised that I solved it, but I did. It's a computationally intractable problem, but my suggestion is to give it a try anyway.
"Hidden" ones I've found:

[hidden#1]: Noisy, buggy, this puzzle is frustrating as hell, but solvable. Use the 162x348 version. You'll get the congratulatory confirmation e-mail, but I don't think the app lets you publish that you've solved it.

[hidden#2]: I had to have someone point me in the right direction to find it, but this was a VERY satisfying puzzle.
Some prime numbers I've seen:

- The e-mail address: {0xFACEB00C>>2 in decimal} = 1051962371 is prime.
- From swarm: 654195331 = 0x26FE3A83 is prime.
- From [hidden#1]: even though the metric makes no sense for this problem, the confirmation e-mail reports that my longest running time is 73.127 ms. 73127 is prime. // Others have reported receiving different, non-prime numbers.

21 comments:

  1. I don't think Facebull is exactly the MSSS problem. MSSS is finding the minimum number of edges (arcs) that produce a strong spanning sub-digraph. Facebull is finding the cheapest set of edges that produce a strong spanning sub-digraph. The optimal set for Facebull may have more edges than the MSSS solution on the same graph. I solved sophie, liarliar, breathalyzer, gattaca, dancebattle, simonsays, smallworld, fridgemadness, rushhour (noticed that you broke it! nice!), but I have not solved Facebull yet...

    ReplyDelete
  2. Ah yes, you are correct that MSSS only minimizes the number of edges, not the sum of their weights.

    So MSSS is reducible to facebull by assigning unit weights. I guess facebull is harder than I thought.

    I've since managed to solve it, though.

    ReplyDelete
  3. What language did you code in to solve it? I've been scratching my head on this for a while, and I like to code in python. However, short of using math and algorithms that are beyond me at the moment, I think I need to use C/C++ or Java to be able to craft a solution that passes the bot.

    ReplyDelete
  4. I used Java; 5 seconds was its longest run time. The algorithm itself is nothing sophisticated. In fact, I'd say it's quite a mess.

    I don't know much about Python to guess how a straight port would perform.

    ReplyDelete
  5. I'm guessing that if you ported it to python, it would not pass the robot. While I love python, Java blows it away in the performance department.

    ReplyDelete
  6. Have you solved swarm yet? If you haven't, I suggest you try again. Concentrate on understanding the formula under the given parameters.

    ReplyDelete
  7. I have not solved it, but (SPOILER ALERT) there's a solution on the web that I have translated to python. Facebull is orders of magnitude more difficult than swarm.

    ReplyDelete
  8. That is, there's a solution to swarm, not facebull. Help a brother out with facebull?

    ReplyDelete
  9. I don't know what to say, man. Like I said, I didn't think my algorithm would be fast enough, but it apparently was. Just concentrate on being correct first, and then find out if it's fast enough later.

    I spent maybe 5 days thinking hard about the problem. I eventually code it in about 30 mins and just hoped for the best. I passed.

    ReplyDelete
  10. Cool. Did you do this recently, i.e. since last year (2009) when they added at least 1 test case with a very huge sparse graph? Also, how would you rate the difficulty of your algorithm: i.e. is it accessible to someone who has solved sophie, and most of the other FB puzzles?

    ReplyDelete
  11. I'm not sure how you know so much about the nature of the test cases, but according to the app, I first solved it on Jan 29th, 2010, 03:47:11 AM.

    The algorithm in concept should be quite accessible. No advanced maths or anything, it's just basic parts you've seen and used before glued together. The code is very messy though. Maybe I can rewrite it better, but I'm into other things now.

    ReplyDelete
  12. Excellent, thanks for your advice!

    ReplyDelete
  13. Hey, can you tell me which algorithm to use for Gattca, refrigerator madness and also can any of these solved in BFS method?

    mail me at lmsumanth@gmail.com

    ReplyDelete
  14. Go to the library and get a few good introductory books on algorithms. Skim through the Table of Contents. gattaca is wIS. fridgemadness is SMP.

    ReplyDelete
  15. what do you mean "hidden" one here?

    ReplyDelete
  16. Read what I wrote: "You'll get the congratulatory confirmation e-mail, but I don't think the app lets you publish that you've solved it."

    At least one puzzle isn't officially listed. There may be others.

    ReplyDelete
  17. For #3meepmeep, has anyone tried to submit a program that "calls home" and returns the actual contents of the file? I know it's probably nothing, but I'm damn curious...

    ReplyDelete
  18. Would you mind expanding a little on the LiarLiar help? I've never attempted any mathematical/programming problem solving in the past and I'm at a loss as to how to start :(

    Any links to newbie solving sites/pages would be much appreciated.

    ReplyDelete
  19. To solve liarliar, it helps if you've previously had experience with trees, forests, graphs, and recursion.

    The requirement isn't high, but if you've absolutely never done any of the above, then you'd want to do some reading and learning first.

    ReplyDelete
  20. Could be dancebattle solved by walking a binary tree?

    ReplyDelete
  21. I guess I shouldn't be asking this... But where are the hidden puzzles hidden? Any tips or hints?

    ReplyDelete