Evènements

Retour sur le Google Hash Code 2016

Publié le : Auteur: pcrouzet Laisser un commentaire
Logo du Google Hash Code 2016

Le 11 février dernier avait lieu le Google Hash Code. Un événement international couvrant l’Europe, le Moyen-orient et l’Afrique et réunissant plus de 1000 équipes de 2 à 4 personnes autour d’une même problématique de développement. Objectif pour chaque équipe : soumettre au moins une solution à un problème posé en moins de quatre heures. Chaque solution était ensuite analysée et les scores en résultant permettaient de classer les équipes en compétition. Le Groupe Sodifrance a présenté plusieurs équipes dans ses agences de Rennes, Nantes et Angers.

Membres des deux équipes de Rennes participant au Google Hash Code 2016
Les membres des deux équipes de Rennes participant au Google Hash Code 2016

Le sujet de cette édition s’intitule « Delivery » (livraison). Il s’agissait d’utiliser une flotte de drones pour livrer des commandes de produits stockés dans différents entrepôts jusqu’à leur destination, chez les clients. Évidemment, les drones ont une charge utile limitée et ne peuvent donc pas forcément porter l’ensemble des produits d’une commande. En plus de ça, les entrepôts n’ont pas tous le même stock et les drones doivent donc s’approvisionner dans l’entrepôt ayant le(s) produit(s) en stock.

La solution doit :

  • Analyser un fichier contenant les paramètres initiaux (positions et quantités de drones, produits, commandes, entrepôts) ;
  • Exécuter son algorithme de livraison ;
  • Produire un fichier contenant les ordres à donner aux drones pour effectuer les livraisons.

Algorithme de résolution

Notre équipe Sodifrance 1 a choisi de développer en C# avec Visual Studio 2013. Pour partager le code entre les membres de l’équipe, nous avons utilisé Visual Studio Online, une plateforme gratuite de gestion de configuration logicielle et d’intégration continue.

Face au temps qui nous a rapidement manqué, nous avons choisi de développer une solution simple que nous pourrions optimiser si le temps nous le permettait.

Elle consiste à parcourir les commandes (orders) et affecter un drone au traitement de l’ensemble de la commande :

public IEnumerable<string> Solve()
{
 var commands = new List<string>();
 var droneId = 0;

 foreach (var order in challenge.orders)
 {
 var nearestWarehouse = ComputeNearestWarehouse(order, challenge.warehouses);
 if (nearestWarehouse != null)
 {
 commands.AddRange(ComputeCommands(order, nearestWarehouse, droneId % challenge.nbDrone));
 RemoveProducts(nearestWarehouse, order);
 }
 droneId += 1;
 }

 return commands;
}

Pour chaque commande, nous choisissons l’entrepôt (warehouse) le plus proche qui possède en stock l’ensemble des produits de la commande :

public static Warehouse ComputeNearestWarehouse(Order order, IEnumerable<Warehouse> warehouses)
{
 var possibleWarehouses = new List<Warehouse>();

 foreach (var warehouse in warehouses)
 {
 if (warehouse.NbItemsOfType.Select((p, i) => p >= order.NbItemsOfType[i]).All(b => b))
 {
 possibleWarehouses.Add(warehouse);
 }
 }

 return possibleWarehouses.OrderBy(w => Program.CalculMove(w.Position, order.Destination)).FirstOrDefault();
}

Chaque commande est ensuite subdivisée en un ou plusieurs paquets (ProductGroups), selon le poids des produits et la charge maximale du drone :

public IEnumerable<string> ComputeCommands(Order order, Warehouse warehouse, int droneId)
{
 var commands = new List<string>();

 var groupsOfProduct = ComputeProductGroups(order.NbItemsOfType, challenge.productWeights);

 foreach (var groupOfProduct in groupsOfProduct)
 {
 var products = groupOfProduct as IList<int> ?? groupOfProduct.ToList();

 foreach (var product in products.GroupBy(p => p))
 {
 commands.Add(string.Format("{0} L {1} {2} {3}", droneId, warehouse.Id, product.Key, product.Count()));
 }

 foreach (var product in products.GroupBy(p => p))
 {
 commands.Add(string.Format("{0} D {1} {2} {3}", droneId, order.Id, product.Key, product.Count()));
 }
 }

 return commands;
}

Diviser la commande en paquets supportables pour le drone :

public IEnumerable<IEnumerable<int>> ComputeProductGroups(IList<int> productList, IList<int> productWeightList)
{
 IList<IEnumerable<int>> result = new List<IEnumerable<int>>();
 var completeProductList =
 productList.Select((p, i) => new Product { Id = i, Weight = productWeightList[i], Count = p })
 .OrderByDescending(p => p.Weight)
 .Where(p => p.Count > 0)
 .ToList();

 while (completeProductList.Any())
 {
 var currentCount = 0;
 var newGroupOfProduct = new List<int>();
 while (currentCount < challenge.maxPayload && completeProductList.Any())
 {
 if (completeProductList.First().Weight <= challenge.maxPayload - currentCount)
 {
 currentCount += completeProductList.First().Weight;
 completeProductList.First().Count -= 1;
 newGroupOfProduct.Add(completeProductList.First().Id);
 if (completeProductList.First().Count == 0)
 {
 completeProductList.RemoveAt(0);
 }
 }
 else
 {
 break;
 }
 }

 result.Add(newGroupOfProduct);
 }

 return result;
}

Résultats

Nous avons pu soumettre notre première solution (valide) seulement 30 minutes avant la fin du temps imparti avec 187 028 points. Nous avons profité des dernières minutes pour apporter de rapides optimisations et monter à 191 492 points. Au classement final, Sodifrance 1 a terminé 351ème sur 1054. Un classement honorable pour une première participation.

Graphique présentant la fréquence des scores par intervalles de 10000 points
Fréquence des scores par intervalles de 10000 points

Il nous a été difficile de partager les tâches sur quatre personnes. Mais globalement, nous avons pair-programmé la plupart du temps et lorsqu’une partie du code était terminée, quelqu’un d’autre la validait.

Lors de ce genre d’événement, on se trouve en situation vraiment différente de notre quotidien. En effet, dans une entreprise de services numériques comme Sodifrance, une part importante de notre métier est de produire un code robuste et maintenable dans la durée. Mais la qualité a un coût que nous ne pouvions pas prendre en charge dans ce contexte, sous peine de ne pouvoir soumettre aucune solution. Il nous a fallu produire très rapidement un code fonctionnel sans se soucier de la dette technique… Ceci dit, nous avons tout de même écrit quelques tests unitaires de façon à pouvoir tester rapidement une fonctionnalité, mais aussi d’éviter une régression si nous étions amené à modifier le code :

[Test]
public void CanCalculMove()
{
 Assert.That(Program.CalculMove(new Point(0, 0), new Point(1, 1)), Is.EqualTo(2));
 Assert.That(Program.CalculMove(new Point(0, 0), new Point(2, 2)), Is.EqualTo(3));
 Assert.That(Program.CalculMove(new Point(0, 0), new Point(3, 3)), Is.EqualTo(5));
 Assert.That(Program.CalculMove(new Point(1, 5), new Point(1, 4)), Is.EqualTo(1));
 Assert.That(Program.CalculMove(new Point(1, 5), new Point(1, 3)), Is.EqualTo(2));
 Assert.That(Program.CalculMove(new Point(1, 5), new Point(2, 5)), Is.EqualTo(1));
 Assert.That(Program.CalculMove(new Point(1, 5), new Point(3, 5)), Is.EqualTo(2));
 Assert.That(Program.CalculMove(new Point(5, 0), new Point(0, 1)), Is.EqualTo(6));
}

[Test]
public void CanComputeProductGroups()
{
 var solver = new Solver(new Program(true, null) { maxPayload = 400 });
 var productList = new[] { 1, 2, 3 };
 var weightList = new[] { 100, 50, 200 };

 IList<IEnumerable<int>> expectedList = new[] { new[] { 2, 2 }, new[] { 2, 0, 1, 1 } };

 var actual = solver.ComputeProductGroups(productList, weightList);
 Assert.That(actual, Is.EqualTo(expectedList));
}

//...

Représentation graphique

Google a mis à disposition une représentation graphique de chaque solution. Voilà à quoi ressemble la nôtre (nous n’avons pas pu enregistrer une vidéo qui soit fluide, l’effet de mouvement est ici très saccadé) :

Représentation graphique des livraisons de commandes par les drones
Représentation graphique de la solution