| Figure 1: carte 1 |
1ère Journée Francilienne de Programmationorganisée par les universités Pierre et Marie Curie (Paris 6), Paris Diderot (Paris 7) et Paris-Sud 11 (Paris 11)21 janvier 2009 |
Les conditions générales des JFP sont décrites par ailleurs ainsi que nombre de conditions particulières à cette journée-ci janvier 2009. Le tout est assorti de quelques conseils (bien sûr, vous les avez déjà lus auparavant). Ce document présente l’énoncé de cette première JFP.
Les tâches qui vous sont soumises peuvent être abordées dans l’ordre qui vous convient. Néanmoins, le code de l’une peut servir au code de l’autre. Regardez l’ensemble des tâches qui vous incombent et n’hésitez pas à factoriser le code.
Un certain nombre de ressources sont mises à votre disposition dans le répertoire ~jfp. Dans la suite du texte la variable d’environnement DIRJFP vaut ~jfp.
Vous logerez tous les fichiers répondant aux questions posées dans un unique répertoire nommé jfp que vous devez créer directement dans votre HOME. Le contenu de ce répertoire sera ce que vous soumettrez. Attention: tous les fichiers explicitement demandés devront être à la racine de ce répertoire. Vous soumettrez sous forme d’une archive tarézipée que vous fabriquerez en étant à la racine de ce répertoire. Vous pourrez soumettre ce contenu autant de fois qu’il vous plaira (soumettez donc régulièrement) mais seule la dernière soumission sera prise en compte.
La page de livraison et les fonctions de tests de vos soumissions sont hébergées sur le site de Paracamplus. Vous y accèdez en utilisant le bouton
Le thème de cette journée est le jeu des robots de l’espace connu sous le nom Lunar Lockout1.
Des robots sont disposés sur un espace représenté par un carré de cases. Le but du jeu des robots de l’espace est, à partir d’une position initiale des robots, d’amener un robot particulier, nommé @, sur la case centrale du carré. Le mode de déplacement des robots s’inspire de la loi d’inertie : à partir d’une impulsion initiale, un robot poursuit infiniment sa route s’il ne rencontre aucun obstacle ; ici, un autre robot. Un robot peut choisir la direction de son déplacement. Lorsqu’il a été arrêté par un obstacle, un robot peut poursuivre son chemin en donnant une nouvelle impulsion dans la direction de son choix.
L’espace avec lequel nous jouerons est un carré de p cases sur p cases, avec p impair vérifiant 5 ≤ p ≤ 51. Outre le robot @, il peut avoir entre 1 et 10 autres robots sur un jeu. Le robot @ est toujours présent dans le jeu. Les autres, suivant leur nombre, sont nommés dans l’ordre alphabétique, de A à J.
La figure 1 est un exemple de carte pour un espace de 5 sur 5 avec 5 robots. Le robot @ est sur fond rouge, A sur fond orange, B sur fond vert, C sur fond bleu et D sur fond jaune. La case centrale grisée correspond au but à atteindre du robot rouge @.
Figure 1: carte 1
Une carte de p cases sur p cases est représentée par p lignes de p caractères chacune. Une case vide est représentée par un point (caractère .), un robot par son nom (caractères @ A B C D E F G H I J). Ces lignes sont précédées par le nombre p de cases du côté du carré.
Par exemple, la carte 1, correspondant à la figure 1, est représentée par les 6 lignes :
5 ..A.. B.... ...C. ..... .@.D.
Cette carte est contenue dans le fichier ${DIRJFP}/carte1.map.
Une carte qui représente une situation initiale sera dite conforme si elle vérifie:
Un robot se déplace dans une des quatre directions cardinales : Nord, Sud, Est, Ouest. Selon l’usage, le nord est situé en haut de la carte, l’est à droite, le sud en bas et l’ouest à gauche.
Les bords du carré ne constituent pas un obstacle.
Les seuls déplacements admis sont donc ceux qui amènent un robot à toucher un autre robot. Ce sont les mouvements légaux du jeu. Un robot s’arrête sur la case précédent l’obstacle rencontré.
Par exemple, à partir de la position initiale donnée par la carte 1, figure 1, D peut aller vers l’ouest (à gauche) car @ l’arrête, dans ce cas D est positionné sur la colonne du milieu. La nouvelle carte résultant de ce mouvement est donné à la figure 2 :
position initiale position résultante
Figure 2: carte 1 - mouvement de D vers l’Ouest (gauche)
Il y avait bien sûr bien d’autres mouvements légaux à partir de cette position initiale. Les voici tous :
Tout autre déplacement serait un mouvement illégal puiqu’il entraînerait le robot à… sortir de l’espace !
Un déplacement, ou mouvement, est représenté par deux caractères : le nom du robot et l’initiale de la direction (N, S, E ou O).
Par exemple :
Le code d’un mouvement représente un coup. Étant donnée une carte, un coup légal est la donnée de deux caractères tels que
Tout autre coup est illégal.
Pour amener le robot @ sur la case centrale, il est en général indispensable d’enchaîner plusieurs mouvements.
Les 5 mouvements DO, DN, DO, @N et @E amènent @ sur la case centrale. Ils constituent une solution au problème posé par la position initiale de la carte 1. Les cartes engendrées par ces mouvements sont données figure 3.
0 - position initiale 1 - D va vers l’ouest 2 - D va vers le Nord 3 - D va vers l’ouest 4 - @ va au nord 5 - @ va vers l’est
Figure 3: carte 1 - solution en 5 mouvements
Un jeu est codé par une suite de caractères représentant une suite de mouvements (au sens de 1.2). Les différents mouvements peuvent être séparés par des espaces ou des retours-chariot. En revanche, les deux caractères qui représentent un mouvement ne doivent pas être séparés.
Le programme arbitre.exe, disponible dans le répertoire ~jfp, permet de jouer une partie. L’arbitre lit la carte initiale dans un fichier texte dont le nom est passé sur la ligne de commande, puis attend sur l’entrée standard (stdin) la suite de mouvements à exécuter. Le code de chaque mouvement et la carte en résultant (sauf sa taille) sont affichés sur la sortie standard (stdout).
Le jeu s’arrête :
L’arbitre permet de jouer une partie en interaction avec le clavier. En voici un exemple où la saisie du joueur est donnée en rouge et la réponse de l’arbitre en noir.
${DIRJFP}/arbitre.exe ${DIRJFP}/carte2.map
A.@.. ..... ..... ....B .C...
AE
==>AE .A@.. ..... ..... ....B .C...
AS
==>AS ..@.. ..... ..... .A..B .C...
BO
==>BO ..@.. ..... ..... .AB.. .C...
@S
==>@S ..... ..... ..@.. .AB.. .C... GAGNANT
On peut utiliser les ressources de l’interprète de commandes en ligne pour tester plus rapidement une suite de coups. Par exemple
echo AEASBO@S | ${DIRJFP}/arbitre.exe ${DIRJFP}/carte2.map
A.@.. ..... ..... ....B .C... ==>AE .A@.. ..... ..... ....B .C... ==>AS ..@.. ..... ..... .A..B .C... ==>BO ..@.. ..... ..... .AB.. .C... ==>@S ..... ..... ..@.. .AB.. .C... GAGNANT
Ou, si le fichier texte soluce.sol contient la ligne
AEASBO@S
on obtient le même résultat avec
${DIRJFP}/arbitre.exe ${DIRJFP}/carte2.map < soluce.sol
Dans l’exemple ci-dessous, le joueur rate son dernier coup :
echo AEASBO@N | ${DIRJFP}/arbitre.exe ${DIRJFP}/carte2.map
A.@.. ..... ..... ....B .C... ==>AE .A@.. ..... ..... ....B .C... ==>AS ..@.. ..... ..... .A..B .C... ==>BO ..@.. ..... ..... .AB.. .C... ==>@N ..@.. ..... ..... .AB.. .C... PERDANT
Et voici pour finir l’exemple d’une partie où le joueur n’a pas su aller assez loin :
echo AEASAE | ${DIRJFP}/arbitre.exe ${DIRJFP}/carte2.map
A.@.. ..... ..... ....B .C... ==>AE .A@.. ..... ..... ....B .C... ==>AS ..@.. ..... ..... .A..B .C... ==>AE ..@.. ..... ..... ...AB .C... PERDANT
L’espace de cette première épreuve est la carte contenue dans le fichier $DIRJFP/carte3.map :
5 ..A.. B.... ...C. ..... .@.D.
Vous devez
Vous pouvez gagner 2 roublards vénusiens :
La conformité d’une solution indique que tous les coups proposés soient légaux. Elle sera testée avec notre arbitre.exe et notre carte carte3.map.
En 1214 avant les JFP, le célèbre joueur artificiel Bleu Profond à proposé l’astucieuse solution suivante
DN BE @O @S @E
Malheureusement, la carte posant le problème auquel répondait cette solution a été perdue. Tout ce que l’histoire a conservé est qu’elle était de taille 5 sur 5.
Vous devez reconstituer cette carte et nous la faire parvenir dans un fichier nommé macartebleue.map.
Vous pouvez gagner 3 roublards vénusiens :
La conformité d’une carte indique qu’elle respecte le format des cartes (n nombre de lignes suivi de n lignes de n caractères correspondant à un ’.’ ou à un caractère robot allant de ’@’ à ’J’). Elle sera testée avec notre arbitre.exe.
Perdu dans votre fin fond de l’hyper espace vous commencez à douter des règles du jeu des robots de l’espace. Avant que votre mémoire ne s’efface totalement, vous décidez de programmer un arbitre du jeu.
Vous respecterez scrupuleusement le comportement de l’arbitre : format des cartes (que vous avez noté ici), format des mouvements et suites de coups (que vous avez noté ici), format des affichages des étapes du jeu et des affichages des fins de partie (que vous avez noté ici).
Vous devez, en tant que membre de la FIFO (Fédération Intergalactique des Fonctions Ouvertes), et bien que perdu au fin fond de l’hyper espace, nous faire parvenir l’ensemble des sources de votre programme ainsi qu’un script bash (ou sh) nommé compil-monarbitre.sh dont l’exécution permet de compiler votre arbitre avec l’un des langages disponibles. L’exécutable engendré s’appellera monarbitre.exe.
Les règles de diffusion de la FIFO sont extrêmement strictes :
Toute compilation, si compilation il y a, doit être des plus précautionneuses et ne produire aucune erreur ni aucun avertissement.
Vous pouvez gagner jusqu’à 7 roublards vénusiens :
À la 174 042 635-ième partie arbitrée par votre programme, une certaine lassitude vous envahit. D’autant que vous inventez vous-mêmes à la fois le problème et la solution. Vous décidez donc de programmer un joueur. Prudent, vous découpez votre tâche en deux étapes.
Dans cette première étape, vous réalisez un programme qui prend sur la ligne de commande un fichier contenant une carte, qui calcule l’ensemble des coups légaux possibles à partir de cette position et les affiche sur la sortie standard.
Chaque coup est affiché sur une ligne. Ils sont triés par ordre alphabétique sur les robots (@ est le premier), puis, à nom de robot égal, par ordre alphabétique sur les directions, c’est-à-dire qu’ils sont triés par ordre lexicographique croissant.
Par exemple, la carte
5 A.@.B ..C.. ..... ..... D...E
donnera l’affichage
@E @O AE AS BO BS DE DN EN EO
Vous devez nous livrer l’ensemble des sources de votre programme ainsi qu’un script compil-coupslegaux.sh permettant leur compilation. L’exécutable engendré s’appellera coupslegaux.exe.
Vous pouvez gagner 6 roublards vénusiens :
Cette première étape accomplie, vous vous lancez dans la réalisation d’un programme joueur qui recherche une solution.
Ce programme prendra sur la ligne de commande le nom du fichier contenant la carte avec laquelle jouer. Si le programme trouve une solution, il affiche sur la sortie standard la suite de coups à jouer. Sinon, il affiche uniquement le message PASTROUVE.
La solution affichée, lorsqu’elle est trouvée, pourra être envoyée telle quelle au programme arbitre.exe.
Vous devez nous faire parvenir les sources de votre programme ainsi qu’un script écrit en bash et nommé compil-joueur.sh dont le rôle est de fabriquer l’exécutable nommé joueur.exe.
Vous pouvez gagner jusqu’à 10 roublards vénusiens
Bonus jusqu’à 6 rubiks saturniens si votre solution fait partie des plus rapides ou des plus élégantes. Attention les rubiks saturniens ne peuvent pas être calculés sur vos soumissions mais seulement à la fin de la journée.
Ce document a été traduit de LATEX par HEVEA