Aller plus loin

Durée : 7h30

Objectifs :

Manipuler des tableaux de données
Définir ses propres structures de données
Utiliser des fonctions et procèdures pour résoudre un problème
Appliquer l’ensemble des notions algorithmiques vu ce semestre

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

Compile sans warning
Obtient les résultats attendus
Avant de coder, il faut écrire un algo avec un papier et un stylo !

Exercice 0 : Avant de commencer

Depuis le terminal, ajouter l’arborescence suivante :

Déplacer vous dans le répertoire précédement créé

cd TD-plusLoin

Rappels

Pour compiler un programme, on utilise l’instruction suivante :

gcc -Wall exo.c -o nomExecutable

Pour executer un programme, on utilise l’instruction suivante :

./nomExecutable

Exercice 1 : Mastermind

Le Mastermind est un jeu de déduction dont le but pour le joueur est de deviner le code défini par un maître du jeu. Cette déduction se fait par étape successives de proposition retour du maître du jeu, dans la limite de 12. Le joueur place des pions de couleurs dans les trous de la première rangée immédiatement en face de lui. Le maître du jeu va donner des informations sur cette proposition de code. - Si l’un des pions correspond par sa position et sa couleur à un pion caché derrière l’écran, le maître du jeu l’indique en plaçant une fiche noire dans l’un des trous de marque, sur le côté droit correspondant du plateau ; - Si l’un des pions correspond uniquement par sa couleur, le maître du jeu l’indique par une fiche blanche dans l’un des trous de marque ; - S’il n’y a aucune correspondance, il ne marque rien.

La partie s’arrête lorsque le joueur découvre le code (le maître du jeu a posé quatre fiches noires) ou bien si au bout des 12 tentatives, le joueur n’a pas trouvé le code, alors le maître du jeu l’a tenu en échec. L’objectif ici est de programmer votre version de ce jeu, considérant que le rôle du maître du jeu est incarné par l’ordinateur et le joueur, l’utilisateur de votre programme.

Nous vous proposons d’implémenter la version simplifiée en terme de taille de code et de couleurs disponibles. Le code à deviner comportera 4 pions de couleur parmi 6 couleurs disponibles (jaune, bleu, rouge, vert, orange, violet). Certains pions peuvent être identiques. Nous utiliserons un plateau de jeu à 12 tentatives. Vous pourrez ajouter le comptage de points (cf détail des règles). Vous trouverez plus d’informations sur le jeu et le détail des règles ici

Créer un répertoire exo2 dans lequel on ajoutera le fichier exo1.c contenant le code suivant :

#include <stdio.h>
#include <stdlib.h>

/* exo 1 : un mastermind*/
int main(){
    return 0;
}

Objectif de l’exercice

NB : vous n’êtes pas obligé d’utiliser les mêmes emojis ou affichage que la vidéo ci-dessus !

Définir une énumération couleur qui défini l’ensemble des couleurs jouables (jaune, bleu, rouge, vert, orange, violet). N’oubliez pas la nomenclature en MAJUSCULES dans le code…
Définir une énumération placement qui défini l’ensemble des résultats de l’analyse (vide, blanc, noir ). N’oubliez pas la nomenclature en MAJUSCULES dans le code….

TIPS : enumeration

typedef enum semaine{
  LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI, SAMEDI, DIMANCHE
}semaine;

Vous pouvez laisser int dans la définition de la pile, car le programme assimilera LUNDI, MARDI, … par les entiers 0, 1 … jusqu’à 6.

Exemple :

Le code

printf("Je suis de le jour %d \n",LUNDI);
printf("Je suis de le jour %d \n",MARDI);
printf("Je suis de le jour %d \n",MERCREDI);

OUTPUT - Dans le Terminal

0
1
2

Écrire une procédure encode qui initialise aléatoirement les valeurs du tableau de code.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void encode(int codeSecret[4]);

Pour vous permettre de valider votre programme ou de valider vos prochains algorithmes, écrire une procédure afficheCode qui permet d’afficher le code défini précédemment.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void afficherCodeSecret(int codeSecret[4]);

Écrire une procédure initialiserPlateau qui permet d’initialiser le plateau de jeu.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void initialiserPlateau(int plateauJeu[12][4]);

Écrire une procédure afficher qui permet d’afficher le plateau de jeu.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void afficherPlateau(int plateauJeu[12][4]);

Écrire une procédure afficher qui permet d’afficher le code du maître du jeu (code de placement) pour un numéro de coups donné.

attention : ici, on ne fera que l’affichage, la vérification du code rentré par l’utilisateur se fera dans la procédure decode (question 11)

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void afficherCodePlacements(int plateauPlacements [12][4],int numeroCoups);

EXEMPLE affichage code placement

Pour le coup numero 0

Pour le coup numero 1

Pour le coup numero 2

Écrire une procédure saisie qui permet à l’utilisateur de définir sa proposition à la ieme ligne du plateau de jeu.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void saisieUtilisateur(int plateauJeu[12][4],int numeroCoups){

Écrire un prédicat estPrésente qui permet de vérifier si une couleur est présente sur une ligne

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
int estPresente(int coul, int codeSecret[4]);

Écrire un prédicat aGagne permettant de vérifier si le joueur a deviné le code.

/* Auteur : ... */
/* Date : ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
int aGagne(int plateauPlacements[nbCoups][nbCodeSecret], int numeroCoups);

Écrire une procédure decode qui reçoit le plateau de jeu, le tableau de placement, le code, un numéro de ligne. Elle met à jour la ie ligne de du tableau de placement, selon les similarités (comme définies ci-dessus), entre la ie ligne du plateau et le code originel.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) : ... */
/* Sortie(s) : ... */
void decode(int plateauJeu[12][4],int plateauPlacements[12][4], int numeroCoups, int codeSecret[4]);

Finaliser tout cela (écran de titre, boucle principale, fin de jeu)

Exercice 2 : La guerre des moutons

On considère une grille d’entier, carrée de taille N, représentant un champ. Dans ce champ, se trouvent 12 moutons disposés aléatoirement (caractère ‘M’), de l’herbe (caractère ‘H’) ou rien du tout (caractère ‘ ’). Le champ est initialisé avec les 12 moutons et de l’herbe ailleurs.

À chaque “tour” d’unité de temps, un mouton se déplace aléatoirement sur une case adjacente, de manière verticale ou horizontale. S’il y a de l’herbe, il la mange et au prochain déplacement, cette case sera vide.

S’il y a un mouton, il y a combat de moutons et à la fin, il n’en reste qu’un. Au prochain déplacement, cette case sera vide.

Si la case est vide et qu’autour (verticalement ou horizontalement), il n’y a pas d’herbe, ce mouton meurt de faim. Cette case devient vide.

Si un mouton se trouve sur un bord, il a moins de possibilité de déplacement.

Créer un répertoire exo2 dans lequel on ajoutera le fichier exo2.c contenant le code suivant :

#include <stdio.h>
#include <stdlib.h>

/* exo 2 :  les moutons */
int main(){
    return 0;
}

Écrire une procédure initChamp qui prend en paramètre la taille du champ.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
void initChamp (int champ[N][N],int taille);

Écrire une procédure affChamp qui prend en paramètre le champ et l’affiche à l’écran.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
void afficherChamp (int champ[N][N],int taille);

Ecrire une fonction bouge qui renvoie un nombre aléatoire entre 0 et 4 ([0,1,2,3] pour respectivement ‘N’, ‘S’, ‘E’, ‘O’).

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int bouge();

Écrire un prédicat verifGrille qui renvoie vrai si le déplacement est possible ou faux si le déplacement ne l’est pas.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int verifGrille(int dep, int i, int j,int taille);

Ecrire un prédicat herbeAutour qui renvoie vrai s’il y a de l’herbe (verticalement ou horizontalement) autour d’une case passée en paramètre.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int herbeAutour(int champ[N][N], int i, int j, int taille);

Écrire une procédure evolue qui prend en paramètre le champ et qui réalise un tour de mouvements du troupeau de moutons dans le champ, selon les règles définies ci-dessus.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
void evolue(int champ[N][N],int taille);

TIPs : pour pouvoir effacer le terminal et attendre 2 secondes

system("sleep 2");
system("clear");

Écrire une fonction compterMouton qui permet de savoir combien de moutons il y a dans le champs.

/* Auteur : ... */
/* Date :  ... */
/* Résumé :  ...  */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
int compterMouton(int champ[N][N],int taille);

Écrire une procédure tournoi qui prend en paramètre le champ et qui réalise les évolutions successives du troupeau de moutons, affiche le champ à chaque étape, jusqu’à ce qu’il ne reste qu’un seul mouton, le gagnant du tournoi.

/* Auteur : ... */
/* Date :  ... */
/* Résumé : ... */
/* Entrée(s) :  ... */
/* Sortie(s) :  ... */
void tournoi(int champ[N][N], int taille);

Exercice 3 : Le jeu de la vie

Description

Le jeu de la vie est un automate cellulaire qui repose sur le principe d’évolution. C’est une invention de John Horton Conway vers 1970.

Règles du jeu de la vie

Le jeu de la vie est un jeu sans joueur, il n’y a aucune intervention du joueur lors de l’exécution. Il s’agit d’un automate cellulaire, un modèle où chaque état conduit mécaniquement à l’état suivant à partir de règles pré-établies.

Le jeu se déroule sur une matrice 2D carrée. Une cellule évolue d’un tour à un autre. Une case a donc 8 voisins potentiels.

Par exemple, ici, la case 1 a un voisin dans la diagonale du haut. Les autres cases sont vides.

Une case a donc des voisins dans les 8 directions suivantes : Nord, Nord-Est, Est, Sud-Est, Sud, Sud-Ouest, Ouest, et Nord-Ouest.

L’évolution de la grille se fait au tour par tour en appliquant un ensemble de règles locales à chaque case. Ces règles prennent en compte l’état et le voisinage de la case et sont appliquées simultanément sur toutes les cases de la grille. Voici les règles que vous utiliserez :

Survie : Chaque cellule entourée de 2 ou 3 cellules continue de vivre.
Mort : Chaque cellule entourée de 4 cellules ou plus meurt de surpopulation. Chaque cellule entourée d’au plus 1 cellule meurt d’isolement. Si une cellule meurt, la case qui la contient devient vide.
Naissance Une cellule apparaît dans chaque case vide entourée d’exactement 3 cellule

Il existe 2 type d’évolution de grille dans le calcul des voisins :

La matrice Finie
La matrice Torique

La matrice finie

Ici on considére que la case n’a que 3 voisins possible

La matrice torique

Toutes les cases ont 8 voisins potentiels.

Il convient de transposer les voisins, Nord-Est, Est, Est, Sud-Est, et Nord-Ouest aux bords opposés de la grille

Implémentation

Le jeu de la vie se représente sur un tableau d’entiers dynamique 2D. La grille est une matrice (carée ou non). Les valeurs de la case possibles sont 0 ou 1. La matrice doit être donnée en entrée via un fichier texte.

Le fichier .txt doit être construit comme suit :

le nombre de lignes et le nombre de colonnes
la matrice de 0 et 1 correspondant au jeu de la vie
le nombre de tour d’évolution
0 => Matrice fermée ou 1=> Matrice torique

Exemple Helloworld

Implémenter les méthodes/fonctions suivantes :

void initialiser(int grille[N],int lignes,int colonnes);
void afficher(int grille[N],int lignes,int colonnes);

Le programme doit être exécuté de la manière suivante :

Solution 1

cat planeur.txt | ./exe

Solution 2

./exe < planneur.txt

Implémenter la ou les fonction(s)/méthode(s) afin de recencer le nombre de voisins d’une case. Pour cela, il convient de parcourir le voisinage d’une case et de calculer le nombre de voisins d’une case donnée.

Attention Vous devez réaliser 2 calculs de voisinage un pour une matrice torique et un pour une matrice finie

Implémenter la ou les fonction(s)/méthode(s) afin de calculer le nombre de voisins d’une case en matrice torique et en matrice finie.
Implémenter la ou les fonction(s)/méthode(s) afin de calculer la nouvelle valeur d’une case.
Implémenter la ou les fonction(s)/méthode(s) afin de calculer la nouvelle matrice.
Implémenter la méthode principale (main) afin de tester les différentes fonctions/méthodes précédements créées

- Aller plus loin

TD8 - Aller plus loin