2iè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)

15 juin 2010

Déroulement de la journée

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

Les questions peuvent être traitées de manière indépendante. Cependant, le code écrit pour une question peut être utile pour les suivantes.

Les questions sont corrigées automatiquement et en temps-réel pendant toute la durée de l'épreuve. Pour cela, vous allez soumettre une archive pour chaque question à un serveur. Chaque archive contient un ou plusieurs fichiers source ainsi qu'un script permettant de fabriquer un exécutable. La page de livraison et les fonctions de tests de vos soumissions sont hébergées sur le site de Paracamplus.

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

Pour vous familiariser avec ce processus de livraison, un exercice d'entraînement est à réaliser avant le début de l'épreuve. Vous y accèdez en utilisant le bouton

Vous retrouverez ce bouton tout au long du sujet.

Blokus Duo

Votre objectif est d'écrire un programme qui joue à Blokus Duo. Il s'agit d'un jeu de plateau à deux joueurs. Les deux joueurs s'affrontent sur une grille carrée de taille 14x14 et disposent chacun de 21 pièces comprenant chacune entre 1 et 5 blocs. Les joueurs posent chacun une pièce à tour de rôle, jusqu'à ce qu'il ne soit plus possible de poser une pièce. Le vainqueur est celui qui a couvert le plus grand nombre de cases.

Pour poser une pièce, il faut respecter les deux règles suivantes :

  1. la pièce posée doit occuper des cases libres de la grille ;
  2. elle doit être en contact avec une ou plusieurs pièces du même joueur, par des coins et par des coins uniquement. En revanche, elle peut être en contact avec des pièces du joueur adverse de quelque manière que ce soit.
De plus, la première pièce de chaque joueur doit occuper une case particulière.

Les pièces

Les 21 pièces de chaque joueur sont les suivantes :

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21

Elles peuvent être tournées ou retournées arbitrairement avant d'être posées. Par exemple, la pièce numéro 9 peut être posée de 4 manières différentes, qui sont

               

D'une manière générale, les pièces peuvent être posées de 1, 2, 4 ou 8 manières différentes selon les cas. L'ensemble des 91 façons différentes de poser une pièce sur la grille est décrit dans ce fichier : pieces.txt. Le format de ce fichier est le suivant. Une première ligne identifie la pièce et donne ses dimensions, sous la forme suivante : 

ic h w
à savoir un entier i sur un ou deux chiffres, une lettre c entre a et h, un espace, un entier h sur un chiffre h, un espace et un entier w sur un chiffre. L'entier i indique le numéro de la pièce (entre 1 et 21). La lettre c indique son orientation. L'ensemble ic est appelé l'identifiant. Le chiffre h indique la hauteur et le chiffre w la largeur. Ainsi,9b 2 3 correspond à une orientation particulière de la pièce 9, de hauteur 2 et de largeur 3.

Les h lignes suivantes contiennent chacune w caractères, et chaque caractère indique soit une case occupée (caractère #) soit une case inoccupée (caractère .). Ainsi, les trois lignes 

9b 2 3
##.
.##
définissent l'un des 4 placements possibles de la pièce 9, de hauteur 2 et de largeur 3.

Le placement d'une pièce sur la grille est défini de manière unique par l'identifiant de la pièce et les coordonnées x,y de la case en bas à gauche de la matrice rectangulaire définissant la pièce. Les coordonnées sur la grille sont des entiers compris entre 1 et 14, et la case (1,1) est située en bas à gauche. Ainsi la notation 

9b 6 3
représente le placement de la pièce 9b sur les quatre cases (6,4), (7,4), (7,3) et (8,3), c'est-à-dire

Question 1 : cases en contact avec une pièce

Dans cette première question, votre programme reçoit en entrée le placement d'une unique pièce sur la grille et indique en sortie la liste des cases qui sont en contact avec la pièce posée, par des coins uniquement.

L'entrée est constituée d'une unique ligne donnée sur l'entrée standard du programme. Elle contient le placement d'une pièce. La sortie contient une ligne par case, chaque ligne contenant deux coordonnées x et y séparées par un caractère espace.

Ainsi, sur l'entrée 

9b 6 3
votre programme doit produire sur la sortie standard les lignes 
5 3
5 5
8 5
9 4
9 2
6 2
ou toute autre permutation de ces mêmes lignes.

Vous devez rendre une archive contenant au moins un script de compilation compile.sh qui permet d'engendrer un exécutable de nom q1.

Votre programme sera testé successivement avec

Question 2 : une séquence de coups est-elle valable ?

Dans cette question, il s'agit de vérifier qu'une suite de coups joués par deux joueurs est valide. Le joueur qui joue en premier est appelé joueur 1 et le second joueur 2. Une suite de coups est valide si :
  1. les joueurs jouent à tour de rôle, en commençant par le joueur 1
  2. la première pièce posée par le joueur 1 doit occuper la case (1,1)
  3. la première pièce posée par le joueur 2 doit occuper la case (14,14)
  4. une pièce posée doit occuper des cases vides
  5. chaque joueur ne peut poser qu'une seule fois chacune de ses 21 pièces
  6. quand un joueur pose une pièce, elle doit être en contact avec une autre pièce du même joueur (sauf pour la première pièce), par les coins et par des coins uniquement ; en revanche, elle peut être en contact avec des pièces du joueur adverse de n'importe quelle manière
Dans cette question, la suite de coups ne mène pas nécessairement à la fin de la partie.

Votre programme reçoit sur son entrée standard la liste des coups joués. Chaque coup est donné sur une ligne, avec une alternance joueur 1 / joueur 2. Une ligne est de la forme 

9b 6 3
pour indiquer qu'une pièce (ici 9b) est posée à une certaine position (ici 6,3). Votre programme doit afficher sur la sortie standard soit le message 
valide
pour signaler que la suite de coups est valide, soit le message 
invalide
pour signaler qu'elle ne l'est pas.

Exemples : votre programme doit répondre valide pour les entrées 

2a 1 1
2b 13 14
11b 2 3
17b 10 11
et 
4d 1 1
1a 14 14
2a 2 3
et doit répondre invalide pour les entrées 
4b 1 1
et 
4d 1 1
1a 14 14
4c 2 3

Vous devez rendre une archive contenant au moins un script de compilation compile.sh qui permet d'engendrer un exécutable de nom q2.

Votre programme sera testé successivement sur 18 entrées de un ou plusieurs coups, valides ou invalides. Chaque entrée vous rapportera 1 point.

Question 3 : coups possibles

Dans cette question, il s'agit de calculer l'ensemble des coups possibles pour le joueur 1 à un certain moment de la partie. Plus précisément, votre programme reçoit sur l'entrée standard une séquence de coups (supposés valides) correspondant au début d'une partie. Cette séquence contient un nombre pair de coups, ce qui signifie que c'est au joueur 1 de jouer. Votre programme doit alors afficher sur sa sortie standard la liste de tous les coups possibles pour le joueur 1, dans un ordre arbitraire, avec le format de la question précédente. Si aucun coup n'est possible, votre programme doit afficher la ligne 
passe

Par exemple, pour le début de partie suivant 

13a 1 1
7g 13 12
1a 3 1
2a 12 12
2a 3 4
13d 9 13
5a 4 2
19a 10 8
4c 1 5
9a 7 11
15b 4 4
11a 6 8
3a 7 1
4c 4 10
20c 3 7
16c 12 7
19f 7 4
3b 9 6
votre programme doit déterminer qu'il existe 142 coups possibles pour le joueur 1, qui sont (à permutation près) les suivants.

Vous devez rendre une archive contenant au moins un script de compilation compile.sh qui permet d'engendrer un exécutable de nom q3.

Votre programme sera testé sur 8 entrées différentes. Chaque entrée rapporte 3 points.

Question 4 : programmer un joueur

Dans cette dernière question, vous devez programmer un joueur qui affrontera d'autres joueurs. Votre programme reçoit sur sa ligne de commande un unique argument lui indiquant s'il est le joueur 1 ou 2 ; cet argument est une chaîne de caractères d'exactement un caractère, valant "1" ou "2".

Lorsque c'est à votre programme de jouer, il doit afficher son coup sur sa sortie standard, ou la ligne passe s'il ne peut pas jouer.

Lorsque c'est à l'adversaire de jouer, votre programme reçoit sur son entrée standard le coup joué par l'adversaire (qui vaut éventuellement passe).

Votre programme dispose de 20 secondes de calcul pour l'intégralité de son exécution. Le temps passé dans le programme adversaire n'est pas compté. Si votre programme dépasse cette limite de temps avant la fin de la partie, il perd la partie.

Votre programme n'a pas à se préoccuper de détecter la fin de partie.

Vous devez rendre une archive contenant au moins un script de compilation compile.sh qui permet d'engendrer un exécutable de nom q4.

Votre programme affrontera successivement deux adversaires de force croissante. Au total, 4 parties seront jouées (une en tant que joueur 1 et l'autre en tant que joueur 2 pour chaque adversaire).

Vous pouvez gagner :

Tournoi de classement

Les programmes répondant à la question 4 s'affronteront dans un tournoi, pour déterminer le vainqueur de ce concours.

Dans un affrontement de deux joueurs, un temps maximal de réflexion est alloué à chaque joueur (comme dans une partie d'échec). Pour chaque joueur, on ne décompte que le temps passé entre le moment où l'adversaire a joué et celui où le joueur donne sa réponse.