Sunday, March 14, 2010

Open facebull

I was asked to share my solution for my facebull, and I finally did (github).

I'm not particularly proud of the code, since it's rather messy. I spent about 5 days thinking about the algorithm, and I coded it in about 30 min and submitted it, and to my surprise it passed.

I am aware that this is probably the most challenging Facebook puzzle, which is why I was initially reluctant to share the solution. In the end, though, I decided that none of this really matters anyway. It's just 250 lines of poorly written Java code that when compiled and ran against some input produces the expected output, and some bot decides that it's good enough.

So there.
Update 03/18: I plan to rewrite this using immutable sets instead of java.util.BitSet; I was worried that the algorithm is way too slow and thought I'd need to squeeze every bit of performance to pass the bot. I think this optimization is premature.

Fact: the original passing solution had 100 more lines of various preprocessing heuristics; they turned out to be unnecessary, since the current version still passes.

9 comments:

  1. Does your java solution steel passes the Facebook robot?
    I have a much faster solution than yours that doesn't pass the robot.

    ReplyDelete
  2. Yup, just resubmitted it today and it still passes.

    Check out Martin-Louis Bright's github; he was the one who requested to see the code, to get some idea about my algorithm (which frankly isn't all that great, but hey, it passes the bot).

    http://github.com/mlbright/puzzles/tree/master/facebull/

    ReplyDelete
  3. Sorry I had a little bug that came out after harder testing. Got 48ms from the robot :D

    ReplyDelete
  4. I've solved all the visible puzzles... can you give me a hint where I can find the secret ones?

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. You solution can't process the following test case
    correctly:

    M1 C1 C2 2147483647
    M2 C2 C3 2147483647
    M3 C3 C4 2147483647
    M4 C4 C5 2147483647
    M5 C5 C1 2147483647
    M6 C4 C3 1
    M7 C3 C2 10
    M8 C2 C1 100
    M9 C1 C5 1000
    M10 C1 C4 10000
    M11 C5 C4 2147483647
    M12 C5 C3 100000

    The answer should be:

    111111
    6 7 8 9 10 12

    Your solution gives:

    -2147472553
    1 2 3 4 5 8 9 10

    ReplyDelete