Okay, the fun thing i did in the first hours, was to generate random code blocks, to optimize the environnement of the greedy algorithm. That was fun, looking at the auto-programming.
Although i wouldnāt bet my life that it was very efficient time wise. Iād probably have been much better to stick with more conventionnal methods.
I use to calculate the cost of use a new rune for the next char or use an existing rune with the lowest cost to show the needed character, just that the time was not helped me, yesterday I was not coding for the contest, and the time up catch me today. It will be interenting if someone(time was not my friend) use some combinatory to eficiently distribute the chars in the runes to reduce paths not necesarily starting in the first rune for the first char
The things that gave the largest improvements were adding loops (just like explained in the description), got me below 5k. Then later realizing that there were also increment/decrement sequences in the testcases, not just repetitive patterns. Implementing them via [<.+>-] loops got me below 4k.
Also I relatively early set up functionality which allowed me to evaluate an output sequence from within code and thus consider multiple alternatives on every step and take the best. That allowed to mix looking for repetitions with simple greedy optimizations and just take whatever gave the shortest answer.
Final score was 3927 - I couldnāt get any lower no matter what I tried. I probably would have needed to move away from the greedy approach, I did realize that some testcases indicated that it might be worthwhile to āplan aheadā.
Thanks Though I absolutely have no idea how a non-greedy (planning ahead) algorithm would look like, that can also consider multiple options like repetitions and increments.
Also while the base algorithms were greedy (doing a locally optimal choice) I believe it was made up a lot by considering multiple options. My final solutions were tracking 6 or so ālocallyā best solutions in each step and at the end chosing the best. That gave me plenty chance to pick a not-so-good option first but make up later by having a better reusable state in the runestones.
I re-ran my code without any use of loops, and it comes out to ~5600.
Loops were definitely a game changer that could move you from above 6000 instructions to well under 6000.
You could loop through:
Movements (eg. [>] to get to the next space)
Rune changing (eg. [-]++ to get to a B)
Post-processing the instructions, if you didnāt already catch something during the pre-processing. (eg. For Test Case 17, I had: +>-[<[.+]+.>+++++])
The most important part for me was definitely the validation script I wrote within the program. It allowed me to check with certainty that any post-processing that the program tried to doā¦ didnāt invalidate the solution.
MODO EDIT: donāt post that, everyone can copy it to have a good score, thatās not the point.
Edit: Itās true, my bad.
Anyway, i got 6001 instructions without loops, didnāt have time to optimizeā¦ I used the simple approach of calculating the number of instructions it would take to get to the letter from each ruin + to move to that ruin. i guess lots of people did the same since lots got the same score.
Thank you for this contest. It seems like you figured out a very fun way to introduce people to the BrainFuck language. BTW will you add this game to the optimization or other sections?
Yeah I immediately recognized it as brainfuck when I saw the problem.But it was reverse brainfuck i.e generating the source code for an given output.My brain literally got fucked while solving this
And yes one of the admins told me that it will be available in the Practice Games Section Tomorrow
WOW Intramonk the code snippets you just show are brilliant I would have never thought of using [>] or [-]++
Thats a spark of genius right there. I just simply used ++++++ & ------ for incrementing and decrementing from an given letter to another.But I make sure I used maximum of 13 of either + or - cause if the difference is greater than 13 I can loop around and go the other direction.And I thought this was the most optimal way
those kind of tricks are actually pretty common, check some tricks in brainfuck and youāll find those
Glad so much people like my game, itās the first game I made for codingame that has been published, more will come and I hope that youāll like them as well.
These are just a few questions to start off the discussion
Though I absolutely have no idea how a non-greedy (planning ahead) algorithm would look like, that can also consider multiple options like repetitions and increments.
I would have never thought of using
