Discussion :

[funtim78]

Bonjour!

Pour commencer, je souhaiterais vous prévenir que lire ce sujet sera un peu long, mais vous le trouverez sûrement très intéressant, donc n'hésitez pas à tout lire!

Je suis "débutant" en C: j'ai commencé il y a 2 mois pour un stage, et j'ai codé pas mal de programmes basiques dans différents domaines. J'ai vu que Google organisait un concours de codage (Google Code Jam), et je me suis dit pourquoi ne pas y participer pour voir un peu mon niveau et apprendre des choses?

Je tiens aussi à préciser que je ne cherche pas une solution toute faite au problème (surtout que la première phase est finie), mais des expliquations.

Voici le problème sur lequel j'aimerais quelques explications (donc un peu long à lire et en anglais, désolé).

Problem

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Input

The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.

Output

For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.

Limits

1 ≤ N ≤ 100
Small dataset

Each line will be no longer than 30 characters.
Large dataset

Each line will be no longer than 500 characters.


Sample:

Input :
3
elcomew elcome to code jam
wweellccoommee to code qps jam
welcome to codejam


Output:
Case #1: 0001
Case #2: 0256
Case #3: 0000

Tout d'abord, j'ai quand même était bien impressionné de voir que le premier a résolu ce problème en environ 10 minutes. Et en environ 30 minutes, il en a en fait résolu 3 comme ca... Il y a vraiment des gens aussi forts que ca?
Parce que moi j'y ai passé quasiment 24 heures pour 2 problèmes ^^


Sinon venons en au vif du sujet.
Pour résumer: on a donc un string de 18 lettres (welcome to code jam) à trouver, quelque soit l'espace entre deux caractères de cette phrase.

Après moulte réflexions, j'en suis venu à l'idée qu'une fonction récursive pouvait être pas mal. Cette fonction serait la suivante:

je lui dit de chercher un caractère dans une chaine à partir d'une certaine position. Si elle trouve ce caractère, elle se rappelle elle même pour trouver le caractère suivant.
Si le caractère suivant a pour numéro 19, c'est que l'on a trouvé notre phrase au complet (il n'y a que 18 caractères dans "welcome to code jam").

Ceci fonctionne très bien pour le petit test qui est donné à la fin. Ceci fonctionne aussi très bien pour le premier test simple donné par google. Par contre le second test plus complexe (avec 500 caractères) met à mal mon ordinateur, et refuse de me donner la réponse.
Je cherche donc à savoir quelles pourraient être les améliorations possibles à cette proposition de fonction récursive afin de rendre la détection plus rapide.

J'ai déjà pensé à supprimé tous les caractères qui n'appartiennent pas à ceux du string en question, mais je ne vois pas d'amélioration notable sur le test long.


Si ca vous intéresse, voici le code que j'ai écrit jusqu'à maintenant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/* ==================================================================
* Author: A. Decagny												*
* Date: September 2009												*
* Context: Google Code Jam 2009 - Welcome to code jam	       		*
* Company: Oº°* Personnal Purposes *°ºO								*
* file: main.c														*
================================================================== */
 
#define DATA_SIZE 550
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void seekIsAGeek(char* welcome, int address, int rankOfLetter, char* data, int* result);
 
int main()
{
    int i = 0, j=0;
 
    char textFileName[30] = "";
    FILE* textFile = NULL;
    FILE* resultFile = NULL;
 
    char** stringOfData = NULL;
    char** dataExpurgated = NULL;
    int nbOfData = 0;
 
    int result = 0;
    char* welcome = "welcome to code jam";
    char buffer[2] = "";
 
    /* We open the file and get the data */
    printf("####################################################\n");
    printf("########  Welcome to \"Welcome to Code Jam\" #########\n");
    printf("####################################################\n");
 
    printf("\n");
    printf("What is the name of the input file?\n");
 
    scanf("%s", textFileName);
 
    textFile = fopen(textFileName,"r");
    rewind(textFile);
 
    fscanf(textFile, "%d\n", &nbOfData);
    stringOfData = malloc(nbOfData*sizeof(int));
    dataExpurgated = malloc(nbOfData*sizeof(int));
 
    for(i=0; i<nbOfData; i++)
    {
        stringOfData[i] = malloc(DATA_SIZE * sizeof(char));
        dataExpurgated[i] = malloc(DATA_SIZE * sizeof(char));
 
        dataExpurgated[i][0]='\0';
 
        fgets(stringOfData[i], DATA_SIZE - 1, textFile);
    }
 
    fclose(textFile);
 
    /* We can now make all the work */
    resultFile = fopen("result.txt", "w+");
    rewind(resultFile);
 
    for(i=0; i<nbOfData; i++)
    {
        result = 0;
 
        /* expurgating of the data */
        for(j=0; j<strlen(stringOfData[i]);j++)
        {
            if (strchr(welcome,stringOfData[i][j]) != NULL)
            {
                buffer[0]=stringOfData[i][j];
                buffer[1]='\0';
 
                strcat(dataExpurgated[i],buffer);
            }
        }
 
        /* number of possibilities? We search for the letter */
        seekIsAGeek(welcome, 0, 0, dataExpurgated[i], &result);
 
        fprintf(resultFile, "Case #%d: %04d\n", i+1, result);
 
        printf("Case #%d\n", i+1);
    }
 
 
    /* And now we can free everything */
    for(i=0; i<nbOfData; i++)
    {
        free(stringOfData[i]);
    }
    free(stringOfData);
 
    fclose(resultFile);
    free(dataExpurgated);
 
    return 0;
}
 
/* This function is used to know where the first googd letter is,
* and then call itself again!
* /!\ This function is a recursive function! */
void seekIsAGeek(char* welcome, int address, int rankOfLetter, char* data, int* result)
{
    int i = 0;
 
    if (rankOfLetter == 19)
    {
        (*result)++;
    }
    else
    {
        for(i=address; i<strlen(data); i++)
        {
            if (data[i] == welcome[rankOfLetter])
            {
                seekIsAGeek(welcome, i, rankOfLetter +1, data, result);
            }
        }
    }
}

Et si vous voulez les fichiers de test pour vous amuser vous aussi, n'hésitez pas à me demander ^^
Mais j'avoue que la je bloque un peu sur la méthode pour réaliser des optimisations...

Et si vous avez des idées de cours que je peux lire pour rendre mes codes plus performant en général, je suis preneur. Les cours d'algorithmie de ce site son un bon début? Et après?

Merci d'avance pour votre aide!

[LittleWhite]

Bonjour,

Bon j'ai pas la solution :s ( j'en suis navré pour moi surtout ).

C'est surtout que j'ai pas compris comment ils arrivent à 256 pour la deuxième ligne.

Enfin bref, pour optimiser des problêmes de ce genre, c'est surtout une question d'algorithmie.

Comme il est dit directement dans le texte qu'ils sont capable de trouver 400 ... ... fois leurs chaines, cela veut dire que le programme avec une methode de recherche "bateau" va prendre des temps. (Arrive à deux grands resultats).
La méthode récursif va planter ( j'ai pas regarder le code, honte à moi, donc je peux avoir faux ) car elle va rentrer dans un niveau de récursion trop grand.

Si j'avais compris entièrement l'exemple, en méthode simple, je dirait de conter le nombre de 'w' de 'e' de 'l' ... ( pour toute les lettres de "welcome to code jam" ) diviser par le nombre d'occurance de celle ci dans la chaine ( donc le nombre de 'o' divisé par trois ).

Donc grace à ce comptage on peut savoir combien de fois on peut recontruire la chaine.
Genre nous avons 34 'w' dans la chaine, donc nous pouvons au minimum avoir 34 fois le mot. Mais si 'o' == 0 on ne peut avoir le mot.
Enfin bref, je verrais bien une méthode de ce genre, qui ne permet que le parcours du texte une seule fois.

Petite précision, faut aussi compter les espaces ( qui sont significatifs ) comme le prouve la troisième ligne de l'exemple.

[Mac LAK]

Vu que tu es limité, par l'énoncé, à trouver au mieux 9999 chaînes adéquates, je commencerais par faire un tableau statique de 10.000 éléments pour la reconnaissance.

Ensuite, tu parcours la chaîne initiale caractère par caractère : quand tu trouves un "w", tu remplis la première case libre du tableau avec.
Ensuite, quand tu trouves un "e", tu incrémentes un compteur de reconnaissance sur chaque "w" déjà trouvé, et tu dupliques les entrées "w" déjà reconnues (c'est à dire toutes les chaînes dont le compteur de reconnaissance est supérieur ou égal à l'indice du caractère en cours).

Sur la chaîne suivante : wweellccoommee to code qps jam
I=indice de parcours, C=caractère en cours, T=tableau de reconnaissance (couple "indice+taille de reconnaissance").

I=0 : C="w"
=> T={(0,1)}
I=1 : C="w"
=> T={(0,1),(1,1)}
I=2 : C="e"
=> T={(0,2),(1,2)}
I=3 : C="e"
=> T={(0,2),(1,2),(0,2),(1,2)} (duplication des entrées >= 2)
I=3 : C="l"
=> T={(0,3),(1,3),(0,3),(1,3)}
I=4 : C="l"
=> T={(0,3),(1,3),(0,3),(1,3),(0,3),(1,3),(0,3),(1,3)} (duplication des entrées >= 3)
etc.

Bon, faudrait vérifier le cas des lettres déjà trouvées (ex : un "e" peut être le premier de "welcome", ou le dernier) en plus, mais ça reste dans le même principe (il y a juste un parcours de la chaîne en cours de reconnaissance à insérer dans l'algo).

A la fin, il suffit de compter les entrées de T dont l'indice de reconnaissance est égal à la longueur de la chaîne à trouver (ici, 19), et tu as le nombre recherché. Tu peux aussi détruire les entrées "reconnues" au fur et à mesure et les comptabiliser à ce moment-là.

L'avantage, c'est que si le texte d'origine est de longueur L, et la chaîne à rechercher de longueur P, tu as une complexité en O(L x P) au pire (avec le parcours de la chaîne à trouver pour les lettres en double), ce qui devrait normalement être relativement rapide.

[Jean-Marc.Bourguet]

Tout d'abord, j'ai quand même était bien impressionné de voir que le premier a résolu ce problème en environ 10 minutes. Et en environ 30 minutes, il en a en fait résolu 3 comme ca... Il y a vraiment des gens aussi forts que ca?

Oui. Une bonne partie de la "force", c'est l'expérience. Je parie qu'il
n'a pas écrit le programme en C en passant (il m'a fallu moins de 12
minutes 37 secondes à partir du moment où j'ai mesuré mais j'avais déjà
refléchi avant à comment le lancer le chronomètre et je n'ai guère fait que
taper le code et vérifier sur 4 exemples -- ceux que tu donnes -- et ainsi corriger une borne, et je n'ai pas respecter les contraintes exactes du format d'entrée et de sortie).

Et si vous avez des idées de cours que je peux lire pour rendre mes
codes plus performant en général, je suis preneur. Les cours d'algorithmie
de ce site son un bon début? Et après?

Il y a un ou deux problèmes de combinatoire dans ce genre dans la section
"défi language fonctionnel"...

Vu que tu es limité, par l'énoncé, à trouver au
mieux 9999 chaînes adéquates, je commencerais par faire un tableau statique
de 10.000 éléments pour la reconnaissance.

Ma compréhension est qu'on te demande le résultat modulo 10000 parce que le
résultat exact peut être beaucoup plus, dépasser la capacité des int par
exemple.

L'avantage, c'est que si le texte d'origine est de longueur L, et la
chaîne à rechercher de longueur P, tu as une complexité en O(L x P) au pire
(avec le parcours de la chaîne à trouver pour les lettres en double), ce
qui devrait normalement être relativement rapide.

Vu que tu maintient une entrée par résultat, tu as une complexité qui est
C(L, P), soit proche de la factorielle de L si P est petit par rapport à L.
Si tu ne tiens compte que du nombre d'entrée -- on se fout du contenu --,
tu as ce que j'ai programmé et ta complexité est bonne.

[Mac LAK]

Ma compréhension est qu'on te demande le résultat modulo 10000 parce que le résultat exact peut être beaucoup plus, dépasser la capacité des int par exemple.

Oui, c'est vrai que l'on peut interpréter le résultat ainsi également... Je suis parti sur mon interprétation principalement à cause des limites de capacité mémoire qui pourraient exploser avec un texte initial très long.

Vu que tu maintient une entrée par résultat, tu as une complexité qui est C(L, P), soit proche de la factorielle de L si P est petit par rapport à L.
Si tu ne tiens compte que du nombre d'entrée -- on se fout du contenu --, tu as ce que j'ai programmé et ta complexité est bonne.

J'avoue que je vois mal pourquoi tu parles de factorielle : au contraire, plus P est petit, plus la complexité chute car le nombre de possibilités de présence diminue très rapidement... Dans le cas limite (P=1), il ne peut pas y avoir plus de L nombre d'occurrences (R) dans le texte initial (0<=R<=L) ! Également, dans l'autre cas limite P=L, on a 0<=R<=1 impérativement... Je pencherais plus pour une complexité "gaussienne" que pour une factorielle, pour ma part (complexité maximale avec P proche de L/2).

Tu noteras que je ne stocke dans mon tableau que deux éléments : l'indice initial de la chaîne (pas son parcours !), et l'indice de reconnaissance (entre 1 et P). Je parle aussi de la suppression à la volée dès qu'une chaine est reconnue pour libérer de la place (nécessaire si l'on prends l'hypothèse que le chiffre à retourner est un modulo 10.000 du résultat).

Après, l'idéal serait un tableau dynamique complet pour stocker ces éléments, mais bon : côté performances, je suis moyennement convaincu, c'est vrai que le dimensionnement initial pourrait poser des problèmes. J'avoue que je n'ai pas cherché non plus à calculer une borne valide pour cette valeur...

Reste qu'à mon avis, le principal facteur d'optimisation est de ne parcourir le texte initial qu'une seule fois, toute l'astuce consistant à mémoriser les diverses chaînes en cours de reconnaissance sous un format rapide et (relativement) économique en mémoire. Quoi qu'il arrive, tu es obligé de maintenir en mémoire les chaînes en cours de reconnaissance, la problématique étant sûrement de borner cette valeur en fonction des paramètre P, L et de l'indice courant de parcours du texte initial...

Faudrait voir si, au lieu de la duplication que j'effectue, un troisième champ "compteur" permettrait ou pas de limiter la casse, ou même de s'affranchir de la duplication...

[Jean-Marc.Bourguet]

Oui, c'est vrai que l'on peut interpréter le résultat ainsi également... Je suis parti sur mon interprétation principalement à cause des limites de capacité mémoire qui pourraient exploser avec un texte initial très long.

C'est difficile d'interpréter

For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer.

autrement.

J'avoue que je vois mal pourquoi tu parles de factorielle : au contraire, plus P est petit, plus la complexité chute car le nombre de possibilités de présence diminue très rapidement... Dans le cas limite (P=1), il ne peut pas y avoir plus de L nombre d'occurrences (R) dans le texte initial (0<=R<=L) ! Également, dans l'autre cas limite P=L, on a 0<=R<=1 impérativement... Je pencherais plus pour une complexité "gaussienne" que pour une factorielle, pour ma part (complexité maximale avec P proche de L/2).

Parce que je me suis planté. C'est bien le nombre de combinaison (trouver le nombre de a^P parmis a^L), donc L!/P!/(L-P)! La complexité est donc au mieux 2^L/(L+1) vu que la somme pour P variant de 0 à L vaut 2^L.

Reste qu'à mon avis, le principal facteur d'optimisation est de ne parcourir le texte initial qu'une seule fois,

Non. Tant que tu comptes individuellement, tu es mal parti pour ce genre de chose.

Faudrait voir si, au lieu de la duplication que j'effectue, un troisième champ "compteur" permettrait ou pas de limiter la casse, ou même de s'affranchir de la duplication...

C'est ce que j'ai fait. Un tableau de la taille de la chaîne à chercher suffit (+1 parce que j'ai préféré traité une condition au limite comme ça).

[Mac LAK]

Non. Tant que tu comptes individuellement, tu es mal parti pour ce genre de chose.

Va falloir que tu expliques "individuellement"... Je vois mal comment arriver au bout de cet algo sans utiliser un parcours et reconnaitre chaque possibilité de chaîne, l'autre solution me paraissant difficilement implémentable en C "brut de fonderie"... A savoir chercher toutes les occurrences de chaque lettre de la chaîne à rechercher dans le texte L, et calculer les chemins sans jamais revenir en arrière (ce qui fait un beau petit problème de graphes et d'ensembles d'ailleurs).

Pour moi, tu as deux solutions pour résoudre cet algo : une en reconnaissance lexicale, donc une par une (ce que j'ai exposé plus haut), et l'autre ensembliste (calcul global). Par rapport aux possibilités natives du C, je vois mal comment faire la seconde, et donc ne pas compter "individuellement" les chaînes...

[Jean-Marc.Bourguet]

Va falloir que tu expliques "individuellement"... Je vois mal comment arriver au bout de cet algo sans utiliser un parcours et reconnaitre chaque possibilité de chaîne, l'autre solution me paraissant difficilement implémentable en C "brut de fonderie"...

Ça me semble plus simple de compter le nombre de possibilités que de gérer tes listes pour les compter par après.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
        for (i = 0; i < needle_size; ++i)
            counts[i] = 0;
        for (lptr = line; *lptr != '\0'; ++lptr) {
            for (nptr = strchr(needle, *lptr);
                 nptr != NULL;
                 nptr = strchr(nptr+1, *lptr))
            {
                counts[nptr-needle] =
                    (counts[nptr-needle] + counts[nptr-needle-1]) % 10000;
            }
        }
        printf("Case #%d: %04d\n", line_num, counts[needle_size-1]);

La seule astuce c'est que counts[-1] est valide et vaut 1.

[Nico404]

Une explication du problème a été publiée : Contest Analysis - Problem C
Elle préconise un solution à base de programmation dynamique.
Perso, j'avais écrit un solution récursive qui a fonctionné pour le small input, mais n'aurait jamais fonctionné pour le large.
Sachez qu'il est possible de télécharger le code source des participants, ça peut être instructif

[funtim78]

Merci à tous pour vos réponses!

Je vais essayer de répondre dans l'ordre à vos interventions!

LittleWhite -> Le 256 vient du fait que chaque lettre de welcome est doublée (ca fait donc 128) et qu'après il y ait 2 espaces à la suite, ce qui multiplie les possibilités par 2 (j'ai aussi galéré avant de trouver ^^).
Sinon la méthode récursive ne plante pas, même avec 19 niveaux de récursions. Sauf qu'elle n'est pas super optimisée pour le "grand test" (cf le lien de Nico404).

Jean-Marc.Bourguet -> non justement, les meilleurs (et plus de 75% des gens qui participent au concours aussi) codent en C++, Java et C (dans l'ordre d'utilisation). Et quand on voit le résultat des meilleurs, on se dit que le C++ et le C sont quand même bien puissants, vu ce qu'il arrivent à faire en quelques lignes de code!
Par contre j'avoue ne pas vraiment avoir bien compris ta méthode de résolution...


Mac LAK -> Ton algo ressemble pas mal à la solution à adopter apparemment. Mais si j'ai bien compris, ton premier indice correspond à l'indice du w, et après le second indice correspond à l'endroit où on se trouve dans le string "welcome to code jam" ?

Par contre vous m'avez totalement perdu avec vos calculs de complexité... les cours d'algo du site expliquent ca? (j'ai jamais réussi à comprendre comme ca fonctionnait en fait...)


Nico404-> Merci pour les infos

[Mac LAK]

Mac LAK -> Ton algo ressemble pas mal à la solution à adopter apparemment. Mais si j'ai bien compris, ton premier indice correspond à l'indice du w, et après le second indice correspond à l'endroit où on se trouve dans le string "welcome to code jam" ?

C'est exactement ça.

Par contre vous m'avez totalement perdu avec vos calculs de complexité... les cours d'algo du site expliquent ca? (j'ai jamais réussi à comprendre comme ca fonctionnait en fait...)

Je ne crois pas qu'il y aie un cours dédié explicitement aux calculs de complexité, mais il doit certainement y avoir plusieurs allusions/explications dans les cours d'algo du site.

Ceci étant dit, si tu veux plus d'infos à ce sujet, direction le forum Algorithmes, y'a pas mal de monde capable de t'expliquer ça et/ou tu pourrais donner l'idée à un rédacteur de faire un cours à ce sujet.

[ram-0000]

Ceci étant dit, si tu veux plus d'infos à ce sujet, direction le forum Algorithmes, y'a pas mal de monde capable de t'expliquer ça et/ou tu pourrais donner l'idée à un rédacteur de faire un cours à ce sujet.

Sur Wiki, une explication qui permet de dégrossir le problème et de dresser le panorama.