Facebook has shut down the robot for good. Since the links to the puzzle descriptions no longer work, this guide is of historical interest only.
The list of puzzles is here.
The robot has been down for months. No one knows when service will be restored.
In one of ten supported languages, write a program to be evaluated on a server maintained by Facebook (“the robot”). I have specific instructions for each language: C, C++, Erlang, Haskell, Java, OCaml, Perl, PHP, Python, Ruby.
You will find most of these puzzles difficult unless you have studied algorithms at the undergraduate level. Please do not discuss algorithms in the context of specific puzzles!
The Thrift-puzzle server has been down for months. No one knows when service will be restored.
In any language supported by Thrift, write a program to make your computer interact with the Thrift-puzzle server, which is maintained by Facebook. When you solve a puzzle, winGame() will return a string like simonsays(0123456789abcdef0123456789abcdef). Receive credit for your solution by sending an email to puzzles@fb.com whose subject is exactly that string. You are not required to attach your code, but the Puzzle Master would appreciate it. You should receive a reply within an hour or so.
To get started with Thrift, install the latest stable release and modify one of the clients in the tutorial directory to solve simonsays. Ignore the warnings about field keys not being specified.
Discover a secret keyword and send an email to 1051962371@fb.com whose subject is exactly that keyword. There are two puzzles with secret keywords. Clues can be found on the Puzzle Master page.
Read how to play.
Look in all of your email folders.
Try an account with a major free email provider.
Reduce the size of your submission. There is an undisclosed limit.
The robot runs make and ant and then checks the working directory for a regular file whose name is the puzzle keyword. “Could not be built/run” means that no such file exists. If such a file does exist but is not executable, the robot makes it executable.
Read how to play.
Send multiple attachments instead of an archive. If you must use subdirectories, ensure that your archive does not have an enclosing directory.
Reduce the build time for your submission. There is an undisclosed limit.
“Found some bugs” means that your program could be built (see above) but failed to write the unique correct output within the time allotted.
Read how to play.
Try my test cases.
Avoid deep recursion.
Make your program faster. Consider switching languages (the time limits stay the same) or algorithms.
Use meepmeep to ask the robot yes/no questions. To determine, for example, whether the robot has conio.h, send
#!/bin/sh
if [ -f /usr/include/conio.h ]; then printf 'Meep meep!\n'; fiThis submission is incorrect, so the robot does not have conio.h. Twenty questions is a slow but effective debugging strategy.
Is the puzzle server up?
Each puzzle has a different port. The host is always thriftpuzzle.facebook.com.
If registerClient or winGame times out, the puzzle server is malfunctioning.
If other methods time out, consult my puzzle-specific advice.
winGame returns a string with characters that are not printable 7-bit ASCIIReport system-wide problems on the Puzzle Master wall.
Use the discussions for all other conversations. Several experienced puzzlers participate on a regular basis.
Be detailed.
Ignore the standard error stream.
When there is a directory where the executable should be, make it the working directory and retry the build step.
Report whether an incorrect submission succeeds on the sample input.
Facebook has chosen to support only those languages in use at Facebook.
Per the Puzzle Master, the robot’s security configuration makes upgrading difficult.
Good algorithms will be successful in any of the supported languages.
-21779453@fb.com bounce?The correct interpretation of {0xFACEB00C>>2 in decimal}@fb.com is 1051962371@fb.com. The Puzzle Master intended that 0xFACEB00C evaluate to 4207849484, but in Java, which lacks unsigned types, 0xFACEB00C evaluates to -87117812. (-87117812 is the integer whose 32-bit signed two’s complement representation is identical to the 32-bit unsigned representation of 4207849484.) Since the Java standard defines >> to be an arithmetic right shift, the value of 0xFACEB00C>>2, which is -21779453, has undergone sign extension and is thus wrong.
Per the Puzzle Master, the robot sends infrequent/vague replies to prevent puzzlers from learning about its test cases and to discourage malicious users from examining its security configuration.
Yes; each submission requires its own email. Please be mindful of the fact that the robot is a shared resource.
Yes.
I, David Eisenstat, am a PhD candidate in the Computer Science Department at Brown University with no previous or current relationship to Facebook. The Puzzle Master works at Facebook and wishes to remain anonymous.
Tests not available yet.
hoppity_test.zip (instructions)
Tests not available yet.
meepmeep_test.zip (instructions)
If A accuses B, exactly one of A and B is a liar. You cannot tell which one, but you do not need to.
There are enough members that recursion depth may be an issue.
If you enjoy this puzzle, you may also enjoy the Knights and Knaves logic puzzles of Raymond Smullyan.
Tests not available yet.
liarliar_test.zip (instructions)
A compiled inner loop is particularly helpful for this puzzle.
Computing the minimum number of changes between two words quickly is not enough.
For some words, every acceptable word with the minimum number of changes starts with a different letter (e.g., korrect → correct).
“c” and “v” each require two changes.
twl06.txt is a Scrabble word list and does not contain “A” or “I”.
Tests not available yet.
breathalyzer_test.zip (instructions) (with thanks to Raluca Musăloiu-E.)
The DNA sequence is irrelevant.
Genes include their endpoints. The output for
3
AAA
2
0 1 1
1 2 1is
1Tests not available yet.
gattaca_test.zip (instructions)
Do not look for a subexponential-time algorithm. (mild spoiler)
The moves already taken may not be optimal.
“Optimal” means looking ahead to the end of the battle.
If m is even, you dance next. If m is odd, your opponent dances next. In both cases, report whether you will win.
One general optimization is enough.
Tests not available yet.
dancebattle_test.zip (instructions)
Tests not available yet.
smallworld_test.zip (instructions)
Tests not available yet.
usrbincrash_test.zip (instructions)
All roads are two-way.
If you take a road with .CurrentSpeed == 0, you still can finish, but your score will be Infinity.
There are some loopholes that lead to surprisingly low scores.
You must connect two clients with different email addresses. Instead of registerClient, the second client calls join with the gameID returned by registerClient in the first client.
If isMyTurn hangs in both clients, the most likely cause other than calling registerClient from both clients is that not all ten pieces were placed successfully. Check the return values of placePiece.
For all upper engineers A and all lower engineers b and c, either A prefers b to c, or A prefers c to b. Because of the tiebreakers, this is true even when all three have identical drink lists. Lower engineers always have strict preferences as well.
The primary objective is to ensure that for all upper engineers A and lower engineers b, at least one of the following statements is true:
Considering only those assignments that achieve the primary objective, the upper engineers have pairwise-distinct best obtainable partners. The secondary objective is to assign them those partners.
The correct assignment is unique. If an upper engineer A and a lower engineer b are supposed to be partners, and you assign a different lower engineer c to A, then there are two possibilities. If A prefers c to b, then for your assignment, there are an upper engineer D (who may be A) and a lower engineer e (who may be b or c) who prefer one another to their assigned partners. If A prefers b to c, then c is not the best obtainable partner of A.
Tests not available yet.
fridgemadness_test.zip (instructions)
Clusters may overlap but not contain one another.
Study the output format carefully.
For some reason, programs that use java.util.Scanner to read the robot’s inputs are judged incorrect. A confirmed workaround is to read the input line by line and split each line on "\t".
Tests not available yet.
peaktraffic_test.zip (instructions)
The primary objective is to maximize the sum of each base’s “expected” mineral gain. The secondary objective is not to use excessive force on any base. This is relevant because expected gains are rounded to the nearest mineral.
The alternate definition P(z, s) = 1/(1 + exp(63*s - 10 - 21*z)) is better suited to evaluation in floating-point arithmetic. Inspect some of its values.
Some inputs have multiple valid outputs. The forces on planet
2 6
1 1
2 1can gain 1 expected mineral from either base but not both, and the specification offers no unambiguous grounds on which to choose. The inputs here and at Facebook have unique outputs.
Tests not available yet.
One square north is row=-1, column=0. One square east is row=0, column=1.
Small herbivores can no longer eat large plants.
After a YouAreDeadException, hatch all of your unhatched eggs to guarantee receipt of a GameOverException.
Prolific species may find that some of their connections time out. This is an unavoidable consequence of network limitations.
The highest-scoring species are hive minds that overcome the limited vision of individual dinosaurs.
Use double-precision arithmetic.
You must start in the first named location.
seconds is not necessarily an integer.
In general, a direct route between two locations may not be the shortest.
For the sample input, the optimal path is front_door,in_cabinet,under_bed,behind_blinds. One way to calculate the expected time is
Pr(front_door) * 0
+ Pr(in_cabinet) * Distance(front_door, in_cabinet)
+ Pr(under_bed) * (Distance(front_door, in_cabinet)
+ Distance(in_cabinet, under_bed))
+ Pr(behind_blinds) * (Distance(front_door, in_cabinet)
+ Distance(in_cabinet, under_bed)
+ Distance(under_bed, behind_blinds))
=.2 * 0 +.3 * 2 +.4 * (2 + 7) +.1 * (2 + 7 + 9) = 6.00.Try inputs with disconnected locations, locations with probability zero, and disconnected locations with probability zero.
Tests not available yet.
sophie_test.zip (instructions)
facebull is by far the hardest puzzle. If you solve it, I congratulate you!
In the official inputs, there are many compounds, but most compounds are produced or consumed by only a few machines.
You must consider purchasing more machines than there are compounds.
Some inputs have multiple valid outputs. Given machines
M1 C1 C2 1
M2 C1 C2 1
M3 C2 C1 1either M1 or M2 may be combined with M3, and the specification offers no unambiguous grounds on which to choose. The inputs here and at Facebook have unique outputs.
Tests not available yet.
facebull_test.zip (instructions)
bagthebanner, a game of capture the flag with robots, was the first Thrift puzzle. It was incompatible with common firewall settings and offered no viable defensive strategies. dinoisland is its replacement.
Tests for some puzzles are not available yet.
On Windows, your Java program must use Unix-style line separators. Put the following lines at the beginning of your main method.
System.setProperty("line.separator", "\n");
System.setOut(new java.io.PrintStream(System.out));Set up a command line from which you can invoke a Java 6 runtime environment (java) and your program, which in this example is liarliar. Before your first test, you need to make the inputs.
$ cd /path/to/liarliar_test
$ java -Xmx1024M MakeInputsTest your program.
$ cd /path/to/your/liarliar/directory
$ java -cp /path/to/liarliar_test Test /path/to/liarliar_test liarliarTo save the output to a file results.txt, append >results.txt to the command. If you cannot invoke your program as the robot would, replace liarliar with a longer command such as java -Xmx1024M liarliar or php liarliar.
To conserve my bandwidth, the zip archives do not contain large outputs. I will not send them to you.
After the robot accepts your solution, please consider posting the summary printed by my test program in the Puzzle Master discussions.
build.xml. Edited the version history to use proper articles.@facebook.com to @fb.com.
© 2009–2011 David Eisenstat