Rapport La Résistance

Table of Contents

index.jpg

1 Introduction

Au cours de cette activité il a été question de créer un programme nous permettant de déterminer le nombre de messages différents qu'il est possible de générer à partir d'une séquence de code Morse et d'un dictionnaire, tous ceci pour aider hypothétiquement le musée de la résistance.

Pour ce faire il faudra utiliser la récursivité et la programmation dynamique.

2 Description synoptique de la méthode

Ce programme peut-être découpé en deux parties:

-La partie de récupération du dictionnaire et de la création de son homologue traduit en morse.

-La partie de tests récursifs permettant de compter combien de combinaisons de mots son possibles au vu des messages codés qui nous sont proposés.

2.1 Fonction de Traduction

La fonction DicoMorse prend en argument les tableaux de chaînes de caractères dans lesquelles sont stockés le dictionnaire proposé ainsi que le dictionnaire que l'on va initialiser en morse, le tableau de caractères contenant l'alphabet en morse et le nombre de mots dans le dictionnaire donné. Cette fonction va me permettre de traduire le dictionnaire donné, caractère par caractère, en fonction de l'alphabet morse que j'ai initialisé dans le main. 

// initialisation des mots données traduits en morse
void DicoMorse(char ** D, char morse[27][5], char ** tradD, int mots){
    int lettreIndice;

    for(int i=0; i<mots; ++i){
        tradD[i] = (char*) malloc(sizeof(char)*21*4);

        for(int j=0; j<(int)strlen(D[i]); ++j){
            lettreIndice = D[i][j]-65;
            strncat(tradD[i], morse[lettreIndice],4);
        }
    }
}

2.2 Fonction de Décompte

La fonction décompte prend en argument un tableau de chaînes de caractères contenant le dictionnaire des mots proposés traduits en morse, le nombre de mots proposés, un tableau de caractères contenant le message à décoder, l'indice par lequel on souhaite commencer le décompte et enfin la table tabSauv de type long long int permettant de traiter des entiers codés sur 64 bits au lieu de 8 bits seulement. Cette table tabSauv va nous permettre de stocker au fur et à mesure de la récursivité les valeurs que nous avons déjà calculées afin de gagner en efficacité.

Cette fonction repose sur deux tests effectués pour chaque mots de notre dictionnaire :

-le mot peut-il être le premier mot de l'intervalle traitée ?

-le mot finit-il le message ?

Ainsi lorsque l'on trouve un premier mot qui peut correspondre au début du message mais que l'on ne trouve pas de mots qui peuvent suivre, on lance un appel récursif de la fonction décompte avec cette fois-ci comme indice de début l'indice sur lequel on se trouve hypothétiquement après le traitement des n premier(s) mot(s).

Ainsi de suite jusqu'à ce qu'un mot soit trouvé terminant la phrase: débute alors le rembobinage de notre récursivité nous menant vers la somme correcte à retourner. 

// Fonction récursive qui renvoie le nombre de message possibles
long long int decompte(char ** tradD, int mots, char * mess, int debut, long long int * tabSauv){

    long long int somme = 0;

    if(tabSauv[debut] == -1){

        for(int i=0; i<mots; i++){ // on parcourt le dictionnaire traduit

            // si le mot du dictionnaire correspond au début du message que l'on est entrain de traiter
            if(strncmp(mess+debut, tradD[i], strlen(tradD[i])) == 0){

                // si on trouve un mot qui permet d'arriver à la fin du message
                if (debut+strlen(tradD[i]) == strlen(mess)){
                    // cas d'arret on ajoute 1 et la récursivité commence
                    somme += 1;
                }

                // sinon
                else{
                    // appel recursif de la fonction à partir de l'indice debut + mot traité
                    // ainsi on va de nouveau chercher un mot jusqu'au cas d'arret
                    somme += decompte(tradD,mots,mess,debut+strlen(tradD[i]),tabSauv);
                }
            }
        }
        // on sauvegarde le nombre de messages possibles à l'indice du cas traité
        tabSauv[debut] = somme;
        // on renvoie le nombre de messages possibles pour ce cas
        return somme;
    }

    else{ 
        return tabSauv[debut]; // on renvoie la valeur qu'on avait rentré dans le tableau
    }
}

3 Mon programme commenté

Au niveau de l'algorithme peu de choses sont ajoutées avec le main. On initialise les tableaux avec malloc ainsi que l'alphabet morse et on libère l'espace alloué.

Le tableau tabSauv est initialisé à -1, repère quant au fait que telle ou telle case a déjà été traitée. La réponse est stockée dans la variable rep puis affichée. 

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


// Fonction récursive qui renvoie le nombre de message possibles
long long int decompte(char ** tradD, int mots, char * mess, int debut, long long int * tabSauv){

    long long int somme = 0;

    if(tabSauv[debut] == -1){

        for(int i=0; i<mots; i++){ // on parcourt le dictionnaire traduit

            // si le mot du dictionnaire correspond au début du message que l'on est entrain de traiter
            if(strncmp(mess+debut, tradD[i], strlen(tradD[i])) == 0){

                // si on trouve un mot qui permet d'arriver à la fin du message
                if (debut+strlen(tradD[i]) == strlen(mess)){
                    // cas d'arret on ajoute 1 et la récursivité commence
                    somme += 1;
                }

                // sinon
                else{
                    // appel recursif de la fonction à partir de l'indice debut + mot traité
                    // ainsi on va de nouveau chercher un mot jusqu'au cas d'arret
                    somme += decompte(tradD,mots,mess,debut+strlen(tradD[i]),tabSauv);
                }
            }
        }
        // on sauvegarde le nombre de messages possibles à l'indice du cas traité
        tabSauv[debut] = somme;
        // on renvoie le nombre de messages possibles pour ce cas
        return somme;
    }

    else{ 
        return tabSauv[debut]; // on renvoie la valeur qu'on avait rentré dans le tableau
    }
}



// initialisation des mots données traduits en morse
void DicoMorse(char ** D, char morse[27][5], char ** tradD, int mots){
    int lettreIndice;

    for(int i=0; i<mots; ++i){
        tradD[i] = (char*) malloc(sizeof(char)*21*4);

        for(int j=0; j<(int)strlen(D[i]); ++j){
            lettreIndice = D[i][j]-65;
            strncat(tradD[i], morse[lettreIndice],4);
        }
    }
}



int main()
{
    // récupération du message
    char * mess = (char*) malloc(100001*sizeof(char));
    scanf("%s", mess);

    // récupération du nombre de mots fournis
    int mots;
    scanf("%d", &mots);

    // initialisation de l'alphabet en morse
    char morse[27][5] =
    {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

    // Création du dictionnaire des mots donnés
    char ** dico = (char**) malloc(mots*sizeof(char*));
    int i;
    for(i=0; i<mots; i++) {
        dico[i] = (char*) malloc(21*sizeof(char));
        scanf("%s", dico[i]);
    }

    // Traduction du dictionnaire en morse
    char ** tradD = (char**) malloc(mots*sizeof(char*));
    DicoMorse(dico, morse, tradD, mots);

    // Création d'un tableau qui contiendra le nombre de phrases pour chaque cas possibles
    long long int tabSauv[100001];
    int j;
    for(j=0; j<100001; j++){
        tabSauv[j] = -1;
    }

    long long int rep = decompte(tradD, mots, mess, 0, tabSauv);
    printf("%lld\n", rep);

    return 0;
}

3.1 Enoncé du Test

Entrée: 

......-...-..---.-----.-..-..-..
5
HELL
HELLO
OWORLD
WORLD
TEST

Sortie: 

2

4 Une solution de la communauté

J'ai choisi de présenter ce code car kAworu a utilisé le principe des arbres pour résoudre ce problème. J'ai trouvé cela intéressant car nous commençons à peine en cours d'ALGO à étudier ce sujet.

Il commence donc par initialiser une structure "tree" où certains détails m'échappent néanmoins.

Son algorithme peut-être résumé comme suit: pour chaque caractère et par extension pour chaque mots, un noeud est créé. Après avoir obtenu un arbre correspondant à toutes les combinaisons possibles, il ne lui reste plus qu'à parcourir efficacement cette arbre pour compter combien de combinaisons sont possibles et enfin donner la solution.

Malgré le nombre de notions qui m'étaient étrangères dans le code de kAworu, j'ai décidé de tenter de présenter l'idée que j'avais de son algorithme car il me semble important de se plonger dans l'inconnu pour découvrir de nouvelles choses. 

#include <err.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>


struct tree {
        struct tree *dot, *dash;
        int nwords;
};

const char *
char_to_morse(char c)
{
        const char *table[] = {
                ['A'] = ".-",
                ['B'] = "-...",
                ['C'] = "-.-.",
                ['D'] = "-..",
                ['E'] = ".",
                ['F'] = "..-.",
                ['G'] = "--.",
                ['H'] = "....",
                ['I'] = "..",
                ['J'] = ".---",
                ['K'] = "-.-",
                ['L'] = ".-..",
                ['M'] = "--",
                ['N'] = "-.",
                ['O'] = "---",
                ['P'] = ".--.",
                ['Q'] = "--.-",
                ['R'] = ".-.",
                ['S'] = "...",
                ['T'] = "-",
                ['U'] = "..-",
                ['V'] = "...-",
                ['W'] = ".--",
                ['X'] = "-..-",
                ['Y'] = "-.--",
                ['Z'] = "--..",
        };
        return (c >= 'A' && c <= 'Z' ? table[c] : NULL);
}

struct tree *
tree_add_char(struct tree *t, char c)
{
        struct tree     *current = t;
        const char      *rep = char_to_morse(c);

        for (const char *p = rep; *p != '\0'; p++) {
                struct tree **next =
                    *p == '.' ?
                    &current->dot :
                    &current->dash;
                if (*next == NULL)
                        *next = calloc(1, sizeof(struct tree));
                if (*next == NULL)
                        err(EX_OSERR, "calloc");
                current = *next;
        }

        return (current);
}

struct tree *
tree_add_word(struct tree *t, const char *word)
{
        struct tree     *current = t;

        (void)fprintf(stderr, "adding %20s=", word);
        for (const char *p = word; *p != '\0'; p++)
                (void)fprintf(stderr, "[%s]", char_to_morse(*p));
        (void)fprintf(stderr, "\n");

        for (const char *p = word; *p != '\0'; p++)
                current = tree_add_char(current, *p);
        current->nwords++;

        return (current);
}

size_t
tree_decode0(const struct tree *root, const char *s, size_t len,
    size_t start, size_t *memoized)
{
        size_t                   n = 0;
        const struct tree       *current = root;
        const struct tree       *next = NULL;

        if (start == len)
                return (n);

        if (memoized[start] != -1)
                return (memoized[start]);

        for (size_t i = start; i < len; i++) {
                next = (s[i] == '.' ? current->dot : current->dash);
                if (next == NULL)
                        break;
                if (next->nwords > 0) {
                        size_t sub = tree_decode0(root, s, len, i + 1, memoized);
                        n += next->nwords * sub;
                }
                current = next;
        }

        if (next != NULL)
                n += next->nwords;

        memoized[start] = n;
        return (n);
}

size_t
tree_decode(const struct tree *root, const char *s)
{
        size_t   len;
        size_t  *memoized;

        len      = strlen(s);
        memoized = calloc(len, sizeof(size_t));
        if (memoized == NULL)
                err(EX_OSERR, "calloc");
        for (size_t i = 0; i < len; i++)
                memoized[i] = -1;

        return tree_decode0(root, s, len, 0, memoized);
}

int
main(void)
{
        struct tree     root;
        char            morse[100001];
        int             n;

        (void)memset(&root, 0, sizeof(struct tree));
        (void)scanf("%s", morse);
        (void)scanf("%d", &n);
        for (int i = 0; i < n; i++) {
                char word[21];
                (void)scanf("%s", word);
                (void)tree_add_word(&root, word);
        }

        (void)fprintf(stderr, "sequence=%s\n", morse);

        (void)printf("%zu\n", tree_decode(&root, morse));

        return (EXIT_SUCCESS);
}

5 Bilan de mes apprentissages

Pour finir, je dirais que ce puzzle m'a aidé à approfondir ma vision des algorithmes récursifs que l'on vient de voir en cours d'Algorithmique. Il m'a aussi permis de découvrir le morse et à me familiariser avec lui !

Author: Quatrefages Augustin

Created: 2022-05-04 mer. 13:52

Validate