Code a la mode – Post Mortem (03/19/2019)

Contests > CodingGame

This post is a corrected version of my “Code A La Mode” Post-Mortem, originally posted here.


A great thanks to @csj and @Matteh, the creators, and to all of the CodinGame team!

What a contest guys! First cooperative game of the platform, and not the last I hope. Excepted some balance problems in the ranking, I really enjoyed it.

But now it’s over, and I finished #106 in legend with C++.

Here’s a little overview of what I’ve done.

The data structure

After reading the statement and seen the amount of inputs, I started by coding the classes architecture destined to stock these ones. I wanted it clear, but also hyper simple to use, to be able to focus myself on the logic and the strategy of the game. Here’s the result:

  • Coordinates: This class simply represent… Coordinates. A x, an y and a simple (Manhattan) method of distance calculation.
  • ItemSet: A class destined to represent a set of items (dishes, ingredients and desserts).
  • Order: A class inheriting of ItemSet, adding the award to cooking it.
  • Cell: A class representing a cell of the kitchen, walkable or not, and also inheriting of ItemSet to represent the available elements on it. It also has a type attribute, to quickly identify it (I have simply kept the ASCII representation of the input).
  • Kitchen: The representation of the map, containing, of course, an array of Cell.
  • Player: Simply inheriting of Coordinates and ItemSet.

The items sets representation

Since an ItemSet, i.e an Order, a Cell or a Player, can’t contain more than one element of each type, I decided to represent these items sets by bits fields, easier to use than strings. So I started by associate a power of two to each possible item via an enum :

enum Item {

    NONE = 0,
    DISH = 1,
    BLUEBERRIES = 2,
    ICE_CREAM = 4,
    STRAWBERRIES = 8,
    CHOPPED_STRAWBERRIES = 16,
    DOUGH = 32,
    CROISSANT = 64,
    CHOPPED_DOUGH = 128,
    RAW_TART = 256,
    TART = 512
};

From there, I modified my ItemSet class to contain a bits field, and by adding to it a constructor taking a string and using it to fill this bits field.

The toolbox

After that, I employed myself to code all the possibly useful tools which I could imagine:

  • I added a series of methods to my ItemSet class allowing to check if it contains an item, contains at least one item in a set, contains an entire set, and so on…
  • I improved my Kitchen class, notably by modifying the constructor to allow it creating as much data as possible from the input (kitchen in a form of Cell array, in a form of graph, Coordinates of equipment…).
  • I coded a BFS, and a series of functions based on it. First, several functions to find not walkable cells (closest item not in a dish, closest dish matching an order, closest “evacuation” i.e the dishwasher or the hatch,…), secondly a function to find the closest spot to access a not walkable cell. All of this taking the partner position in consideration.

About Remy

All of this done, it was time to code the decision function. Named Remy for the occasion, it has undergone a lot of modification through the leagues. But here’s in a nutshell the last version’s logic:

  • If Remy doesn’t have an order in progress, or if the order in progress has already been delivered, he chooses a new order.
  • To choose the order to prepare, Remy consider two things : The award of the order, and if a pending dish somewhere in the kitchen is matching. If a dish match, Remy just add 1000 (Totally arbitrarily) to the award. At the end he chooses the order with the best reward.
  • Then, Remy determine if some complex desserts (Croissant, tart, or chopped strawberries) must be prepared. If yes, he determine what to prepare first this way : If he’s closer to the closest strawberries than the closest dough, he start by the strawberries. If he’s closer to the dough, and the dough is closer to the oven than the chopping board, he starts by the croissant. Otherwise, he starts by the tart.
  • Once a preparation started, Remy finish it step by step. For example, if the tart is the first element to prepare, Remy will pick the dough, then will chop it, then will garnish it, then will cook it, and only after that he will select the next element to prepare.
  • If the oven is not empty, Remy will wait his turn, and eventually get out of the oven what is cooking, if the partner doesn’t (It’s the only case in what Remy take in consideration the partner baking.). During the cook, Remy just wait next to the oven.
  • If Remy is preparing a complex dessert, and the partner put on a table one dessert of this type, he stops his preparation and consider this element ready, except if he’s monitoring a baking, in this case he goes to the end.
  • At any step, excepted the baking, if the needed element has already been prepared and is available on a table, Remy will prefer picks it rather than prepare it.
  • Once all the complex preparations done, Remy composes the dish. First, he takes the closest element of the recipe, dish included. If he has an element in the hands which is not a dish, he goes take a dish. Then he takes the other elements of the recipe, one by one, by order of proximity.
  • When the order is ready, Remy deliver it. But if the partner delivers the same order before him, he put the dish on a table. Same thing during the preparation.
  • If there’s no clean dish, and no in progress dish which match with his current order, Remy take the closest dirty dish and go put it in the dishwasher or in the hatch, according to what is closest.
  • At any moment, if Remy is carrying something and needs his hands to do something, he’s able to put his load on a free table the time to perform this action.
That’s all!

Dropped idea

I wasted a lot of time with an idea which seemed good to me, but the results did not agree…

The problem were since the BFS take the partner position in consideration, Remy has some time to do the entire turn of the kitchen to access to an element, whereas perhaps the partner would have moved, next turn.

So I tried this: If the shortest way to access the element is blocked by the partner, Remy move next to him and wait two turns (The best value I tested.), if after that the partner has not moved, Remy take the other path.

By testing this in the IDE, I seen a real improvement of the Remy’s movements. But in the arena, the global results were poor…

Not seeing any bug, I rapidly tested some improves, like reconsidering the path if the partner move during Remy’s kitchen turn. But with no results…

So, I finally dropped the idea…

Ideas of improvements

  • I’m definitely convinced there’s a way to improve in the coordination of the Remy’s moves with the partner’s ones. Remains to find which…
  • There’s clearly better to do with the preparations order. Like doing the closest task whatever what Remy is doing. For example : Put a raw tart on a table the time to chop strawberries, if they are on the way to the oven.
  • Add a fix to avoid the infinite loops like : Remy is carrying chopped strawberries and puts them on a table to prepare another dessert. The partner is carrying a dish which is missing strawberries and see the Remy’s strawberries on the table. So he puts down his dish to come take these ones. But Remy see the partner’s dish and that it matches with his current order, without the strawberries. So, Remy take back the strawberries and go take the dish. But ! Not seeing the strawberries anymore, the partner takes back his dish. Not seeing the dish anymore, Remy puts down the strawberries, and so on…
  • Consider all the orders at the same time, and not only one.
  • Have a more collaborative comportment.

Thanks again everyone !

BlaiseEbuth


As a bonus, here’s a video of the contest (with sound!) made by @R4N4R4M4:

Something to say?

Leave a Reply

Your email address will not be published.