Feel free to send your feedback or ask some help here!
Awezome puzzle !
1 Like
Great new format of competition =) It was unexpected but pleasant surprise =)
great contest, the loops were disturbing at first glance (or still are), but the fun was there
1 Like
Yes, this challenge was great. Very easy with a dumm algo, but far complex to improve
3 Likes
Oh, the test cases are working now in Firefox.
Very nice challenge, thanks CodingGame 
1 Like
I honestly did not like this competition by the end. I wrote a general search algorithm that achieved 5518 without using any loops, which is sort of what the instructions suggested, before trying to incorporate loops into the search. However looking at the test cases released it seems that the contest rewards writing optimal algorithms on case by case basis for very specific regular expressions rather than writing general algorithms. I believe this does not reward programming or algorithmic ability but rather time and effort spent fitting specific test cases. In a machine learning competition this is called overfitting on test data and is guarded against by using private validation data separate from what is used to compute the public leaderboard. I saw at least one mention in chat about an easy test case that could shave off a few hundred points, which is not what a healthy competition should be about.
15 Likes
Can someone please give a clue on how to use loops efficiently? Are we supposed to build suffix trees and search for repeated substrings? Brute force? Some kind of learning algorithm?
4 Likes
A basic use of loop is [+]. If you need to reset a rune to the space caracter, just do [+]. You can also use [>] or [<]. Bilbo will move and stop on the first space caracter.
You have more complex uses. For example, +[.+] will spell the alphabet. -[.-] will spell the reversed alphabet.
16 Likes
I understand how loops work. Right now, I believe to be somewhat around the same point as @quarkral above (i.e. my code is optimized to produce the smallest possible output without loops). Now, my question is: how can I properly “teach” my algorithm to benefit from loops?
Inserting minimalists loops as you suggest, @Magus, doesn’t seem to be really helpful. If you try it by hand, you understand quite fast that loops need to produce several letters at once to be efficient.
Should I test all possible combination of tokens inside the [...] (i.e. brute force) ?
There must be a way to speed up the process but i don’t know where i should start looking at.
1 Like
Here is how my code work :
Read loops
A read loop is a repetition of letters in the magic phrase. Like “AAAAAA” or “ABABABAB”. You have to use a rune as a counter to do that. For example you want to print “ABABABABAB” (6*AB). First you write A and B on two runes (so you do +>++). Then you need a counter for a 6 times loop, so you move on it and you set it (>++++++). Then you can do your loop in 4 parts : Move on the letters, read the letters, move on the counter, decrement it. ([<<.>.>-]). Final result : +>++>++++++[<<.>.>-]
Write loops
Write loops is when i have repetition in my final phrase. For example if you have to print the alphabet with spaces (A B C D E F G …). My code will first say something like +.>.<+.>.<+.>.<+. (and so on …). I detect the repetition of +.>.< and i do the same thing as the read loops. I use a rune as a counter.
15 Likes
Thanks @Magus. That looks like a good starting point.
Any advice on how to detect repetitions programmatically? Should I use regexp? Suffix trees?
Also, any suggestion on how to use the context to optimize further? In your first example, if the stone before A already contains “F”, it would be more efficient to put your loop counter on the left. I.e. >+>++<<[>.>.<<-]
It seems painfully complicated to detect cases like that.
To detect a loop i just look for every possible substring in a string (from the longest to the smallest). It is fast enought in javascript so i think you can do the same in any language.
For the optimization, my code can choose the “fastest” rune. For example if i need to say “F”, it will look for every runes and perform the code for using it. For example if bilbo is on an empty rune, the code will be “++++++”, if the rune on the left is already an “F”, the code will be “<”, it’s shorter so my code will use that rune.
2 Likes
I would really like if this problem would be split into two, one allowing for loop usage and the other not (similar to the multiple stages of the regular puzzles). As of now i only tried to tackle the loopless variant, but can’t get a good impression on how far I’ve come through consulting the leaderboard.
4 Likes
I started the puzzle very optimistically and did a breadth-first search into the next N characters, looking for the runes having states closer to the sentence I want to spell. I came up with the idea of using a lookup table to store the shortest distances going from one letter to another, taking into account going over zero and using [-] to reset the rune. At that time I did not see the loops part and did not use them. The result length was 5.9k which was disappointing for me.
Then I looked at the repetitions in the output Brainf**k code and put them into loops. I liked the generality of this approach. The restriction here is that the memory state has to remain intact after the loop finishes. I also searched, for every number of repetitions required, the optimal loop counter and increment/decrement setting. For example a 13x loop of (.) will be >+[<.>++], after this my score dropped to about 4.4k, which I believed could have been better.
Then I looked at the redundancies within the magic phrase itself, and hand-optimized on a case by case basis. I checked the average of the phrase and whether it is better to initialize the runes to M’s first, I checked the frequencies of words and letters and initialise the runes with them. Other cases like GAAVOOOLLU, BALROG and the two words case are very interesting and have been optimized individually. The validation cases turned out to have very similar performances as the test cases.
In order to get to this level I have completely taken the program offline and worked on it on my Visual Studio. I also created a versioning tool to keep track of the best outputs of each test case, and the version of the program used to achieve it. This helped me a lot to manage mistakes and keep track of breakthroughs.
Finally I cleaned up the code and gained a few characters by observing that ‘<>’, ‘±’, are redundant, and that any character other than a ‘.’ at the end is useless. Also a program starting with > or < can be trimmed. I am now ranked #17 with length 3378.
11 Likes
I am posting in case others have the same problem.
I wrote a trivial c++ program to solve Code of the Rings. It solves every test cases, every time I test it, but when I submit it, one, sometimes two of the validation tests fail, never the same. Sometime they all pass.
I thought that I somewhat screwed up with some uninitialized variables, even if the code is very simple. So I wrote an even simple perl program that solves all test cases but the last one. Same behavior, when I submit it, one of the test randomly fails.
Anyone experiencing the same situation ?
I have been able to reproduce an error while running the test cases:
Standard Error Stream:
/usr/bin/stdbuf: Resource temporarily unavailable
We got an issue that we fixed. So it should be ok now. Let me know if it still happens.
1 Like
I wrote Java program to solve Code of the rings. It solves every test cases, but when I submit it, it fails on 10 test.