3ième Journée Francilienne de Programmation

organisée par les universités Pierre et Marie Curie (Paris 6), Paris Diderot (Paris 7) et Paris-Sud 11 (Paris 11)

18 janvier 2011

Déroulement du concours

Les conditions générales des JFP sont décrites ici. Ce document présente l'énoncé des JFP 2011.

Les questions ont été conçues pour être résolues de façon incrémentale, à la fois dans la difficulté mais aussi dans l'ordre logique d'une histoire à raconter. Si elles ne peuvent, dans l'absolu, être traitées complètement indépendamment; il est tout à fait possible de sauter certaines d'entre elles et de répondre partiellement à d'autres. Le problème contient deux parties : des questions de cryptanalyse (messages chiffrés à découvrir) et une machine virtuelle à implémenter. Pour chacune des deux parties, le code utile à résoudre une question est généralement utile à résoudre les suivantes.

Les réponses aux questions peuvent être corrigées automatiquement et en temps-réel pendant toute la durée de l'épreuve comme indiqué sur la page principale. Toutefois on peut rappeler que pour cela, vous devez soumettre à un serveur une archive compressée (un fichier .tgz ou .tar.gz). Chaque archive doit contenir un ou plusieurs fichiers source ainsi qu'un script. Ce script est essentiel, il est le point d'entrée du processus de vérification. Il doit être à la racine de l'archive et doit porter le nom de compile.sh. De plus son exécution doit être possible à travers la commande bash < ./compile.sh. Son exécution sert généralement à déclencher une ou plusieurs compilations de programme fournis. Une fois son exécution terminée, le serveur commence ses propres tests...

La page de livraison et les fonctions de tests de vos soumissions sont hebergées sur la plateforme FW4EX de correction automatisée.

Attention : toute compilation, si compilation il y a, doit être des plus précautionneuse et ne produire aucune erreur ni aucun avertissement.

Le correcteur est automatisé, respectez attentivement les consignes données, car il est impitoyable. Lorsque vous soumettez quelque chose, le serveur vérifiera systématiquement toutes les étapes du concours, ainsi vous devez prendre soin à un moment donné, de ne rajouter que des fonctionnalités ou des programmes pour cette nouvelle étape en faisant attention à ce que ce qui fonctionnait auparavant continue à fonctionner.

CorrectWar, un CoreWar politiquement correct

CorrectWar une guerre impitoyable!

Pendant la préhistoire de l'informatique, déjà, les programmeurs barbus des années 60 aimaient s'amuser à confronter leurs talents au cours de joutes ludiques de programmation. Ainsi est né le CoreWar, un jeu développé par Victor A. Vyssotsky, Robert Morris Sr. et M. Douglas McIlroy dont le principe consistait à écrire des programmes se battant les uns contre les autres dans la mémoire de l'ordinateur.

Comment un programme pouvait-il donc en attaquer un autre? Eh bien, dans ces systèmes informatiques primitifs, le code des programmes évoluait dans la mémoire centrale, accessible à tous en lecture et en écriture! Il suffisait donc d'être le premier à écrire une instruction invalide dans le code machine de l'autre programme pour mettre à genoux son adversaire.

La violence de ces confrontations entre programmes a profondément choqué les organisateurs des JFPs si bien qu'ils en ont conçu une version pacifiste, juste et politiquement correct du CoreWar. Cette nouvelle moûture a été appelée CorrectWar.

Votre objectif est d'écrire une machine virtuelle dans laquelle des batailles de CorrectWar pourront se dérouler dans un respect scrupuleux de l'éthique inter-programmes (cf. «How to make your programs friendly to others?», Proceedings of the 3rd ICPE, Intergalactic Conference on Programming Ethics, Alpha Centauri, Feb. 29th 2010). Les questions du sujet fournissent une description progressive de la machine qui sera testée au fur et à mesure de votre développement. À notre grande déception, et malgré nos intenses réflexions sur les règles du jeu, quelqu'un a réussi à écrire un programme tricheur qui parvient à prendre malicieusement le contrôle de ses adversaires. Saurez-vous, dans la dernière question de ce sujet, détecter ce type de comportement inacceptable et donc ces programmes indignes de participer à CorrectWar ?

Certaines choses ne devant pas être révélées trop facilement au grand public (la guerre, même propre, est souvent une affaire de secrets), il vous est demandé, en préliminaire, de décrypter certains messages afin de pouvoir avancer complètement.

Chut!

Question -1 : Jules est un petit cachotier

L'histoire veut qu'un célèbre empereur romain prénommé Jules et désireux de transmettre secrètement des messages à ses troupes ait utilisé un moyen de chiffrement utilisant une permutation circulaire de l'alphabet. Par exemple, le chiffre de Jules élémentaire (de distance 1) transforme A→B, B→C, ..., Y→Z et Z→A. Celui de distance 2 transforme A→C, B→D, ..., X→Z, Y→A et Z→B.

On vous propose d'étendre ce système de chiffrement à celui du code ASCII. L'extension consiste alors à ne faire tourner que la suite des caractères « imprimables » du code ASCII, à l'exclusion du caractère d'espacement, soit tous les caractères du code 33 ASCII(33)=! jusqu'au code 126 ASCII(126)=~, inclus. Pour tous les autres caractères AUCUNE transformation ne doit être appliquée, autrement ces caractères restent identiques à eux-même.

Pour vous mettre en jambes, il vous est demandé d'écrire un programme (dans le langage de votre choix) dont l'exécutable devra s'appeller impérativement jules (et rappellez-vous être un des produits de l'exécution de compile.sh) et qui devra permettre de :

déchiffrer tout message lu dans un fichier de nom message.crypt
et d'écrire le résultat de ce décodage dans un fichier de nom message.clair.

La permutation circulaire de ASCII(33) à ASCII(126) que vous devez utiliser est de distance 47 (donc ASCII(33)→ASCII(33+47), etc). On notera que cette permutation circulaire appliquée à elle-même est la permutation identité (donc une involution). Et donc, l'algorithme de déchiffrement est aussi celui de chiffrement.

Afin de mettre au point votre programme, le texte chiffré suivant est fourni :

v6?:2= 42 >2C496 DFA6C 3:6?P

et correspond au text clair suivant :

Genial ca marche super bien!

Si votre programme est au point, le résultat de votre soumission vous renverra le résultat du déchiffrement (par votre programme) d'un texte que nous gardons jalousement par-devers nous. Ce texte contiendra des informations très utiles pour résoudre les questions suivantes.

Pour vous mettre, l'eau à la bouche, nous vous donnons le début de ce texte chiffré mystérieux :

yF=6D 6E q=2:D6 G@FD D@F92:E6?E F?6 3@??6 2??66 a_`` 6E

et le début de son déchiffrement :

Jules et Blaise

Mais attention, car auparavant, votre programme sera soumis à un impitoyable test consistant à tester que le déchiffrement de n'importe quel texte est possible : nous allons tester votre déchiffreur sur un fichier contenant, dans l'ordre, les caractères de ASCII(0) à ASCII(127).

Résoudre cette question vous rapportera 1 point et une surprise...

Question 0 : À l'aise Blaise

Vous ne pensiez pas vous en sortir ainsi, non ? Le système précédent est bien trop simple... C'est pourquoi on vous demande d'utiliser un système de chiffrement/déchiffrement construit au XVI-ième siècle par un certain Blaise.

Le chiffrement/déchiffrement repose sur le mécanisme utilisé précédemment : chaque caractère est chiffré par un chiffrement similaire à celui de la question précédente. La différence est si que pour chaque lettre du texte à chiffrer l'algorithme est bien le même, la distance utilisée est différente. Les distances utilisées sont données sous la forme d'une suite de valeurs (cette suite est ce que l'on appelle la clé secrète), i.e. une liste de nombres de longueur l (le saviez-vous ?). Notons la c₁ c₂ ... c_l.

Pour le chiffrement, c₁ représente la distance à appliquer dans l'algorithme de chiffrement du premier caractère du texte, c₂ au second, etc. Si la clé est épuisée, on reprend depuis le départ, ainsi le c₁ représente la distance à utiliser pour le chiffrement du l+1-ième caractère du texte s'il existe, c₂ au l+2-ième, etc.

Le déchiffrement procède à l'inverse (au lieu de faire tourner l'alphabet vers la droite on le fait tourner d'autant vers la gauche).

Voici un exemple qui devrait vous aider à mieux comprendre encore.

si la clé est 1 2 3;
si le message à coder est AAA BBB;
(d=1) le codage du premier A est A+1→B donc B;
(d=2) le codage du second A est A+2→B donc C;
(d=3) le codage du troisième A est A+3→B donc D;
(d=1) le codage de <espace> est <espace>→<espace> donc B; attention ici la distance est bien 1, mais le caractère ne doit pas être encodé puisqu'il ne fait pas partie des caractères à modifier;
(d=2) le codage du premier B est B+2→D donc D;
(d=3) le codage du second B est B+3→E donc E;
(d=1) le codage du troisième B est B+1→C donc C;
le message chiffré et ensuite à déchiffrer est donc BCD CDB;
(d=1) le décodage de B donne B-1→A donc A;
(d=2) le décodage de C donne C-2→A donc A;
(d=3) le décodage de D donne D-3→A donc A;
(d=1) le décodage de <espace> donne <espace>→<<espace> donc <espace>; attention ici la distance est bien 1, mais le caractère ne doit pas être encodé puisqu'il ne fait pas partie des caractères à modifier;
(d=2) le décodage de D donne D-2→B donc B;
(d=3) le décodage de E donne E-3→B donc B;
(d=1) le décodage de C donne C-1→B donc B;
le message après décodage est AAA BBB.

Voici deux exemples de décodage à obtenir afin de tester votre programme :

Clé :
```
1 2 3
```
Texte chiffré :
```
Cqqkqxs
```
Texte clair :
```
Bonjour
```

Clé :

40 78 4 5

Texte chiffré :

j_r -Q f \+f3b i/ jt8Sxn9^rj< ez `sn6 xt?d h+|23

Texte clair :

Bon ca a l'air de fonctionner au poil tout ca...

Il vous est demandé d'écrire un programme (dans le langage de votre choix) dont l'exécutable devra impérativement s'appeler deblaise et qui devra permettre de :

déchiffrer à l'aide de la clé lue dans un fichier de nom cle.txt,
le message lu dans un fichier de nom message.crypt
et d'écrire le résultat du décodage dans un fichier de nom message.clair

La clé devra être représentée dans le fichier cle.txt comme une suite de nombres humainement lisibles et séparés par un espace comme par exemple :

1 2 3 12 34

Attention : votre soumission devra utiliser la bonne clé, mais ça vous le savez déjà non ?

Résoudre cette question vous rapportera 1 point et une surprise...

La machine virtuelle

La spécification de la machine virtuelle du CorrectWar vous est donnée dans le fichier suivant. Les questions 1 et 2 vont vous guider dans la réalisation de cette spécification. Lisez-là avec attention car elle fourmille de détails croustillants...

Question 1 : Initialisation de la machine virtuelle

Pour décrire l'état initial d'une partie de CorrectWar, on fournit la liste des programmes dans un fichier binaire organisé selon un schéma très précis.

Le codage des nombres

Pour décoder les données contenues dans ce fichier, il faut savoir tout d'abord que chaque mot de 16 bits y est représenté par deux octets successifs. Le premier correspond aux bits de poids fort et le second correspond aux bits de poids faibles. Par exemple, le mot de 16 bits 1111111100101010 (soit le nombre -24 en base 10) sera représenté par l'octet 11111111 suivi de l'octet 00101010. (Ce type de codage est connu sous le nom de big-endian ou grand/gros-boutiste/boutien en français et parfois même grand indien.)

Le codage des listes

Ensuite, il faut aussi savoir que les données correspondant à une liste de lg éléments (lg sera toujours strictement plus petit que 32768) commencera toujours par cet entier lg codé sur 16 bits. Dans la suite la liste

n₁,
  ... n_lg

sera représentée par [lg; n₁; ... n_lg]. Il suffira donc d'appliquer lg fois la fonction de décodage des éléments pour décoder la totalité de la liste. Par exemple, la liste de 2 mots de 16 bits (en décimal -214, 42) (soit codés en binaire

1111111100101010,
  0000000000101010

) sera représentée par

[0000000000000010;
  1111111100101010; 0000000000101010]

et donc la séquence d'octets (ici écrits en binaire) suivante :

00000000 00000010 11111111 00101010 00000000 00101010
octet 0  octet 1  octet 2  octet 3  octet 4  octet 5

Le codage des programmes CorrectWar

Vous êtes maintenant fin prêts pour décoder le fichier binaire puisqu'il contient une « liste de description de joueurs ». Au passage, on sait qu'il n'y a au plus que 254 joueurs.
Une description de joueur est elle-même une « liste de fragments de programme ».
Un fragment de programme est une position suivie d'une « liste d'instructions ».
Les positions sont des entiers 16 bits signés.
Le format des instructions des programmes est décrit dans la spécification de la machine.

Ainsi, par exemple, la partie de 2 joueurs telle que

le joueur 1 ne contient qu'1 seul fragment de code 21, 0 en position 42 ,
le joueur numéro 2 contient 2 fragments de code : le premier -1, -2 en position 128 et le second 5, 4, 78 en position 256 ;

est décrit par la liste :

[2;
   [1; [42; [2; 21; 0]]];
   [2; [128; [2; -1; -2]]]; [256; [3; 5; 4; 78]]]
]

laquelle est représentée par la séquence d'octets suivante :

00000000 00000010 00000000 00000001 00000000 00101010
00000000 00000010 00000000 00010101 00000000 00000000
00000000 00000010 00000000 10000000 00000000 00000010
11111111 11111111 11111111 11111110 00000001 00000000
00000000 00000011 00000000 00000101 00000000 00000100
00000000 01001110

Ma première machine virtuelle...

Pour cette question, vous devez écrire un programme nommé vm1 qui ouvre un fichier binaire nommé jeu, décode son contenu et initialise la mémoire de la machine virtuelle en plaçant chaque fragment de code à sa position initiale. Il enregistre enfin le contenu de la mémoire dans un fichier texte humainement lisible et de nom memoire.txt.

L'affichage de la mémoire

Le format de ce fichier est le suivant :

chaque mot de 16 bits de la mémoire est affiché sur une ligne distincte;
sur chaque ligne apparaît d'abord l'adresse du mot. Cette adresse doit être codée en base 10 sur 5 caractères avec '0' comme caractère de remplissage. Ainsi la valeur 123 doit être affichée comme 00123;
ensuite un espace;
pour finir la valeur du mot de 16 bits comme entier non signé doit être affichée en base 16 (avec les chiffres 0123456789abcdef) sur 4 caractères de long et '0' comme caractère de remplissage. Ainsi le mot binaire 0000101000000010 doit être affiché 0a02.

Le premier mot de la mémoire est numéroté 0. Par exemple, une mémoire de la forme [0; 42; 43; 44; ...] doit produire la sortie :

Si vous réussissez, cette question vous rapportera 5 points et...

Question 2 : Conception du processeur de la machine virtuelle

Il est maintenant temps d'implémenter le processeur de la machine virtuelle. À l'aide de votre spécification de machine virtuelle, écrivez un programme nommé vm2 qui initialise la mémoire à l'aide d'un fichier jeu, exécute les 100 premières instructions du premier fragment de code du premier joueur, puis produit un fichier memoire.txt représentant le contenu de la mémoire, comme dans la question précédente, et un fichier joueur.txt contenant la valeur des registres, de SP et de PC du premier joueur en base 10 séparés par des espaces.

Par exemple, si à la fin de l'exécution, les valeurs des 16 registres sont :

| r0  = -1  | r1  = 1   | r2  = 2   | r3  = 3   |
| r4  = 5   | r5  = 8   | r6  = 13  | r7  = 21  |
| r8  = 34  | r9 = 55   | r10 = 89  | r11 = 144 |
| r12 = 233 | r13 = 377 | r14 = 610 | r15 = 987 |

que le registre SP vaut 1024 et que le registre PC vaut 32 alors on produit le fichier joueur.txt :

-1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1024 32

Sachez que les tests que nous allons réaliser sont nombreux, mais progressifs. Vous pouvez donc utiliser le système de soumission à votre avantage en soumettant votre programme régulièrement même si l'intégralité de la machine virtuelle n'est pas implémentée. Les messages d'erreurs vous permettront alors de savoir si vous êtes sur la bonne voie. Dans l'ordre nous allons tester les groupes d'instructions suivants :

base et d'affectation (Nop, Mov, Load, Store, Mark)
arithmétique (Inc, Dec, Add, Sub, Mul, Div, Mod)
tests et sauts (Jmp, CJmp, IsZ, IsNZ, IsNeg, IsPos)
gestion de pile (Push, Pop)
appel de fonction (Gosub, Return)

Si vous réussissez, cette question vous rapportera 36 points et...

Les règles du jeu

Avant de commencer une partie, il faut initialiser les données de jeu de chaque joueur. Les informations suivantes sont associées à chaque joueur:

Un identificateur I qui est son indice d'apparition dans la liste des descriptions de joueurs fournie en entrée, numérotées à partir de 0.
Une marque qui est égale à (255 - I).

Une partie est une séquence de tours de jeu. Les tours sont numérotés à partir de 0.

À chaque tour, les joueurs exécutent, l'un après l'autre, une instruction , dans l'ordre de la liste donnée dans le fichier d'entrée.

Si un joueur écrit dans un fragment de code d'un autre joueur, il est disqualifié.

Si au tour d'indice T, le nombre d'occurrences de la marque d'un joueur en mémoire est strictement plus petit que "T / 50 - 50" alors ce joueur est hors-jeu. Notez que "/" est la division entière.

Le jeu s'arrête quand tous les joueurs sont plantés, disqualifiés ou hors-jeu.

Pour calculer le score des joueurs à la fin de la partie, on utilise les règles suivantes:

Si un joueur a été disqualifié alors son score est -100000.
Si un joueur s'est planté ou a été mis hors-jeu, alors son score final est égal au nombre de cases mémoires contenant sa marque auquel on retranche la somme des longueurs de ses fragments de code.

On classe les joueurs vis-à-vis de leur score final respectif. Si deux joueurs ont le même score alors c'est celui qui a l'identificateur le plus grand qui gagne.

Question 3: Vérifier le marquage

Dans un premier temps, nous allons commencer par tester si votre machine sait détecter si un joueur ne pose pas suffisamment de marques au cours du jeu. Pour cela, un unique joueur sera chargé en mémoire et votre programme devra détecter à partir de quel tour le joueur est hors-jeu.

Vous devez donc écrire un programme nommé vm3 qui charge un fichier nommé jeu, exécute 4096 tours de jeu puis produit un fichier hors-jeu.txt dans lequel on trouvera une unique ligne contenant l'indice du tour où le joueur est mis hors-jeu. Si un tel indice n'existe pas, alors le fichier devrait contenir la valeur -1.

Si vous réussissez, cette question vous rapportera 2 points.

Question 4: Savoir disqualifier

Dans cette question, nous allons vérifier que vous savez disqualifier les joueurs qui ne suivent pas les règles minimales du savoir-vivre militaire. Votre machine va charger une description de partie contenant le code de deux joueurs. Seulement, elle ne va exécuter que le code du second joueur pendant 1024 tours en s'assurant que ce dernier n'écrit jamais dans les zones de la mémoire où les fragments de code du premier joueur ont été chargés.

Vous devez donc écrire un programme nommé vm4 qui charge un fichier nommé jeu, exécute 1024 tours de jeu en exécutant exclusivement le code du premier joueur puis produit un fichier disqualifie.txt dans lequel on trouvera une unique ligne contenant l'indice du tour où le joueur est disqualifié. Si un tel indice n'existe pas, alors le fichier devra contenir la valeur -1.

Si vous réussissez, cette question vous rapportera 2 points et...

Question 5: Assemblage final

Pour cette question, après avoir initialisé la mémoire de la machine à l'aide du fichier nommé jeu, votre programme vm5 doit jouer la partie de CorrectWar puis produire dans un fichier resultat.txt, en les séparant par un espace, l'indice du dernier tour où il restait encore au moins un joueur en lice, le classement des joueurs en affichant l'identificateur puis le score de chacun d'eux. Par exemple, pour une partie se terminant au tour 1440401 où le joueur 0 a fait un score de 28757 et le joueur 1 un score de 30, votre programme doit afficher:

1440401 0 28757 1 30

Si vous réussissez, cette question vous rapportera 4 points et...

Question 6 : Détection d'un petit filou

Un programme très malin a été détecté. Comprenez le fonctionnement de ce petit filou et rédigez des explications dans un fichier le-filou.txt. Ce petit texte ainsi que l'élégance de votre code servira à départager les équipes éventuellement ex-aequo.