FLASH INFORMATIQUE FI



hc2.ch, a success story made in EPFL


Les 125 étudiants intrépides qui ont participé à l’édition 2013 de l’Helvetic Coding Contest se sont brisé les dents sur une quinzaine de problèmes algorithmiques très exigeants. Pour y réussir, il fallait avoir plus d’un tour dans son sac  ! Accordez-vous une petite escapade au monde des casse-têtes…



The 125 brave students who participated in the 2013 edition of the Helvetic Coding Contest found in the fifteen proposed algorithmic tasks a hard nut to crack. To be successful, one needs to be up to every trick  ! Allow yourself a short trip to the amazing world of brain-teasers…


Christian KAUTH


Il est devenu culte et le rendez-vous annuel par excellence pour tout programmeur qui se respecte – l’Helvetic Coding Contest (hc2) a rassemblé en mars sur le campus 125 étudiants afflués des quatre coins du pays. L’équipe d’organisation de PolyProg a su, une fois de plus, servir ce qui va droit au coeur de tout programmeur : une série de casse-têtes algorithmiques stimulants disponibles en trois langues, assaisonnée par un riche buffet et des présentations techniques, le tout dans une ambiance amicale et agréable.

Esprit d’équipe, créativité et know-how

Une inscription via hc2.ch, un petit problème de qualification, nécessaire pour harmoniser la demande avec l’offre, et tout allait comme sur des roulettes. À la sortie du métro, il suffisait de se laisser guider par les flèches pour s’immerger dans l’ambiance hc2 et ce, dès l’entrée dans les bâtiments du Centre Ouest. Check-in rapide, photo d’équipe et un café-croissant pour bien démarrer la journée en causette. Une sonnerie de cor annonça la partie officielle de la journée, qui commença par un mot de bienvenue et quelques présentations des sponsors Open Systems et AdNovum. Elle fut suivie d’un léger concours à blanc pour se familiariser avec l’environnement : chaque équipe tricéphale disposait d’un seul ordinateur pour résoudre les problèmes et y coder une solution en C/C++ ou Java. Le code était à soumettre via une interface Web, qui répondait quelques secondes plus tard avec le verdict. Dès que le code avait résolu les tests correctement dans le délai imparti, un nouveau problème, plus épineux, devenait accessible à l’équipe. À la fin de cet échauffement, un buffet bien garni attendait les participants. Le moment de faire le plein en énergie pour quatre heures et demie de concours intensives. Esprit d’équipe, créativité et compétences algorithmiques furent de mise pour résoudre un maximum de problèmes. Des posters présentés en fin de journée révélèrent les solutions. La journée se clôtura par la remise des prix pour les meilleurs et pour les plus chanceux. Les vainqueurs 2013 étudient à l’ETHZ et se classent parmi les jeunes programmeurs les plus talentueux du monde.



Nombre de participants aux concours hc2 depuis 2010

Si la mémoire fait défaut

Je vous propose de saisir papier et stylo et d’essayer de résoudre un problème du concours qui a piégé deux tiers des équipes qui s’y sont attaquées. Un vrai régal dont la solution ne présuppose aucune connaissance en programmation. Imaginez une liste de chiffres uniques, qui est rebouclée sur elle-même, comme l’illustre la figure ci-dessous. Cette liste ne peut être traversée que dans un sens (indiqué par la flèche) et consiste en une partie linéaire suivie d’une partie cyclique, qui fait que vous pouvez passer l’éternité à la traverser. On vous donne le début de cette liste et vous demande combien d’éléments uniques elle contient. Pour ce faire, vous pouvez demander l’identité de la case suivante pour n’importe quelle case de votre choix. Cette information vous permet de traverser la liste. Puisque chaque case est caractérisée par un identifiant unique, vous avez moyen de distinguer les cases. L’approche qui saute à l’oeil consiste à mémoriser les identifiants, et d’arrêter la traversée dès qu’un duplicata est trouvé, car ce serait la fermeture du cycle. Ceci est correct, mais malheureusement vous ne disposez de loin pas d’assez de mémoire pour mémoriser tous les identifiants des cases – bienvenu(e) à l’hc2 !



Le lièvre et la tortue

L’astuce consiste en plusieurs traversées de la liste à des vitesses différentes. Imaginez une tortue et un lièvre, qui partent en même temps, avec des vitesses de 1 et 2 respectivement. Supposez que la partie linéaire de la liste contienne L (3 dans l’exemple) éléments, tandis que la partie cyclique en est composée de C (9 dans notre cas). Vu que le lièvre court deux fois plus vite que la tortue, et que la partie linéaire a une longueur L, il aura une avance de L sur la tortue au moment où celle-ci s’apprête à entrer dans le cycle. À vrai dire, le lièvre court en cercle de longueur C, donc son avance effective vaut L modulo C.



À partir de ce moment, les deux courent en rond, et le lièvre finira par doubler la tortue, après que cette dernière aura fait X pas dans le cycle. Étant donné que le lièvre avait une avance de L modulo C pas et court deux fois plus vite, X doit vérifier la congruence suivante : X = L + 2X (mod C) dont la solution est X=-L (mod C). Ceci veut dire que les deux se rencontrent à L pas devant l’entrée au cycle !



Au moment de la rencontre du lièvre et de la tortue, faisons partir une deuxième tortue depuis le début de la liste. L pas plus tard, cette tortue aura parcouru la partie linéaire, et l’autre viendra d’achever son premier cycle. Ainsi les deux carapacés se rencontreront à l’entrée du cycle, observation cruciale pour résoudre l’énigme ! Il en suit que la longueur de la partie linéaire correspond à la distance parcourue par la deuxième tortue avant qu’elle ne rencontre la première.



Reste à déterminer la longueur du cycle. Pour ce faire, organisons encore une course entre tortue et lièvre depuis l’entrée du cycle. Comme vous l’aurez deviné, le lièvre doublera la tortue à ce même endroit deux tours plus tard. Ainsi la longueur du cycle correspond à la distance parcourue par la tortue dans cette course, information qui vous suffit pour résoudre notre petite énigme !

En résumé 

  • Faites partir ensemble le lièvre et la tortue 1.
  • Au moment du doublement, faites partir la tortue 2 et démarrez le chrono.
  • Au moment de la rencontre des deux carapacés, le chrono indique L+1. Remplacez une tortue par un lièvre.
  • Au moment du doublement, le chrono indique L+C+1.
  • La réponse au problème est L+C.

Si cette petite excursion au monde des casse-têtes a suscité votre intérêt, n’hésitez pas à partir à la découverte de la gamme entière des colles posées aux participants de l’Helvetic Coding Contest sur hc2.ch.
PolyProg, [polyprog.epfl.ch->http://polyprog.epfl.ch, sera de retour avec de nouveaux défis algorithmiques dès la rentrée académique !





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.