On April 13, 2012 the long awaited indie game Fez was finally released after 5 years of troublesome development. The goal of the game is to explore the environment, solve puzzles and collect cubes in order to unlock doors. The game is a 2d side-scroller living in a 3d environment. It is better viewed then explained:
FEZ LAUNCH TRAILER from POLYTRON on Vimeo.
The main goal is to collect the 32 golden cubes, but the more perseverant gamers can also try to collect 32 anti-cubes and more by solving much more difficult puzzles. The gaming community collaborated on the more difficult ones, but the last one had yet to be solved a few days after all the others had been solved.
The last puzzle
If you are already familiar with the story surrounding the last puzzle, jump to the next section.
The main theory for the last puzzle was that players had to stand at a very specific spot in the game and input a sequence of button presses. The standard sequences in the game are 8 inputs long and use up to 7 different buttons. Needless to say, no one wanted to try 2 097 152 different combinations, hence why players tried to make sense of some of the remaining mysteries in the game.
After a few days of unsuccessful attempts at breaking the code, the community realized that joining hands and brute-forcing the sequences together was a viable alternative. Fortunately, a player who had found the solution started dropping hints to dramatically reduce the set of possible solutions to a more manageable 78 125 combinations (he said the sequence was 7-inputs long and only used 5 inputs). Some people created a shared spreadsheet on Google Docs to split the work of trying the thousands of sequences, I went a different way.
Ars Technica wrote a good article about the story around the puzzle.
Rails, Heroku and Bootstrap: a success story
I was not too fond of the spreadsheet, not because it was a bad idea, but it just seemed a crude way of splitting the work even though it was practical and easy to set-up. On Tuesday evening (the 17th) I decided I would build a web application that would present visitors 10 sequences to try, then they could say whether one of the sequences worked or not. The user would then be presented 10 more sequences to try and so on until the solution was found.
To generate the sequences in an optimal order I used a De Bruijn sequence algorithm (thanks to Peter Taylor for telling me about it).
A De Bruijn sequence [...] is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in A appears as a sequence of consecutive characters exactly once.
This was perfect for the problem at hand since the sequences could be entered in any order, only the last 7 button presses were checked to see if the sequence was right.
In the image above, entering the first row in order then entering the last input of each subsequent rows will input all 4 sequences in 8 inputs instead of 20. For 10 sequences of 7 characters, that's 16 inputs instead of 70.
No more than a couple hours were needed to build a rudimentary version of the app. I unit tested the basic algorithms to make sure they behaved correctly and launched the app on heroku only a few hours after I had started working on it. I then shared the link (fez-monolith.heroku.com fez.mbillard.com) on a Gamefaqs thread where some players had gathered to work on the puzzle.
Trolls, false positives and false negatives
As soon as the app went live I was already working on the next version where people could confirm or deny sequences marked as being right. This turned out to be very important because trolls were already trying to negate the work of others by entering false information like marking untested sequences as invalid or marking invalid sequences as being the solution.
The fix for false positives was quite easy, people could just confirm or deny them, they would then disappear from the list of potential solutions. However, false negatives were harder to detect, the only way was to have more than one person try each sequence. Unfortunately for the community, the correct sequence was marked as invalid relatively early in the life of the app.
Causes of false negatives and why mysql != postgresql
Each false negative was the result of one of these 3 problems:
- trolls purposefully marking any sequence as being invalid
- users not inputting the sequences correctly
- my lack of experience with postgresql
To understand, take a look at the following code used to retrieve 10 supposedly consecutive sequences (which had been created in order in the database):
# Get a random set of X consecutive sequences
@sequences = Sequence.where("id >= ?", random_sequence_id).limit(nb_sequences)
What's wrong? There's no ordering in the retrieval of the sequences. On my development machine this wasn't a problem because I was using MySQL which was returning the sequences in the expected order. Postgresql on the other hand, which was required on Heroku, did not always return the sequences in order. This probably caused some users to input the sequences using the suggested method (the first sequence fully then only the last input of each following sequence). Someone reported the issue, but unfortunately I could only fix it much later in the day after my normal workday. This was entirely my fault for not knowing that a SQL query is non-deterministic without an order by clause.
Some stats and conclusion
Time between when the app went live to when the solution was found: ~18h
Number of contributors: more than 1300
Number of trolls: 123 people found a correct sequence, 20 of them found a lot more than one
Number of tested sequences: 66,227/78,125 (84.771%)
Number of false positives: 515
The solution had been marked as negative about 5 hours after the app went live either by someone trying to ruin the efforts of the others, because of an error from the player inputting the sequence or due to the ordering error in my code mentioned earlier.
Overall I am very satisfied with the project, it was shared by many on Twitter and on various forums as well as on Kotaku. I managed to set-up a very useful application in a matter of hours using Rails, Heroku and Bootstrap. The current website will remain live as I see no reason to take it down, I have put it in a frozen state to preserve its state at the time the sequence was found.
The code for the app is available on GitHub.
