Programmation fonctionnelle avan-

cée
L3 Info, L3 Mag Info

TP 2
1 Le Solitaire
Le but du TP est de coder des fonctions utilitaires permettant de jouer à une variante du Solitaire. Ce
jeu (aussi appelé Klondike en anglais) est un jeu utilisant 52 cartes disposées de façon particulière. Quatre
zones, initialement vides sont réservées pour les cœurs, piques, trèfles et carreaux. À côté d’eux, la défausse
(initialement vide) et la pioche consistent en deux tas de cartes. La cartes de la pioche sont face cachée.
Enfin, 7 piles de cartes sont disposées sous les zones de rangement. Initialement les tas ont respectivement
0, 1, 2, . . ., 6 cartes cachées et 1 carte visible. La figure 1.a montre une configuration initiale de notre jeu.
Dans cette figure, les carrés pointillés représentent des emplacements vides (sans carte). De plus, afin de
simplifier les fonctions d’affichage, les piles de cartes sont affichées horizontalement et précédées de leur
numéro (plutôt que verticalement). Le but du jeu est de ranger toutes les cartes, dans l’ordre sur chacun
des quatre emplacements réservés pour chaque couleur (une couleur ici est cœur, pique, trèfle ou carreau,
pas noir ou rouge). Les règles sont très simples.
On dit qu’une carte est directement accessible si elle est soit sur la défausse, soit le plus à gauche de l’une
des piles. Dans la figure 1.f, les cartes directement accessibles sont : le 9 de trèfle (sur la défausse), le Roi de
pique, Valet de trèfle, 3 de carreau, 3 de pique, Roi de trèfle, 8 de carreau et 9 de carreau.
Mouvements des cartes :
— on peut déplacer un As sur la zone de rangement vide de sa couleur
— si une carte est directement accessible et qu’elle est immédiatement supérieure à la carte au sommet
de la zone de rangement de sa couleur, alors on peut l’y ranger (i.e. si la dernière carte posée sur la
zone des cœurs est le 10 et que le Valet de cœur est accessible, on peut le ranger au dessus du 10. Par
contre si la dernière carte posée sur la zone des cœurs est le 8 et que le Valet de cœur est accessible,
on ne peut pas le ranger car il ne suit pas immédiatement le 8).
— on peut déplacer la carte au sommet de la zone de défausse pour la mettre sous une carte visible
des piles numérotées, si elle est de valeur directement inférieure et de couleur alternante (i.e. on peut
placer un 7 de pique sous un 8 de cœur ou un 8 de carreau)
— on peut déplacer toute une suite de cartes d’une pile à une autre, la carte la plus en dessous devant
être directement inférieure et de couleur alterante à la carte de destination. Autrement dit, on peut
déplacer une carte non directement accessible d’une pile si on déplace aussi toutes les cartes en dessous.
— enfin, si une des 7 piles est vide, on peut uniquement placer un Roi dessus.
À partir de la figure 1.a, on peut par exemple ranger l’As de cœur qui est directement accessible sur
la pile numéro 5, ce qui donne la configuration de la figure 1.b, dans laquelle la carte est rangée et le 9 de
carreau qui se trouvait en dessous est dévoilé.
Ensuite, on peut choisir de déplacer le 3 de carreau (pile 2) sous le 4 de pique (pile 4). On obtient la
figure 1.c. Le Valet de trèfle devient ainsi visible. On peut ensuite déplacer le 3 de carreau et le 4 de pique
sous le 5 de cœur (pile 3). Le résultat de cette opération est donné à la figure 1.d.
On peut ensuite déplacer le 9 de carreau (pile 5) sous le 10 de pique (pile 7), comme dans la figure 1.e.
À ce stade, on se retrouve bloqué, on va donc choisir de piocher (il est toujours possible de piocher même
quand on peut jouer autre chose), ce qui révèle 9 de trèfle dans la zone de défausse.
On procède ainsi, en piochant lorsque l’on est bloqué jusqu’à avoir réussi à ranger toutes les cartes (ou
à abandonner car on se retrouve complètement bloqué). Si à un moment la pioche est vide, on retourne la
défausse pour en faire une nouvelle pioche.
Le programme fourni en exemple se lancer simplement avec la commande :

./solitaire_ref.exe

Une fois le programme lancé, la partie commence. Les commandes possibles sont :
1
Début de partie. Carte A♥ rangée.
∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷
A♥ ∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷
1: K♠
1: K♠
2: 3♦
2: 3♦
3: 5♥
3: 5♥
4: 4♠
4: 4♠
5: A♥
5: 9♦
6: 8♦
6: 8♦
7: 10♠
7: 10♠
Saisir une commande : R5
Saisir une commande : D24

(a) Une configuration initiale. (b) On a rangé l’As de cœur.

Carte(s) déplacées de la pile 2 à la pile 4. Carte(s) déplacées de la pile 4 à la pile 3.

A♥ ∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷ A♥ ∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷
1: K♠ 1: K♠
2: J♣ 2: J♣
3: 5♥ 3: 3♦ 4♠ 5♥
4: 3♦ 4♠ 4: 3♠
5: 9♦ 5: 9♦
6: 8♦ 6: 8♦
7: 10♠ 7: 10♠
Saisir une commande : D45 Saisir une commande : D57

(c) On a déplacé le 3 de carreau. (d) On a déplacé le 3 et le 4 sous le 5.

Carte(s) déplacées de la pile 5 à la pile 7. Nouvelle carte piochée.

A♥ ∷∷∷ ∷∷∷ ∷∷∷ ∷∷∷ A♥ ∷∷∷ ∷∷∷ ∷∷∷ 9♣
1: K♠ 1: K♠
2: J♣ 2: J♣
3: 3♦ 4♠ 5♥ 3: 3♦ 4♠ 5♥
4: 3♠ 4: 3♠
5: K♣ 5: K♣
6: 8♦ 6: 8♦
7: 9♦ 10♠ 7: 9♦ 10♠
Saisir une commande : P Saisir une commande :

(e) On a déplacé le 9 sous le 10. (f) On a pioché.

Figure 1 – Plusieurs étapes du solitaire

2
 — P pour piocher une carte ;
— Ri pour ranger la carte se trouvant en i. Ce dernier peut être soit la lettre D pour indiquer que l’on
veut ranger la carte se trouvant dans la défausse sur son emplacement finale, soit un entier entre 1 et
7 pour indiquer que l’on veut ranger la carte se trouvant le plus à gauche de la pile indiquée
— Dij pour déplacer le plus de cartes possible entre i et j. Ici, i est soit D soit un entier de 1 à 7 et j est
un entier de 1 à 7.
— Q pour quiter.
Ainsi, pour obtenir les figures 1.a 1.f, on entre successivement les commandes :
— R5 (on range l’As se trouvant dans la pile 5)
— D24 (on déplace le 3 de la pile 2 sous le 4 de la pile 4)
— D43 (on déplace le 3 et 4 de la pile 4 sous le 5 de la pile 3)
— D57 (on déplace le 9 de la pile 5 sous le 10 de la pile 7)
— P (on pioche)

2 Structure du programme et méthode de travail

Attention si vous ne travaillez pas sur une machine du PUIO, allez lire le paragraphe en fin d’énoncé.

2.1 L’archive Zip

L’archive contient les fichiers suivants :
solitaire_defs.ml Un fichier contenant uniquement la définition de types OCaml pour représenter les cartes
et la configuration du jeu, ainsi qu’une fonction et plusieurs variables globales. utilitaires. Il convient
de lire attentivement les définitions de types, mais il ne faut absolument pas modifier ce fichier.

3
 1 type valeur = Valeur of int | Valet | Dame | Roi
2
3 type couleur = Coeur | Pique | Carreau | Trefle
4
5 type carte = { couleur : couleur ; valeur : valeur }
6
7
8 type jeu = { coeur : carte list;
9 pique : carte list;
10 carreau : carte list;
11 trefle : carte list;
12 piles : (carte list ∗ carte list) list;
13 defausse : carte list;
14 pioche : carte list }

Les cartes sont représentées comme lors des exemples du cours : une carte est un produit nommé
à deux composantes (la valeur et la couleur). Le type valeur est un type sommes contenant trois
constantes (Valet, Dame, Roi) et un constructeur avec argument représentant les cartes numériques.
Le type couleur est composé de quatre constantes.
Dans la suite on appelera un tas de carte une simple liste de cartes. Une pile de cartes est par contre
représenté par une paire de listes de cartes : les cartes visibles et les cartes cachées. Le type jeu est un
produit nommé qui représente une configuration de jeu. Les champs coeur, pique, carreau, treffle
contiennent des tas de cartes (carte list) qui sont les zones de rangement. Les champs defausse et
pioche représentent ces deux tas du jeu. Enfin, le champ piles représente les 7 piles de cartes. Le
type de ce champs est (carte list ∗ carte list) list, c’est donc une liste de paires. Cette liste
sera de taille 7 en pratique.
Enfin, le fichier définit une fonction :
32 let string_of_carte c = ...

Cette fonction, du type carte -> string renvoie la chaîne de caractère permettant d’afficher la carte
convenablement, avec les couleurs. Par exemple, effectuer
[Link] "%s\n"(string_of_carte { valeur=Roi; couleur=Coeur })
affichera :
K♥
Le fichier contient enfin deux variables globales :
49 let carte_cachee = ...
50
51 let zone_vide = ...

La première est une chaîne de caractères correspondant à « » représentant une carte retournée
et la seconde contient une chaîne correspondant à « ∷∷∷ » représentant un tas de cartes vide.
solitaire_defs.cmi, solitaire_defs.cmo, help_solitaire.cmi et help_solitaire.cmo : des fichiers com-
pilés (binaires) contenant le code du corrigé. Il ne faut ni effacer ni modifier ces fichiers. Si cela
vous arrive, il faudra les récupérer depuis l’archive originale. Attention, si vous décompressez de nou-
veau l’archive, les fichiers existants seront écrasés. Il convient donc de faire une copie de votre fichier
[Link] contenant vos réponses avant de décompresser de nouveau l’archive, sinon vous risquez
de tout perdre !
[Link] : le fichier que vous devez compléter contenant la logique du jeu (détection déplacement de
cartes, affichage du jeu).
[Link] : le programme principal qui utilise votre fichier [Link]. Il gère les saisies de l’utilisateur,
l’initialisation, . . .. Vous pouvez le lire, mais ne devez pas le modifier.
Makefile : un fichier de configuration pour la commande make qui va compiler votre programme.

4
 2.2 Compilation et tests
Pour compiler votre programme, vous ne devez pas appeler ocamlc directement mais utiliser la commande
make dans le répertoire où se trouve votre code :
— la commande make écrite seule dans le terminal, compile votre fichier [Link] et produit une fi-
chier exécutable [Link]. Vous pouvez tester votre programme en le lançant (./[Link])
et le comparer au programme de référence (./solitaire_ref.exe).
Lorsque vous lancez ces programmes, le choix des cartes est aléatoire, ce qui peut compliquer les tests.
Si vous les lancer avec l’otpion -norandom comme ceci :
./solitaire_ref.exe -norandom
alors le déroulement de la partie sera le même que celui indiqué à la figure 1 à chaque fois, ce qui peut
vous permettre de reproduire une même partie entre le programme de référence et le votre.
— la commande make test lance un interpréteur OCaml avec les fonctions de votre fichier [Link]
chargées à l’intérieur. Vous pouvez donc directement appeler vos fonctions pour les tester. Par exemple,
pour tester la fonction lance_de : unit -> int de la question 1 :
make test

OCaml version 4.14.1

# init_jeu;;
- : unit -> Solitaire_defs.jeu = <fun>
# let jeu = init_jeu ();;
val jeu : Solitaire_defs.jeu = ...
# affiche_jeu jeu;;
...

Le programme compile votre fichier et lance l’interprète OCaml (ces commandes sont affichées dans le
terminal). Vous pouvez ensuite saisir des expressions OCaml. Vous pouvez quitter l’interpréteur avec
CTRL-D.

2.3 Utilisation du corrigé

Afin que le TP ne soit pas un exercice à tiroir (où rater la première question implique de rater la suite),
un fichier binaire help_solitaire.cmo est fourni. Il contient le corrigé de toutes les fonctions. Vous ne
pouvez évidemment pas retrouver le code source correspondant, mais vous pouvez l’utiliser. Le début du
fichier [Link] à compléter est comme suit :
1 open Solitaire_defs
2 ∗)
3
4 let affiche_tas tas =
5 ( ∗ Commentez la ligne ci- dessous et mettez votre code.
6 Si votre code ne fonctionne pas , commentez le et remettez cette ligne . ∗ )
7
8 failwith "todo"
9 ;;
10
11 ( ∗ Q2
12 affiche_piles : (carte liste ∗ carte list) list -> unit
13 Affiche la liste des piles. Chaque pile est précédée de son numéro , en
14 commen çant par 1. Pour chaque pile (lvisibles , lcachees ) on affiche :
15 - son numéro , suivi de deux points ":"
16 - les cartes de lvisibles , chacune suivie d’un espace . Comme précé demment
17 les cartes sont à convertir avec string_of_carte .
18 - pour chaque carte de lcachees , on affiche la chaine contenue dans

À la ligne 1, l’instruction open Solitaire_defs permet d’inclure les définitions du fichiers solitaire_defs.ml
à cet endroit. Vous pouvez donc considérer que les types jeu, carte, valeur ainsi que toutes les variables
5
du fichier sont visibles ici.
La fonction affiche_tas (ainsi que toutes les suivantes) appelle directement la fonction du corrigé du
même nom. Vous devez évidemment remplacer le corps de la fonction par votre propre code, mais, si vous
êtes bloqué pour une fonction vous pouvez
— mettre votre code en commentaire. Il sera tout de même corrigé.
— revenir au code initial qui appelle le corrigé.
Cela vous permettra de ne pas rester bloqué sur une question et d’avancer aux questions suivantes sans être
pénalisés pour les suivantes.
Attention, ceci ne fonctionne que sur les machines du PUIO. Pour les étudiants utilisant leur machine
personnelle, vous pouvez télécharger l’archive _ext.zip sur la page du cours, et vous serez en mode un peu
dégradé (le corrigé pré-compilé n’est pas disponible).