FLASH INFORMATIQUE FI



Le problème le plus populaire de l’hc2 2011 passé au crible


Pour la 2e édition de l’Helvetic Coding Contest, PolyProg a soumis 83 étudiants venant des quatre coins de la Suisse à un ensemble de huit casse-tête fort provocants demandant créativité, esprit d’équipe, excellentes capacités analytiques, tout comme des connaissances en C/C++ ou Java. Sur les 30 équipes, 24 se sont aventurées à résoudre le problème Terra Incognita qui s’avéra plus complexe qu’il n’y paraissait à première vue. Testez jusqu’où vous auriez poussé la barre...



For the 2nd edition of the Helvetic Coding Contest, PolyProg challenged 83 students from all over Switzerland with a set of eight brain teasers that asked the best of their creativity, team spirit, excellent analytical skills and working knowledge in C/C++ or Java. Out of the 30 teams, 24 ventured to solve the Terra Incognita problem, which turned out to be craftier than one would have thought at first sight. Test how far you would have kept pace...


Christian KAUTH


Le problème

Si les huit problèmes décrivaient le périple autour du monde de Heidi, vache mascotte du concours, il s’agissait dans Terra Incognita de deviner efficacement sa demeure actuelle en lui posant des questions. À cette occasion, Heidi vous a laissé une liste avec ses N (1 <=N <= 50) destinations et leurs descriptions. Les destinations peuvent être comparées via P (1<=P<=8) propriétés, qui peuvent avoir chacune une parmi trois valeurs possibles. Ces propriétés pourraient être emplacement (sur la côte, plaine, montagnes) ou attractivité (tourisme, culture, travail) entre autres. En ce qui nous concerne, les propriétés sont numérotées de 1 à P et peuvent prendre comme valeur 1, 2 ou 3. Toute paire de villes dans la liste de Heidi est différente selon au moins une propriété.
Vos questions doivent être de la forme : est-ce que la propriété p a la valeur x ? avec x dans 1,2,3 et p dans 1,...,P. Heidi répondra seulement par oui ou non. Étant donné que la communication pourrait être chère, vous devez minimiser le nombre de questions que vous posez avant de deviner dans quelle ville Heidi se trouve. Votre réponse est considérée correcte seulement si votre supposition correspond à la seule ville qui est cohérente avec toutes les réponses obtenues, et si vous n’avez pas posé plus de questions que nécessaire. Les cas de test sont conçus de manière à récompenser les solutions qui minimisent le nombre de questions dans le pire des cas, mais des stratégies non optimales obtiendront quand même quelques points.

Une première tentative

La première idée qui pourrait éventuellement vous venir en tête serait de considérer les N destinations l’une après l’autre. Pour chacune de ces destinations, nous posons à Heidi P questions, une par propriété, pour vérifier si les valeurs des propriétés de notre destination candidate correspondent bien à celles de la demeure actuelle de Heidi, pour un total de NP questions. Nous pouvons évidemment nous arrêter dès que nous trouvons une correspondance parfaite entre notre destination candidate et la demeure de Heidi ou sauter vers le prochain candidat dès qu’une contradiction se manifeste.
Si cette solution trouve la bonne destination et a l’avantage d’être courte à coder, elle s’avère horriblement inefficace. En effet Heidi décide de sa demeure en fonction de vos questions, et elle vous répondra de manière à maximiser le nombre de demandes nécessaires. Pour améliorer notre approche, nous pouvons mémoriser les réponses antérieures de Heidi afin de ne jamais répéter une question (p. ex. si deux destinations c1 et c2 ont la même valeur pour la première propriété p1, ne posons pas cette même question deux fois !)
Serait-il donc plus efficace de déterminer plutôt les valeurs des propriétés et de compter combien de villes sont en accord avec toutes les réponses ? Tout à fait, et c’est l’observation qui était nécessaire pour obtenir 40% des points ! Il suffit en effet de demander 1, voire 2 questions par propriété. Nous pouvons donc connaître les valeurs de toutes les propriétés pour un maximum de 2P questions seulement ! Si à l’obtention de chaque réponse, nous éliminons les villes en contradiction avec la réponse, nous pouvons arrêter le processus dès que toutes les destinations sont éliminées, à une exception près.

Bien choisir ses mots

Nous savons désormais que 2P questions font l’affaire à coup sûr et que Heidi nous donne toujours la pire réponse. L’astuce qui se propose serait de poser les questions non pas dans un ordre aléatoire, mais de choisir toujours la question qui nous apporte le plus d’information ! Si nous avons par exemple le choix entre deux questions qui partageraient les 11 villes restantes selon (10,1) et (5, 6) respectivement, nous avons apparemment meilleur temps de poser la deuxième, après laquelle il nous reste au maximum 6 candidats et non pas 10 ! L’algorithme qui trouve la question qui répartit les candidats le plus symétriquement possible simule en interne toutes les réponses à toutes les questions. Cette approche a séduit la moitié des équipes qui ont tenté ce problème, récompensées avec 70% des points.

La meilleure question

Malheureusement tout ce qui brille n’est pas or, et l’intuition peut tromper. S’il semble logique que le nombre de questions nécessaires est proportionnel au nombre de candidats restants, nous n’avons porté aucune importance à la corrélation des autres propriétés parmi ces candidats ! L’approche correcte serait de simuler toutes les questions dans tous les sous-ensembles de candidats possibles et de choisir la suite de questions la plus courte. Une telle technique s’appelle minmax. Comme son nom l’indique, elle essaye de minimiser le maximum de questions. Le problème peut effectivement s’interpréter comme un jeu, dans lequel nous essayons de minimiser le nombre de questions tandis que Heidi cherche à le maximiser.

Une bonne dose d’abstractions

Représentons ce jeu sous forme d’un graphe dont chaque noeud correspond à une constellation du jeu et chaque arrête représente un coup. Ainsi en posant/répondant à une question, nous traversons ce graphe. Pour que cela ait un sens, il faut que le graphe ait un point de départ et au moins un point d’arrivée. Comme chaque question force Heidi à restreindre le choix de sa demeure et chaque réponse nous permet d’exclure des candidats, ce graphe est acyclique (i.e. avec chaque coup, nous nous éloignons du point de départ) et le jeu s’approche forcément d’un point d’arrivée. Ce type spécial de graphes s’appelle arbre, illustré à merveille par l’image d’un vrai arbre. Nous partons du tronc (point de départ) et cherchons à atteindre une feuille (point d’arrivée). Pour chaque feuille il y a un seul chemin unique qui la relie au tronc.
Se pose naturellement la question sur la taille de cet arbre. Si chaque noeud représente une combinaison de candidats restants, il y a 2N (environ 1015) noeuds, ce qui dépasse largement les contraintes de mémoire et de temps d’exécution. Comme précédemment, nous pouvons observer que les états sont définis non pas par les destinations, mais par les valeurs que peuvent prendre les différentes propriétés. Avec 3 valeurs par propriété, la taille de l’arbre se réduit à moins que 23P. Accordons 3 bits à la représentation des valeurs possibles de chaque propriété, un par valeur. A priori la propriété peut avoir les valeurs 1, 2 ou 3, ce que nous représentons en binaire par 0b111 (un 1 par valeur possible). Pour les états 0b001, 0b010 et 0b100, la valeur de la propriété est connue. En notant que l’état 0b000 est inatteignable (la propriété ne peut pas être indéfinie), il y a 23-1 états par propriété. En concaténant les représentations de toutes les propriétés, nous arrivons donc à (23-1)P < 23P (environ 107) noeuds, une taille parfaitement admissible avec des états encodés en 32-bits.
Le point de départ avec toutes les valeurs possibles pour toutes les propriétés s’encode avec les 3P bits à 1, donc 23P-1. Toutes les feuilles ont exactement un bit à une par groupe de trois bits (i.e. par propriété). Sous l’hypothèse que les deux joueurs ne font pas de coup illégal, tous les états avec exactement P bits à 1 sont des feuilles (donc des points d’arrivée).

La traversée minmax de l’arbre

Chaque noeud est défini par sa constellation (state), le nombre minimal de questions qui le séparent d’une feuille (minQ), initialisé à l’infini (INF), tout comme la question (bestQ) à poser pour s’approcher de la feuille la plus proche. La fonction récursive find_clever_question trouve la meilleure question à poser dans la situation courante (cState) et mémorise tous les résultats intermédiaires pour ne pas gaspiller des ressources de calcul. Cette fonction vérifie tout d’abord si on est arrivé dans une feuille. Dans ce cas, il ne reste plus qu’un seul candidat et il n’y a plus de questions à poser. Ensuite elle vérifie si la constellation actuelle a été évaluée précédemment. Si oui, on connaît déjà le nombre minimal de questions depuis cette constellation. Si par contre nous avons à faire à une nouvelle constellation, pour l’évaluer, nous devons évaluer récursivement toutes les constellations qui peuvent naître de la constellation actuelle. Donc pour toutes les propriétés encore ambiguës, nous posons les questions nécessaires et évaluons les états qui naissent d’une réponse positive (yState) et d’une réponse négative (nState). Si le maximum des questions strictement nécessaires dans chacun de ces états, augmenté de 1, est inférieur au nombre de questions qui nous semblait nécessaire depuis l’état actuel, cette question est meilleure que n’importe quelle autre considérée jusqu’à présent.

Int Find_clever_question(int cState)
 If candidate_count(cState)<=1
   Return 0
 If minQ[cState] <> INF
   Return minQ[cState]
 for every property p for which cState has still several bits set
   for every value v set
     yState:= next_state(cState,'yes')
     nState:= next_state(cState,'no')
     minQ[yState]:= find_clever_question(yState)
     minQ[nState]:= find_clever_question(nState)
     if (max(minQ[yState],minQ[nState])+1 < minQ[cState])
       minQ[cState] = max(minQ[yState],minQ[nState])+1
       bestQ[cState] = (p,v)

Compter les bits, mais vite !

Toutes les fonctions utilisées par find_clever_question seront appelées fréquemment pendant la traversée récursive et il est crucial qu’elles soient de la moindre complexité possible pour réduire le temps d’exécution total. Intéressons-nous dans ce contexte à la fonction candidate_count qui retourne le nombre de candidats satisfaisant un certain état. Supposons pour cela que les candidats sont encodés comme les états, avec exactement un bit à 1 par groupe de 3 (1 valeur par propriété). Cette fonction doit itérer sur toutes les destinations et compter pour combien d’entre elles les bits à 1 dans la destination sont aussi à 1 dans l’état (i.e. l’état n’exclut pas la destination). Une telle comparaison peut se faire en complexité linéaire en comparant les nombres bit par bit.
Mais il y a mieux ! Comme les états et destinations sont encodés par des nombres à 32 bits, l’union logique bit par bit (&) se fait en temps constant. Il s’agit ensuite de vérifier si cette union a P bits à 1 (nécessairement un par propriété, comme la destination l’impose). Ce comptage de bits pourrait se faire aussi par considérations bit par bit. Mais la même union logique en temps constant nous permet de gagner un facteur 4 en comparant les bits par groupes de 4 ...

Count_bits(int n)
 bcnt4[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
 nBits(0);
 while (n)
   nBits += bcnt4[n & 0xF];
   n >>= 4;
 return nBits

voire même en temps constant d’un seul coup en parallèle par cette formule un peu magique.

count_bits(int n)
 n = n - ((n >> 1) & 0x55555555);
 n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
 return (((n + (n >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;

Le calcul des états yState et nState se fait aussi en temps constant par des opérations logiques sur les bits, moins exotiques pourtant. Est-ce que vous pouvez les imaginer ?
Voilà, la barre est maintenant bien au niveau des prestigieux concours internationaux d’algorithmique et je vous propose d’accorder une pause à votre matière grise. Si vous désirez enchaîner sur d’autres problèmes de l’hc2 2011, organisé par PolyProg et sponsorisé par Open Systems , vous trouverez votre compte sur hc2.ch qui offre en accès libre tous les documents du concours (données en 3 langues, solutions en C++, fichiers pour tester votre code, tout comme le juge qui fait les tests automatiquement). Au plaisir de vous accueillir pour l’édition 2012 ou lors d’une des séances de formation de PolyProg .
Bravo à Sandro Feuz, Sebastian Millius et Christian Helbling qui ont remporté la médaille d’or à l’ETHZ !
Au plaisir de vous accueillir pour l’édition 2012 ou lors d’une des séances de formation de PolyProg.



Glossaire

calcul des états yState et nState  :
yState         =  cState & ~((1<<(p*3+((v+1)%3))) | (1<<(p*3+((v+2)%3))))
nState         =  cState & ~(1<<(p*3+v)

hc2  :

premier concours de programmation suisse organisé annuellement à l’EPFL par PolyProg, hc2.ch

Open Systems :

www.open.ch

PolyProg :

association du campus qui promeut les compétences en algorithmique des étudiants et doctorants

séances de formation de PolyProg :

moodle.epfl.ch/course/view.php ?id=8471, key="SayHello"



Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.