Code of the Rings was our first ever 24-hour optimization contest. A new type of contest, a new set of challenges…
Some time ago we launched a survey, and optimization games came up as one of your favorite things on the platform. Always up for a fresh challenge, we created the whole coding challenge as an optimization game. 🙂
The Game: Code of The Rings
The goal was to help Bilbo escape the enchanted forest by sending him a sequence of instructions which would enable him to spell out a secret phrase with the help of magical runes. The expert CodinGamers quickly realized they dealing with the generation of Brainf**k code.
The size of the memory (= the forest) and the capacity of each memory cell (= a rune) were modified to make the game as fun as possible. We wanted to make the game interesting but still as accessible as possible, in such a way that writing a program to pass all tests would be nice and quick.
Optimizing the Code
The real difficulty involved optimizing the code. Several notable techniques were possible:
- Greedy: implement any technique one can think of with pen and paper to gain a few extra points (e.g. : move to a rune closer to the target letter rather than use the current tune, using [-] for setting a rune to zero, taking into account the circular nature of the memory (forest)…) and combine the results into the best solution.
- Breadth-first search: anticipate ones moves several turns in advance. e.g. test all the different ways to go from one letter to another in every situation.
- Heuristics: a method designed to find an approximation of the best solution without brute-forcing through every conceivable possibility.
- Initialization: initialize all the forests runes to M with ————-[<-]. This is handy if all the letters of the phrase are close to M. It also lets you use [<] and [>] to travel efficiently through the forest providing you set empty runes at key locations.
- Extra loop checks (): detect any repeating pattern within the phrase to minimize your output. Additionally, one can directly compress Brainf**k code by checking for patterns within the output.
Do not hesitate to tell us what tricks and strategies you came up with during the contest, via this forum post.
This challenge was also a way to introduce Brainf**k and the concept of a Turing Machine, which can look scary at first but opens up a whole new way of looking at programming.
We hope you enjoyed it as much as we did 🙂
You can now find the game labeled Bilbo’s Forest – Output length in the “Optimization” puzzle category.
Podium and Rankings
2593 players managed to find a place in the leaderboard, congrats to all of you!
The podium’s top 3 managed to reduce their output length to under an impressive 3500 characters: SimonM (France, C++, 3231 characters), eldidou (France, C++, 3394 characters), et geza (Hungary, C++, 3418 characters).
The average time passed on the contest is 18 hours, 33 minutes, and 15 seconds.
Thanks to all 4452 participants that took part in this experiment. We hope you enjoyed the game despite the few problems that arose.
Obviously, when we launch something new, we’re also taking risks, since there is always a big part of the unknown… Therefore, despite our best efforts, the contest was subject to a few hiccups. We apologize for these (namely server overload and incorrect ranking displayed).
Join our next online coding challenge “Back to the Code” on the 26th of September!