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.

Does your java solution steel passes the Facebook robot?

ReplyDeleteI have a much faster solution than yours that doesn't pass the robot.

still*

ReplyDeleteYup, just resubmitted it today and it still passes.

ReplyDeleteCheck 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/

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

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

ReplyDeleteWhat the f??? ACT GAGA!!!

ReplyDeletePlease explain your solution

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteYou solution can't process the following test case

ReplyDeletecorrectly:

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