Demi 08: Reconnaissance vocale

Bonjour,
Tout d'abord, voici le sujet de l'énoncé:

LIMITE DE MEMOIRE

1024 ko

LIMITE DE TEMPS

5000 ms
ENONCE

On s'intéresse à un programme de reconnaissance vocale.

Le but est de partir d'une suite de phonèmes enregistrés pour arriver à un mot connu.

Pour cela, l'on vous fournit un graphe orienté de transitions. Chaque état est numéroté par un nombre entre 0 et N-1 (N

Pour chaque phonème (qui sera représenté par un caractère ASCII), en partant d'un état donné, on peut se rendre sur ceux des états voisins qui sont reliés à l'état courant par un arc étiqueté par le phonème en question. Le score d'un chemin est la somme des scores des arêtes qui le composent (en fait, des produits de probabilités).

L'on vous donne un sommet/état de départ et une liste de phonèmes enregistrés. Vous devez donner le sommet d'arrivée le plus probable, c'est à dire l'extrémité d'un chemin de score maximal étiqueté par le mot enregistré. (S'il y en a plusieurs possibles, retournez le sommet dont le numéro est le plus petit).
ENTREE

Le nombre N sur la première ligne.
Le numéro de l'état initial sur la deuxième.
Un nombre M sur la troisième ligne, et sur les M lignes suivantes, deux entiers i et j, un caractère ASCII c, et un score s, séparés par des espaces et représentant une transition i->j étiquetée par le phonème c avec le score (la probabilité de transition, en fait) f.
Sur la dernière ligne, le mot à lire, d'un maximum de 100 lettres, et qui peut être constitué de tous les caractères ASCII sauf '\n'.
SORTIE

Le numéro de l'état final tel que défini plus haut, suivi d'un saut de ligne.

Ce n'est pas que je bloque pour cet exercice, mon algo passe les 6 premiers tests. Toutefois, bien qu'il échoue aux autres, il est vraiment dommage de ne pas pouvoir passer aux autres problèmes, en ayant trouvé l'algorithme. Les conditions de résolution d'un problème me paraisse un peu trop strict, quant aux informations fournies en sortie. Il devient en effet très difficile de débugger son programme( les tests 7 et plus contiennent il me semble 26000 liens -_- ).
En résume, il me paraitrait judicieux de baisser les exigences de validatité d'un algo.

Ca peut sembler flemmard, mais bon, au bout d'un moment c'est lassant d'être forcé pour arriver au problème suivant, d'y aller à coup d'affichage d'énoncé...

Si toutefois vous voulez examiner mon code ( relativement court, mais j'essaierai de le commenter au possible \^\^ ), je suis tout disposé à le mettre.
Merci de m'avoir lu

Up!

Sinon, si quelqu'un pouvait poster le sujet du dernier challenge de la demi-finale 08, "Passe-Temps" ce serait cool.
Merci

LIMITE DE MEMOIRE

32000 ko

LIMITE DE TEMPS

4000 ms
ENONCE

Le passe-temps favoris de Cimone est de jouer au jeu suivant. Le jeu consiste en une grille de N*N cases. Le but est de colorier certaines cases de façon à satisfaire les contraintes du jeu. Tout d'abord, certaines cases de la grille sont interdites. La deuxième contrainte est que pour chaque colonne et pour chaque ligne de la grille, le nombre de cases devant être coloriées est fixé. C'est-à-dire que l'on vous donne en entrée N entiers l[i] et N entiers c[i], et que les cases doivent être marquées de telle sorte qu'il y ait l[i] cases coloriées sur la i-ème ligne, et c[i] cases coloriées sur la i-ème colonne..

Ecrivez un programme qui dit si oui ou non il est possible de colorier certaines cases de la grille N*N de telle sorte à satisfaire les contraintes du jeu.
ENTREE

• sur la première ligne, un entier N (1

• sur la deuxième ligne, N entiers, les l[i] (compris entre 0 et N), indiquant la contrainte de marquage des cases sur chaque ligne de la grille.

• sur la troisième ligne, N entiers, les c[i] (compris entre 0 et N), indiquant la contrainte de marquage des cases sur chaque colonne de la grille.

• sur les N lignes suivantes, N caractères contigus représentant la grille. Le caractère '0' (zéro) indique une case libre, alors que le caractère 'X' représente une case interdite (il est interdit de la colorier).
  SORTIE

un entier, 1 s'il est possible de colorier les cases de façon à satisfaire les contraintes du jeu, et 0 sinon.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

3
2 2 1
3 1 1
000
0X0
000

en sortie ...

1

Exemple 2
en entrée ...

3
2 2 1
3 2 0
000
0X0
000

en sortie ...

0

@ kjus : c'est presque un nonogram quoi(mais en plus compliqué)

Bah, il faut que ton algo soit exact, pas approché... Tant que tu ne réussis pas les gros tests, tu n'as pas trouvé l'algo ! Soit il est trop lent, soit il y a un bug que les tests plus petits n'avaient pas vu...

A titre d'info, pour le test 7, N=20 et M=26000 alors que pour le test 6, N=10 et M=13000. De nombreux candidats ont réussi cet exo en demi-finale l'année dernière, donc ton code ne doit pas être tout à fait exact...

On peut quand même dire que le 6 est un gros test \^\^.
Je vous poste la partie intéressante de mon programme ici, le reste n'étant que la récupération des données et la recherche du maximum:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

        for ( i = 0; i                 for ( j = 0; j                         if ( store_data[ j ] == -1 )
                                continue;           
                        for ( k = 0; k                                 if ( link[ j ][ k ][ word[ i ] ] == -1 )
                                        continue;                       
                                if ( cp_store_data[ k ] == -1 || cp_store_data[ k ]                                    cp_store_data[ k ] = store_data[ j ] + link[ j ][ k ][ word[ i ] ];                               
                        }                                                                                                            
                }                                                                                                                    
                memcpy( store_data, cp_store_data, sizeof( int ) * n );                                                              
                memset( cp_store_data, -1, sizeof( int ) * n );                                                                      
        }

Note: désolé si l'indentation a disparu...

Je suis très mauvais en explication, mais je vais quand même essayer:

Tout d'abord store_data et cp_store_data sont deux tableaux qui représentent l'état actuel à chaque sommet ( donc de taille n )
store_data correspond au meilleur état possible des sommets à la lettre d'indice i
cp_store_data permet la transition entre 2 lettres successives, et représente donc le meilleur état des sommet à la lettre d'indice i + 1.
Toutes les cases de cp_store_data sont initialisées à -1, comme pour store_data excepté la case représentant le sommet de départ qui est initilisée à 0.

Le tableau tridimensionnel link se présente sous la forme:
valeur_du_lien = link[ sommet_depart ][ sommet_arrive ][ lettre ]
valeur_du_lien a la valeur -1 si ce lien n'existe pas

Commentons le passage:

1

                                if ( cp_store_data[ k ] == -1 || cp_store_data[ k ]                                    cp_store_data[ k ] = store_data[ j ] + link[ j ][ k ][ word[ i ] ];

k représente le sommet d'arrivé et j le sommet de départ, i l'indice de la lettre actuelle dans word
On va mettre à jour la valeur du sommet k dans cp_store_data si cette valeur est -1 ou si elle est inférieure à celle obtenue en partant du sommet j et en emprentant le lien link[ j ][ k ][ word[ i ]
En d'autres mots, il existe un autre chemin qui amène au sommet k à la lettre i + 1, tout en ayant une valeur ( score dans les termes de l'énoncé ) supérieure.

J'espère que ces explications sont assez claires, désolé si je ne suis pas un bon pédagogue.

Ps: Modérateur, si vous jugez que ce code se permet une résolution de l'exo ( bien qu'il ne passe pas les tests, ni ne soit d'une clarté éblouissante \^\^ ), je m'en excuse. N'hésitez donc pas à supprimer ce post.

Merci

Pour les gros tests : et si ton système d'exploitation plantait quand tu ouvres un fichier entre 600 et 650 Mo, tu dirais quoi ? :-) En informatique, il n'y a pas d'à peu près...

Sinon, ton idée (et ton bout de code) me semblent corrects, même si ta boucle sur ton tableau n'est pas très optimale en temps. Es-tu sûr que tu as des structures de données assez grosses pour t'accomoder du test 7 ?

Pour les gros tests : et si ton système d'exploitation plantait quand tu ouvres un fichier entre 600 et 650 Mo, tu dirais quoi ? :-) En informatique, il n'y a pas d'à peu près...

Je voie pas trop ce que tu veux dire par là, si tu pouvais préciser stp.

Ouais je sais que c'est pas optimal, mais c'est une modification de mon code d'origine pour que ce soit plus simple.
Mais là, à mon avis y'a pas de raisons pour un qu'il y ait un problème de taille, puisque mon malloc ne me retourne pas d'erreur.

Dans le cas où les plateformes lors des épreuves et celle d'entrainement du site soient différentes, quelqu'un pourrait confirmer qu'il a réussi à passer cet exercice en section entrainement?
Merci

Ce que je veux dire c'est que tu sembles dire "bah, je passe déjà le test 6, ça suffit". Si ton programme marche "à peu près", c'est qu'il ne marche pas, l'informatique c'est binaire, 0/1 :-)

Pfou ça avait l'air plutôt difficile ! Et oui pour l'informatique binaire, complétement d'accord.

Oh, un paradoxe.