Structures de données

La bradgote ressemble à la fois à la belote, au bridge et au tarot.

La bradgote se joue à 4 joueurs appelés respectivement Nord, Est, Sud et Ouest.

🂨🃋🂡🂫🃔
Nord
🃖🂭🃅🃆🃇Ouest Est🂱🃁🃂🃙🂩
Sud
🃚🂮🂻🃈🃑

La bradgote se joue avec un jeu de 52 cartes, que l'on distribue au début du jeu, 5 par 5, aux joueurs. Les 5 cartes d'un joueur s'appellent sa main. Les joueurs jouent par camp de 2 joueurs. Nord et Sud constituent un camp, Est et Ouest l'autre camp. Nord commence et Sud met ses cartes sur la table, face en l'air, avant de jouer. Nord pose une carte sur la table, puis Est en pose une (si possible de la même couleur) et ainsi de suite jusqu'à ce que 4 cartes soient sur la table. Celui qui a posé la carte de la plus haute valeur (à condition que ce soit dans la bonne couleur) remporte la levée (les 4 cartes) et pose la première carte de la levée suivante. Les cartes rapportent des points ainsi :

Pour connaître les points rapportés à un camp par la levée, on additionne les points des 4 cartes. La carte gagnante de la levée est celle qui rapporte le plus de points, tant qu'elle est de la bonne couleur. On suppose que Nord pose la première carte. Si Est n'a pas la couleur demandée, il a intérêt à poser une carte rapportant le moins de points possible, alors que si Sud n'a pas la couleur demandée, il a au contraire intérêt à poser une carte rapportant beaucoup de points puisque Nord est dans son camp.

On appelle valeur d'une carte le nombre qui est inscrit dessus, ou le mot Roi, Dame, Valet ou As. La couleur d'une carte est l'un des mots Carreau, Coeur, Pique ou Trefle.

I/ Structure en C

Chaque carte est définie par une couleur (de carreau à trefle) et une valeur (de as à roi). Une possibilité pour modéliser une carte en C est donc de prendre un tableau de deux chaînes de caractères, l'une pour la couleur et l'autre pour la valeur.

On commence donc par

#include <stdio.h>
#include <string.h>

On peut aussi prendre deux pointeurs, l'un pointant vers la couleur, et l'autre vers la valeur. Ceci évite d'avoir à se rappeler si c'est la couleur d'abord ou la valeur d'abord, et facilite ainsi le débogage.

1) Définition d'une carte

Les deux pointeurs nommés respectivement valeur et couleur, sont regroupés dans une structure :

typedef struct {
    char *valeur;
    char *couleur;
} carte;

2) Construction d'une carte

Pour construire une carte, on crée un pointeur p qui va pointer successivement vers chacun des champs de la structure :

carte c1, *p;
p = &c1;
p -> couleur = "carreau";
p -> valeur = "roi";
printf("%s de %s\n",c1.valeur,c1.couleur);

On a alors l'affichage

roi de carreau

3) Calcul des points

Comme il y a plusieurs valeurs donnant le même nombre de points (1 point), on réserve leur examen à la fin. L'algorithme consiste donc à

%3 valeur valeur roi roi valeur->roi dame dame roi->dame 5 5 roi->5 valet valet dame->valet 4 4 dame->4 2 2 valet->2 1 1 valet->1

En C cela donne

char points (carte *c) {
    if (strcmp(c -> valeur,"roi") == 0) { return 5; }
    if (strcmp(c -> valeur,"dame") == 0) { return 4; }
    if (strcmp(c -> valeur,"valet") == 0) { return 2; }
    return 1;
}

Avec

carte c2;
p = &c2;
p -> couleur = "pique";
p -> valeur = "valet";
printf("%s de %s",c2.valeur,c2.couleur);
printf(", vaut %u points\n",points(p));

on a

valet de pique, vaut 2 points

II/Jeu de cartes en Ocaml

1) Type somme

En Ocaml, un type somme est un choix entre plusieurs types différents. Par exemple, si Carreau, Coeur, Pique et Trefle sont des types, alors le type couleur défini par

type couleur = 
    | Carreau 
    | Coeur 
    | Pique 
    | Trefle 
    ;;

est un type somme.

2) Type polymorphe

Les types Roi, Dame, Valet et As ne sont pas des entiers (l'as aurait pu être l'entier 1), mais on considère les types 2, 3, 4, 5, 6, 7, 8, 9 et 10 comme des entiers. Ou comme un type Nombre qui est entier. Le type valeur défini par

type valeur = 
    | Roi
    | Dame
    | Valet
    | As
    | Nombre of int
    ;;

est donc un type polymorphe (en grec cela signifie qu'il peut prendre plusieurs formes).

3) Type produit

Une carte est donnée par une couleur et une valeur, on peut donc la modéliser par un couple formé d'une ccouleur et une valeur, qui est de type couleur*valeur. Mais on va ici choisir un type produit qui ressemble un peu à un struct de C :

type carte = { v : valeur ; c : couleur } ;;

Le 🂺 s'obtient donc en évaluant l'expression

{ v = Nombre 10 ; c = Coeur };;

et la 🂽 en évaluant l'expression

{ v = Dame ; c = Coeur }

III/ Filtrage par motif

1) Points des cartes

Les points rapportés par une carte à la bradgote ne dépendent pas de leur couleur, mais seulement de leur valeur. On a donc affaire à une fonction points_valeur : valeur -> int telle que

La fonction qui, à une valeur de carte, associe le nombre de points que rapporte la carte à la bradgote, a donc pour diagramme sagittal :

%3 roi roi 5 5 roi->5 dame dame 4 4 dame->4 valet valet 2 2 valet->2 10 10 1 1 10->1 9 9 9->1 8 8 8->1 7 7 7->1 as as as->1

2) filtrage par motif

On reproduit presque à l'identique ce diagramme sagittal avec

let points_valeur v =
  match v with
    | Roi -> 5
    | Dame -> 4
    | Valet -> 2
    | _ -> 1
;;

En anglais, to match veut dire « adapter : on joue à la boîte de formes où il s'agit d'essayer de brancher un polygone dans un trou adapté.

3) Points d'une carte

Maintenant qu'on connaît les points à partir de la valeur de la carte, il suffit pour connaître les points d'une carte, de faire

let points c = 
    points_valeur c.v
    ;;

ce qui définit la fonction points : carte -> int. Avec

let t = { v = Dame ; c = Coeur };;

print_int (points t);;

on obtient alors

4