CodinGame held the “Code a la Mode” coding competition in March 2019. The game is now available to play.
A bit of time has gone by since Fantastic Bits, but the lazy way is still working well – or, at least, well enough for me. I have indeed reached Gold in all multiplayer contests for the past two years and Legend twice, including a rather satisfying #44 rank at Code4Life.
However, ugliness has become an unfortunate trademark of my contest code. It systematically turns into an unmaintainable spaghetti mess in the last few days of the competition, as I randomly try out hastily written last-minute hacks in a hopeless attempt to make my way back up the leaderboard.
For Code a la Mode, though, I decided to try my best to avoid that. I ended up with what is definitely my best contest entry ever on CodinGame, both from a design and implementation perspective.
Let’s see how it went.
Wood 3: Basic Customer Service
My usual method for passing Wood leagues is to code first and ask questions later. I quickly implement each new rule in the most direct way I can think of. For Wood 3, this means:
- A simple structure for the orders in order to bundle the content and reward, plus I/O operators to ease the reading of inputs and outputting debug information. I represented the content as a sorted array of strings; this helps both the readability when debugging and another part of the algorithm (more about that below).
- X/Y pairs of global variables for the locations of resources, initialized as the kitchen map is read – I’m not even storing the kitchen map at all!
- Sorting the customer by reward to select the one with the lowest reward: Since the obvious choice would be to select the highest one, picking a less obvious order reduces the risk of getting in the partner’s way.
- Comparing my list of current items against the selected order and determining my next target as the first missing item of the order. Since the lists of items are ordered at Step #1, this can be accomplished by just comparing the lists item by item and stopping as soon as items don’t match anymore. If I have the full set, then my next target will be the window.
- Finally, a single USE command with the location of the next target, which automatically gets interpreted as a MOVE if I’m not next to the target.
Wood 2: Chop, Chop, Chop
I handled the chopped strawberries very simply:
- New X/Y variables for the locations of the chopping board and the strawberries crate.
- I modified the order of contents at Step #1 to put the chopped strawberries first in the list. This way, they always come first when I prepare a new order, which ensures I will always have my hands free, so I don’t bother putting items on tables.
- I added a special case at Step #4 when I need chopped strawberries, to go to the strawberries or chopping board, depending on what I’m carrying at the time.
Wood 1: They See Me Cooking
I handled the croissants exactly the same way as items in Step #4: I simply target either the dough or the oven, depending on my current item and the oven contents.
There is one single extra adjustment: Since preparing croissants and chopped strawberries both require empty hands and I still didn’t want to handle dropping and picking up dishes, I chose to ignore orders that contain both a croissant and chopped strawberries.
In the (relatively rare) case where all three orders require both, I will just wait until one of the orders is completed by my partner and replaced with a new one. Yes, it’s grossly suboptimal, but remember that the philosophy here is to have something that will work in most cases, not every case: It’s OK to accept that there are complex situations you simply can’t or won’t handle – at least for now.
At this point, I also started to scan the kitchen for chopped strawberries or croissants that my partner might have laid down, and included those in Step #4. Still quite simple: new X/Y pairs for each type of item, keeping the one closest to me when reading the tables information.
Lazy tip here: In the vast majority of cases, there won’t be chopped strawberries all over the place, so you can allow yourself some degree of inaccuracy for the implementation of “closest.” Initially, I even just chose the first item I could find, and this was more than enough to get me to Bronze league! If you’re reading this before trying the game, hopefully, it will be the same for you.
(Special thanks to Razovsky for quickly coding a mad strawberry chopper for this screenshot and replay: This is a funny behavior that many of us accidentally coded during the contest, but I had lost all the replay links.)
Only in Bronze did I decided to use the closest item, according to the Manhattan distance (that was quicker to write). Only in the Gold league did I finally replace it with true flood-fill-based distance.
Bronze: Tart Attacks!
Bronze League brings us the dreaded blueberry tarts. In fact, they are not such a big deal to handle, since they can be processed just like the other two “complex” items. There are more steps, but it’s still a simple chain that you can run in a single go if you start with empty hands: dough → chopping board → blueberries → oven. So, for a first draft I just added that logic at Step #4 and adjusted the order selection once more to only select orders that contain at most one complex item.
Of course, this can only get you so far. At some point, you do need to start handling partial dishes, storing food on tables and picking it up later. I added yet another pair of X/Y variables for the location of the closest available table and tracking of whatever I would store on it, so I could check that it had not been taken by my partner.
That seemed simple enough to me at the time, but soon required adding extra stuff in Step #4 in order to drop, pick up or skip the contents of the storage table, also ensuring that I had a dish before picking up a second item – which I might already have left on the storage table…you can see where this is going.
Long story short, I eventually managed to get it to work, and it was enough to rank #60 after the promotion to Silver, but there were a lot of situations where the behavior of my AI was clearly inefficient, and by then my code had turned into an ugly mess of spaghetti and duplicated code.
It was time to start thinking (yes, sometimes, you do have to) and perform what one of my colleagues calls a triple-R: Reboot, Reformat, Reinstall. Yes, I dropped my code entirely and started over (yes, sometimes you do have to do that as well).
Make Me One with Everything
What helped me clean up my code and algorithm was the realization of something fundamental that had quite escaped me until then: Virtually everything in the game can be represented and handled the same way.
There is no difference between the initial infinite stash of strawberries and strawberries dropped on a table. A semi-complete order on a dish or the chopping board are not special things, they’re just resources that I’m going to use at some point in the game, so there is no reason to represent or handle them differently.
Everything can be thought of as a set of elements: all appliances, raw ingredients, complex ingredients in intermediate and finished states, customer orders, partially-completed dishes, stuff that you’re holding, stuff that’s in the oven, stuff that’s on tables…
Every. Single. Thing.
Raw ingredients and appliances are sets with a single element; customer orders and partial dishes are sets with several elements. A free table is an empty set, and so on…
With this representation:
- Standard operations on sets can be used to determine elements present in one set (a customer order) and missing from another set (a player’s item), or when a set (the contents of a table) contains elements from another set (elements missing from an order), and so on…
- The kitchen can be represented as a simple 11×7 array of such sets, which is small and easy to iterate over.
- No need to keep X/Y pairs of coordinates for anything anymore; I just scan the entire array until I find what I want.
The only special case here is the oven: If it contains a baked croissant or tart, then I don’t represent it as the oven, but as whatever it contains, just as if it were a table. This way it’s much easier to include the contents in my pickup code, but it effectively removes the oven from my map. However, if I have to bake something, I still need to be able to go to the oven, so I did keep one X/Y pair with the location of the oven for that case.
At this point, let me make a couple of important side notes about implementation:
- There is a distinction between the idea and the implementation of the idea. Even if I’m using the concept of set here, it does not mean it has to be implemented as an actual set structure if the language I’m using provides it. It might be arrays of strings with some helper functions, integer enums, bitfields…I used a classic pattern of power-of-2 enums that each occupy a single bit inside one integer (Empty = 0, Dish = 1, Blueberries = 2, Ice Cream = 4, Strawberries = 8…) which can be combined and manipulated using bitwise operators.
- There is also a distinction between simple and straightforward. Typically, while the idea of power-of-2 enums I used is simple, bitwise operators might not be straightforward for beginners. The bottom line is that you want to keep your ideas simple and your implementation straightforward. It’s up to you to find your path there, according to your current knowledge and habits – which will evolve over time. However, the more direct your implementation is, the more important it is to write wrapper functions with clear semantics. If your logic for “what items am I missing for this order” takes 30 lines of code with nested loops and 7 ifs in your implementation, that’s OK. But you can’t afford to keep it inlined in the middle of the rest of the code. It’s still OK to write it inlined when you start out, but you do have to factorize it out to some “getMissingItems()” function, before it becomes so embedded with the rest that it’s not possible to move it anymore.
With that in mind, the high-level game logic for one turn becomes as simple as:
- From the initial kitchen map, the tables information and the oven information, generate an 11×7 array of “sets” (actually an array of integers in my implementation).
- Select an order to process – I’m still going with my initial idea of always going for the lowest-scoring one.
- Determine a target set of items:
- If the selected order matches exactly what I have in hand, then I’m ready for delivery and my target set is “Window.”
- If the selected order can be assembled from what I have in hand plus what is available in the kitchen, I can determine the order items missing from my hand, scan the map and target the set with the most missing items – still ensuring that I have a dish before I pick up a second item. That set can be anything, including a partial dish. Yes, this automagically handles picking up the stored dishes that had messed up my Silver code so much!
- Otherwise, prepare the missing items. This is pretty much the same as in my Bronze code, implementing the chopped strawberries/croissant/tart chains. The table drop, when necessary, is achieved by simply targeting an empty set – and the dropped item will then become just another set of items ready for pickup at Step 3b.
- Go to the closest location that contains the target set, still using only the USE command – no fancy optimization of movement.
Because the ideas here are simple and I chose a straightforward implementation (for me), this turned out to be very quick and easy to write from scratch – about two hours to set up the core infrastructure and one more to add the extra features – with very few bugs along the way. Adding tarts literally took me no more than three minutes and a dozen lines of code… The results were amazing: I reached #20 by the time the Gold league opened!
Small Details Go Legend
In Gold, I only added a few extra features, still very simple and obvious:
- Selecting the target order on every turn means that when the list of orders changed, my target might change as well. I would then drop whatever I was holding to take care of the other order, even if I was on my way to delivery. To fix this, I simply kept track of the target order, only selecting a new one if the target disappeared from the list of customer orders.
- Lots of replays showed wasted time in front of the oven – and burned food inside it. So, if I’m standing next to the oven and it contains a croissant or tart, then I take it out – no matter what else I’m doing – setting my own item on a table beforehand if necessary.
- I also changed the order selection to the highest-scoring one with the fewest missing items.
The order tracking and oven save went a long way towards preserving a very high Gold ranking. Although I wasn’t high enough to be part of the first Legend promotion, I was still very close to the boss and got promoted just a few hours after the opening.
After that, I did try some extra features, such as using the baking time to start assembling an order, or setting my items close to my next target rather than close to my current location. Although I felt those behaviors made sense, somehow they never yielded the results I was hoping for, once added to the arena.
Admittedly, by that time the competition had improved and most people in Legend league were more or less tied. It was sometimes hard to really see whether a change was an improvement – in fact, I often needed to spam-push the same code many times in order to get a good start and rise quickly out of the depths of the league.
In the end, I just shelved those changes for deeper exploration when the game is released as a multiplayer game. After minor adjustments to the existing features, I finally stabilized at #64 at the end of the contest.
While #64 is definitely not a top-tier rank, I’m still very satisfied with it, considering how simple my code is – a single idea for the data representation, which makes everything else simple to imagine and easy to implement. For once, I was able to keep the code very clean and quite compact as well – less than 500 lines of code, no spaghetti, no ugly warts or quick fixes.
As one of my teachers said to me 20 years ago or so, any fool can build something complex, but it takes genius to come up with something simple and beautiful. I don’t see myself as a genius, but now I think I understand what he meant.
I had a lot of fun in this contest, and it certainly got me to refine my simplicity skills a bit further. Thanks a lot to csj and Matteh for this opportunity!