Google Hash Code, édition 2015 !

L'année dernière il s'agissait de quelque chose (je crois la plateforme (sous entendu : Android, bureau..) n'avait pas d'importance) qui devait permettre de trouver le chemin optimal dans les rues de Paris. Je t'invite à taper sur Google : "Google Hash Code 2014"

Pour la première épreuve (qui était juste une épreuve de test pour anticiper le déroulement du lendemain), j'ai fait un topic dessus (avec 0 réponse ) : https://zestedesavoir.com/forums/sujet/1974/dessiner-en-binaire-avec-de-lascii/

Pour le deuxième sujet, tu peux aller regarder ici (et avoir une solution du problème) : http://www.jill-jenn.net/codeweek/3-exploration-paris.html

Pour l'organisation, ce qui est bien c'est la bouffe à volonté. Sinon l'ambiance est cool mais trop peu de communication entre équipes je trouve (sans se passer les solutions mais juste discuter). L'année dernière on était directement situé dans la cafétéria, l'installation était parfaite.

Après comme c'est résumé dans l'article de Jill-Jênn, ce fut décevant de constater que les premiers n'avaient pas des algorithmes très sioux. La première épreuve était je trouve beaucoup plus intéressante.

Merci je regarderais ça de plus pret

Sososo ? Une équipe pour se former ?

Bonjour à tous !

Plus que deux semaines pour se préparer au tour de qualifications ! Avec mes coéquipiers, on enchaîne les sujets de Prolog pour s'entraîner, et vous ? J'ai cru comprendre qu'il y avait une ou plusieurs équipes en voie de formation par ici, est-ce que c'est toujours d'actualité ?

Oui.. J'ai fait un post mais personne ne semble motivé..

Salut à tous,

Pour ceux que ça intéresse, j'y ai participé et c'était vraiment fun. Au final, en 4h c'est plutôt chaud d'imaginer un gros algo et on peut avoir des résultats plutôt bon (378 au final pour mon équipe, en sachant que la meilleur équipe était à 404 une heure avant la fin) avec une heuristique assez simple, un peu d'aléatoire et peut-être un peu de chance.

D'ailleurs, le sujet était sur la répartition optimal de n serveurs sur m baies entre p services de manière à maximum les performances du service le moins performant dans le cas où sa meilleur baie est down… et comble de l'ironie les serveurs du hash code était totalement HS au début (pas loin de 10 minutes je dirais) et surtout à la fin où on pouvait même plus submit pendent les 15 dernières minutes. Ce qui fait qu'ils ont dû rallonger le temps alloué pour envoyer les solutions qui ne se faisait plus par leur site mais par un formulaire gDoc. On aurait quasiment dit Prologin au niveau organisation (#freeTroll).

J'ai participé, mais j'ai presque pas codé (trop rouillé du code). Du coup, j'ai donné des pistes d'idées à exploiter et j'ai aidé moralement mes teamates.

On a fait 322, puis peut-être un 361, mais vu qu'on a pas pu le soumettre et que ça passe par le formulaire, pas moyen de vérifier.

On est parti sur un algorithme de recherche local.

Par contre, j'aime pas trop ces problèmes où tu pars d'une solution simple et tu l'améliores par un glouton/une heuristique. Ca avantage trop le code sur l'algorithme.

Par exemple voir l'équipe d'Ulm à 321 après 30mn, tu sens la solution hasardeuse qui pop. Et ensuite pour monter, il faut trouver l'heuristique qui marche bien.

Dans le Hub, il y avait deux trois profs et leurs idées étaient les mêmes. Pas d'algorithme astucieux à trouver, non, juste des heuristiques "faciles" à mettre en place. C'est pas inintéressant, mais je trouve que ça prime un peu trop sur la qualité de l'algorithme.

Ca reste une expérience intéressante à faire, et être dans un Hub c'est assez sympa (notamment pour voir les profs sécher sur le problème).

La question que je me suis posée dès le début, c'est s'il n'était pas possible d'utiliser un programme linéaire pour résoudre ce problème. Les contraintes me semblaient pas trop dur à formaliser.

Résultats tombés : on est les derniers à se qualifier grâce au formulaire de fin.

Arff toujours trop lent … C'est con je m'étais bien débrouillé à prolog l'année derniere. Saroupille: GG! du coup vous etes pris pour qu'elle phase ?

La phase où tu as le droit de visiter les locaux de google pour disputer une finale sympa ! (et deux repas offerts)

Pareil, on est aussi qualifié. Par contre, je doute que les deux repas offerts arrivent à rentabiliser l'aller-retour Toulouse/Paris

Ca gere! bon faut pas que j'oublie l'an prochain

Berdes, quelle était votre méthode pour résoudre le problème ?

Globalement, c'était une génération directe de solution : On tri les serveurs par capacité/taille et on les place au fur et à mesure dans les baies qui ont le moins de puissance. Ça permet d'équilibrer facilement la puissance des baies. Ensuite, on assigne les serveurs aux différents groupes de la même manière, baie par baie à chaque fois au groupe qui a le moins de puissance, encore une fois pour équilibrer.

Il me semble que ça nous a permis d'obtenir quelque chose comme 369. Vu que c'était quasiment la fin on a ensuite préférer ajouter un peu d'aléatoire pour explorer rapidement pas mal de possibilités a priori équivalentes : quand il y a plusieurs groupes qui ont la même capacité, on assigne le serveur sur un d'eux au hasard. Pareil pour le remplissage des baies. On a du monter un peu (371-372) et ensuite, on a augmenté l'aléatoire : au lieu d'affecter un serveur uniquement à des groupes qui ont le moins de capacité, on a élargi un peu aux groupe qui ont une capacité proche de la capacité minimale. Et on est monté jusqu'à 378 comme ça.

Après, on aurai pu aussi générer une bonne solution et l'améliorer ensuite en repérant pour chaque groupe la baie avec la plus grande capacité (qui ne sert à rien dans le score) et passer la puissance excédentaire de cette baie à un autre groupe qui en profiterais.

Ok, bravo d'avoir réussi à implémenter cette idée en si peu de temps.