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 to do on the platform. Always up for a fresh challenge, we made the whole Worldcup as an optimization game. :)
Obviously when we launch something new, we're also taking risks, since there is always a big part of 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).
Thanks to all 4452 participants that took part in this experiment. He hope you enjoyed the game despite the few problems that arose.
PODIUM & RANKINGS
2593 of you 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.
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.
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.
THE GAME
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 a nice and quick.
The real difficulty involved optimizing your 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.
- Initialisation: 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. Additionnaly, 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 yourselves thought up during the contest, via this Forum post: https://www.codingame.com/forum/t/code-of-the-rings-feedback-strategies/775/26
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: https://www.codingame.com/puzzles
Great contest, thanks! I wonder why there are so many C++ programmers... would it be because most of the participants were professional programmers?
ReplyDeleteMaybe that is what is still teached.
Delete