There are performances that deserve to be highlighted, such as Maxime’s: he’s coded the whole Game of Drones battle in… Bash! Even if he did not end on top of the rankings, he proved it was possible. And to us, it was an impressive challenge to take. Congrats Maxime, we’re glad to have you in the community. And thanks for the review 😉
—
“I wanted to give some feedback about my experience on the Game of Drones challenge and CodinGame offered me this opportunity. Indeed, I decided that I could try to write the bot in Bash. Why? Because it’s fun and that’s what matters. I did not wanted to spend too much time on this contest and I knew I would need a substantial amount of time and thinking to be in the top10.
Bash is actually not a bad language and at first I thought I could do anything with it. I was wrong.
The first step is reading the input. So we need a way to store the position of the drones of all the players. However, Bash does not allow to do 2D-arrays. So I used indirect referencing to store the data. The idea is fairly simple, I use a first variable to build the name of my variable and then I can use ${!var} to read the value (you can do the same with eval). Since I’m using my variables mostly in calculations, I can actually directly do stuff like that: ((tab_${i}_${j} = other_tab_${i}_${j} + 1)).
With a few loops and using read, we can read and store all the input data. So let’s move on and talk about my first “prototype”, which was mainly a proof of concept. I won’t describe the algorithm, it was stupid. But this algorithm required to compute for each drone the closest zone (including those which belong to the opponents). Considering the number of players, zones and drones, this should not be a problem, right? Well, it depends on how you do a for-loop in Bash. Using seq, writing 2 nested for-loops that call a function that does an extra loop and add a few calculations is enough to use the 100ms available and time out. It’s 5 to 10 times faster to use a C-style for-loop or avoid to call seq in the nested loops by storing the result of $(seq N) into a variable. But at that time, I didn’t know that.
This first bot was good enough to beat the bots around 300-400 in the ranking. However, I got too many timeouts when there were too many players and drones. I was frustrated because my bot wasn’t even doing anything clever and yet it exceeded its available time. As a consequence, I decided to drop most of my code and to ignore the coordinates of the opponents’ drones. So what can we do without knowing the position of the opponents?
My second algorithm was the following:
– For each drone that is not moving:
– a counter is incremented (one per drone),
– if the drone spent too much time without moving and if it is in a zone that does not belong to me, go to the closest zone different than the current zone.
– For each drone that is moving:
– reset the counter to 0,
– keep moving until destination is reached.
That very simple algorithm got me approximatively at the 200th position on Sunday. It was less than 100 lines of code properly indented and with functions. But I noticed two issues with this algorithm:
– Sometimes, drones are leaving a zone to go to another zone that still does not belong to me and then go back to the previous zone.
– Drones that leave a zone and go to a zone that belongs to me are creating an over-protected zone instead of capturing others.
I wanted to deal with both problems at the same time before submitting my code. That was a mistake. But first, here are my ideas:
– Count how many times drones have left a zone and abandon zones left 3 times. Reset the counter to 0 each time I own the zone.
– Only leave zones to zones that does not belong to me unless I have no choice.
As I said, I should not have tried to fix the two problems at the same time. Why? Because there is not way to quantify the benefits on the ranking of each improvement. Actually, I lost 50 places in the ranking when I sent this code. I blamed the second improvement, dropped the code corresponding to the second improvement and then realized that there was a tiny bug in the code linked to the first improvement…
Anyway, I had another simple idea to deal with the second issue: avoid to send more than half my drones to the same zone. That only requires to count the number of drones I own in each zone and to add a condition in the function that returns the nearest zone. This last improvement led me in the top100 during the day before the end of the contest. I ended up at the 137th position.
I’m pretty sure I could have done better. For instance, by improving the speed of the loops and by avoiding functions, I think I could have taken the opponents’ drones into consideration. But as I said, I didn’t want to spend too much time on it. Plus, my personal objective was to be in the top200. I also like the fact that approximatively 100 lines of bash and a very simple algorithm was enough to be in the first quarter of the ranking.