No, the contest is over, you have to wait for the Code Of the Rings PUZZLE
When will the puzzle be released? Also, would it be pretty similar to the contest in terms of format?
I don’t really bothered to note (nothing game breaking if that is the question …). The base code was a greedy algorithm (there was a lot of that in the first few minutes/hours of the contest) and was based upon the “all space” starting position.
So the “evolution” tried to invent a loop that would minimise the number of instruction of that particular greedy algorithm over the set of test codes, by properly setting up the “all space” to something more efficient.
It did provide (a small) boost to performance. But it was mostly fascinating to look at my computer trying to programs it’s own way to self awarness.
Unfortunately I couldn’t get myself to include loops in my algorithm. Writing code-producing code is too mind-bending an experience for me to wrap my head around. 
On the other hand I managed to get 5886 instructions without any loop. In regard to your original question that seems like a pretty good score, so I will explain my algorithm (it’s a greedy one):
At first it did only use the rune it was initially sitting on (rune 0). The initial algorithm was: for each char in the output string, loop the rune around to get the desired character then hit the “.” instruction. So if I wanted to print ADZ my code would be +.+++.-----.
Not really optimized is it. So the next thing I did was this: before looping the rune around to get the desired char, first find out if there is another rune which is closer to the desired char and find the most optimized solution. So the algorithm was now: for each char, move Bilbo around to the desired rune, then modify that rune, then output the character.
In regards to printing ADZ the code would now look more like +.+++.>-. which is more optimized. Note that I left the first rune sitting at D meaning that afterwards if I wanted to print a character alphabetically close to D I’d go back to that rune to do so.
In practice, I solved the last test (long spell) in around 1400 instructions. My character used in the end 10 consecutive stones to print out the message.
One interesting thing to think about is that I managed to bring my score down about a hundred instructions by favoring far away stones in my moving process. For example there are two optimized solutions for printing AZ: +.–. or +.>-. They both use the same number of instructions but I found out the second approach was better in the long run because it used more stones to print out its message, which in turn gives us more options to choose from in moving to another stone.
5 Likes
(I am guessing he hacked into the system and manipulated the leaderboard)
Actually it’s not a true.
There was a bug in test cases input handler. The “][” output could pass all tests.
1 Like
Hi,
Thanks CvxFous, an extremely enjoyable challenge! I feel like the format along with the time constraint was chosen really well.
I scored 23rd with 3700 score. Although it is good, I am still a little disappointed with myself, the guys in the first few positions were very clearly on a different level of generation and optimisation. I used greedy techniques, which was probably what separated the first few places from the rest. However, I can’t even begin to think how to globally optimize for a problem like this
My main breakthroughs were because of the brainfuck algorithms page and this other one which talks about language optimization when compiling from brainfuck to C. The first one had some really neat tricks like [-] to 0 a cell, [>] to move to the rightmost empty cell, etc. The second one gave me the idea to try and post-process my code (which is not really relevant to the contents of the code, although the contents are still interesting).
The biggest breakthrough was definitely the post-processing. I.e. generating some functional code first, then searching for recurring patterns, replacing them with loops and checking the instruction count gain/loss. This allowed me to go from ~6k instructions to 3,9k. Given my algorithm was greedy and post-processing was such a success, any pre-processing optimizations actually ended up giving me worse results.
I tried:
- Analysing letter frequency and trying to keep the most frequent ones on the memory, unless the alternative had really poor score
- Doing pre-seeding on the memory to have random letters from the start, to allow reaching others easier
- Using
[-]--and[>]type fastmoves - Others, which I forget
Although before post-processing these yielded improved code-lengths, it proved that overall they achieved solutions which optimized worse with loops.
Yeah, anyway, great fun. Thanks for the challenge!
3 Likes
I quickly done a dummy algo in 9 lines to get 100% but I got about 11000 instructions.
I done an other algo based on Huffman compression to get the most used letters and cut the tree for the best ratio dictionary/calculation registers. I got about 7700 instructions.
I haven’t spent much time on the good challenge and had no time to test loops.
24h challenge is an excellent format. I love it ! 
3 Likes
hi,
I have a problem.
i can’t get my position.
they is a “calcul en cour”.
OK we will investigate. Should be fixed today.
I did mostly like J_campion. First with only one stone (more than 10000 instructions), than I tried choosing the rune that miimized the next step. I got to 6001 instructions.
And then I added loops. Mainly, I looked at the next occurence of the current letter, and tried to see if it was a recurring pattern. And then I tried to find how many times it was occurring. It was a naive algorithme, since I could find the good pattern in FUMFUMFUM, but for example for BAOBABBAOBABBAOBAB, it would test BAO, AOB and finaly OBABBA, which would have worked.
I also tested that the states of the runes and the initial position were the same before and after the second occurence.
The instructions I got where the one for the first occurence, then setting the counter rune, then looping the instructions for the second occurence. Of course, I checked if it was shorter than doing the same thing without a loop.
I got around 4250 instructions this way.
After that, I optimized a bit, by only setting the runes for the state before the loop, than doing one more turn of the loop, to do all the occurrences inside the loop.
I got around 4020 instructions
And just 10min before the end, I added a small optimization because noticed that any ascending chain, like RSTUVWXYZ could be produced by [.+], and the same thing for descending chains containing A.
That’s how I got under 4000 instructions.
5 Likes
Hi everyone, I started the challenge using a greedy strategy. I knew that as an optimization challenge DP would be a better solution but I didn’t figure out the recursion formula at the beginning. So my greedy strategy gave me about 6100 without using loops; and then about 59xx when I added loops.
At this level I decided to rewrite 80% of the code and use DP. My strategy was to calculate the best cost of spelling a letter in every position ( 0 to 30 ) based best costs of the previous letter. This gives me 5800 without loops. Then when I added loops ( for one and two letters only, I couldn’t go further ) I got my final score which is 5496 
Finally, I have really enjoyed this challenge because I like optimization problems
2 Likes
What is DP ?
Dynamic programming. No, it’s not dirty.
1 Like
Hi ! Here are some points explaining my solution 
I spent an hour or two thinking about what kind of algorithm I should use. The approach I choosed is closed to dynamic programming.
First I wrote several functions to travel and change letters using <,>,[<],[>] and +,-,[-],[+]
Then the main idea of my solution is to fill an array of size N+1 (where N is the number of character in the string to displayed). In cell number k (0 <= k <= N), I keep the list of the S bests solutions I have been able to produce and that display the first k characters of the string (in my final submission S = 3).
for k from 0 to N-1
for each solution "act" in dyn[k]
use a greedy algorithm to extend solution "act"
I added different greedy heuristics progressively.
-
Try every possible destination, change the letter on the stone and display it. (~5700 points)
-
Find an increasing sequence (ex: UVWXY, IFECA or BBBBB) and display it using a loop like “+>++[<.+>+]” (~5000 points)
-
Find an increasing sequence with patterns of size 2 (ex: A B C D, UAVBWCXDYEZF, …) and display it using a loop like “+>->++[<<.+>.->+]” (~4700 points)
-
Store a word (of size <= 27) and display it several times. If we run “[>>[.>]<[<]<-]” starting from “C_WORD_” we can print WORDWORDWORD. (~3600 points)
-
A more general loop: "[<_______>+] " with some restrictions on _____ : (~3400 points)
- make sure the counter is never changed by _____
- the starting and ending state must be the same when running _____
-
Run “++++++++++++[>-]” at the beginning to turn every space into an other letter.
(efficient with ‘N’) (~3300 points) -
Store two words (ex: “NOLEM_MORIA”) and display them using “>[.>]<[<]” or “<[.<]>[>]”. (~3200 points)
And finally I removed patterns like “<>”, “><”, “±”, “-+” to win something like 10 points, and tried several values for each constant.
I hope my explanations are clear enough =P
Simon
13 Likes
I have a two steps approach.
In the first step I try to find a good solution without loop (by using beam search), and in the second step I post-process the output of the first step by adding loops where I detect repeating patterns in the instructions.
The beam search algorithm is just a like the greedy algorithm except that, at each step, instead of keeping only one list of instruction, it keep a pool of the S best lists of instruction found (S, the size of the beam, goes from few hundreds to few thousands depending on the size of the target string).
The heuristic to check if a solution is better than another is just the number of instruction used (plus a tie breaker based on the position).
Since the same state can be reached by multiple list of instruction, the beam can be quickly filled with multiple list of instruction that will give the same result.
In order to avoid exploring those lists of instruction, I check if the state has already been reached, and prune the search if this is the case.
If I understand correctly SimonM used a similar approach but with a smaller beam and better state transitions (I don’t have those state transitions : [<],[>],[-],[+]).
For the second step, I find the repeating pattern that will the reduce the number of instruction by the biggest amount, and I continue this as long as I found improvement.
Finding the best repeating is a brute force (every start position in the instruction list in the instructions * every possible pattern length * every number of repetition), and a check that the pattern have the same starting and ending positions in the rune list.
In order to replace the repeating pattern by a loop I find the closest rune set to SPACE that is not modified by the pattern and use it has a counter.
for example, if a pattern P is repeated 2 times and if a there a free rune available just as the right of the current position, I use this sequence of instruction:
>++[< P >-]< the counter is set to B and is reduced by 1 each iteration.
if a pattern P is repeated 20 times :
>+[< P >++++]< the counter is set to A and is incremented by 4 each iteration.
The optimal values of the initialisation and the increment of the counter for each number of iteration can be found easily by brute force.
There a lot of room for improvement :
- using state transition like [<],[>],[-],[+]
- using a smarter heuristic for the beam search (for example it doesn’t take into account the fact that loop will be added afterwards, neither it takes into account the fact that it’s often good to have multiple runes set to (or close to) letters that will be used after in the string)
- handling of special “easy” cases (many public cases could be solved with an almost hard-coded solution, I guess it’s the same for hidden test cases)
- using runes set to something else than SPACE as counters for loops
I really like this problem and the 24h optimisation problem format, I hope that there will be others like this ones !
6 Likes
Thank you very much to both of you for those explanations. I had never heard of “beam search”. So i guess reading your articles really improved my knowledge.
Very good contest, once again ty all
3 Likes