Now that the contest is over lets discuss the strategies that you used
PS : I am not an an admin at CG
##A few question that you can answer
- Whats the lowest score you achieved without loops
- Which part was the toughest ?
- What was your greatest breakthrough ?
You can discuss about other things too These are just a few questions to start off the discussion
###Intresting things that Happened
- God came down for a few minutes in the form of Frisky and achieved a score of 32
(I am guessing he hacked into the system and manipulated the leaderboard)
###Update : Admins have told me not to paste links as anyone can Copy-Paste them and get a highscore.
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.
How many Instruction(score) did you achieve with than method ?
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”.
WOW 3927 Is an awesome score dude. Congrats.
Yeah Greedy Algorithms are easy to implement but dont usually give an optimal Answer
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.
Use the loops to do increment or decrement sequences ? I missed this good idea
It was a very pleasant contest, although. I liked it.
I used a loop for a staired-template for the ASCII codes.
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
- 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.
more codes i got from the chat :
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
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
- 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
Thanks for those code snippets they are like gold
For information,all the links will be dissapear when the puzzle will be available. No full code are allowed on the forum.
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.
Thanks for playing
Can I still submit solutions just to test my code and see my score?