[Selection 2010]: Des chiffres ?! Des corrections ?!

Voilà, je vais poster les algos n°1 et 3 tels que je les ai soumis !

nucleotide.c :

1
2
#include 
#include

#define cinq 4
#define float int
#define interrupteur switch
#define beau case
#define agre case

char nucleotide(int N, char* s)
{
float i, compteur[cinq], nbMaxDOccurrencesAnticonstitutionnellement, plusPresenteAvecAccentSurLeE;
char bases[4] = {'A', 'C', 'G', 'T'};
for(i = 0 ; i compteur[i] = 0;
compteur[0] = 0; // Pour être sûr, on le refait à la main
compteur[1] = 0;
compteur[2] = 0;
compteur[3] = 0;
for(i = 0 ; i interrupteur(s[i]) {
case 'A': compteur[0]++; break; // Kazaa
beau 'C': compteur[1]++; break; // Beauté
agre 'G': compteur[2]++; break; // Agressé
agre 'T': compteur[3]++; break; // Agrégé
}
}
nbMaxDOccurrencesAnticonstitutionnellement = 0;
for(i = 0 ; i if(compteur[i] > nbMaxDOccurrencesAnticonstitutionnellement) {
plusPresenteAvecAccentSurLeE = i;
nbMaxDOccurrencesAnticonstitutionnellement = compteur[i];
}
return bases[plusPresenteAvecAccentSurLeE];
}

int main(void)
{
int N;
char* s;

scanf("%d\n", &N);
s = calloc(N+1, sizeof(char));
fgets(s, N+1, stdin);

printf("%c\n", nucleotide(N, s));

return 0;
}

soussequence.c :

1
2
#include 
#include

int L;

typedef struct noeud noeud;
struct noeud {
int valeur;
noeud *fils[4];
noeud *lien;
int profondeur;
int nbOccurrences;
} *bottom, *racine, *gagnant;

noeud *alloc() {
noeud *n;
n = malloc(sizeof(noeud));
return n;
}

void init() {
int i;
bottom = alloc();
racine = alloc();
gagnant = alloc();
bottom->valeur = 0;
for(i = 0 ; i bottom->fils[i] = racine;
bottom->lien = NULL;
bottom->profondeur = -1;
racine->nbOccurrences = 0;
racine->valeur = 0;
for(i = 0 ; i racine->fils[i] = NULL;
racine->lien = bottom;
racine->profondeur = 0;
racine->nbOccurrences = 0;
gagnant->valeur = 0;
}

void quiEst(int valeur) {
char bases[4] = {'A', 'C', 'G', 'T'};
int i, *resultat, pas = 0;
resultat = calloc(L, sizeof(int));
while(valeur > 0) {
resultat[pas] = valeur % 4;
valeur >>= 2;
pas++;
}
for(i = L - 1 ; i >= 0 ; i--)
printf("%c", bases[resultat[i]]);
printf("\n");
}

void sous_sequence(int N, int L, char* s) {
int i, j, n[26], nbOccurrences, nbOccurrencesMax = 0;
n['A' - 'A'] = 0;
n['C' - 'A'] = 1;
n['G' - 'A'] = 2;
n['T' - 'A'] = 3;
noeud *r, *r2, *exr2, *top, *candidat;
char base; // Un chariot à Baze (il faut être de Marseille pour comprendre ; en plus, cette marque n'existe plus, elle s'est fait racheter par Monoprix ; et pas par Mammouth, même si MammOUTH écrase les prIX).
init();
top = racine;
r = racine;
for(i = 0 ; i // printf("=== Traitement de %c ===\n", s[i]);
// nouveauTop = 0;
r = top;
base = s[i];
exr2 = NULL;
while(r->fils[n[base - 'A']] == NULL) {
// printf("On est en %p (%d) de profondeur %d.\n", r, r->valeur, r->profondeur);
if(r->profondeur r2 = alloc();
// printf("On insère quelque chose sous (%d) : %p (%c)\n", r->valeur, r2, base);
r->fils[n[base - 'A']] = r2;
r2->valeur = (r->valeur for(j = 0 ; j r2->fils[j] = NULL;
r2->profondeur = r->profondeur + 1;
r2->nbOccurrences = 0;
if(r2->profondeur == L) { // On tient un candidat !
candidat = r2;
nbOccurrences = 1;
r2->nbOccurrences = nbOccurrences;
if(nbOccurrences > nbOccurrencesMax || (nbOccurrences == nbOccurrencesMax && candidat->valeur valeur)) {
nbOccurrencesMax = nbOccurrences;
gagnant = candidat; // Nouveau gagnant !
}
}
/* if(nouveau
Top == 1) {
top = r2;
nouveauTop = 2;
printf("Nouveau top : %p !\n", top);
} else */
// if(r != top) {
if(exr2 != NULL) {
exr2->lien = r2;
// printf("%p -> %p\n", exr2, r2);
}
exr2 = r2;
// printf("exr2 passe à %p.\n", r2);
} else {
top = top->lien;
// printf("On est au maximum de profondeur...\n");
}
// printf("Je rappelle que r vaut %p.\n", r);
r = r->lien;
// printf("Le prochain sera %p (%d).\n", r, r->valeur);
}
// printf("Je sors juste de while, nouveauTop vaut %d (r : %p, exr2 : %p).\n", nouveauTop, r, exr2);
if(r->profondeur == L - 1) {
candidat = r->fils[n[base - 'A']];
nbOccurrences = candidat->nbOccurrences + 1;
r->fils[n[base - 'A']]->nbOccurrences = nbOccurrences;
// quiEst(candidat->valeur);
// printf(" passe à %d occurrences !\n", nbOccurrences);
if(nbOccurrences > nbOccurrencesMax || (nbOccurrences == nbOccurrencesMax && candidat->valeur valeur)) {
nbOccurrencesMax = nbOccurrences;
gagnant = candidat; // Nouveau gagnant !
// printf("===[");
// quiEst(gagnant->valeur);
// printf(" %d]===\n", nbOccurrences);
}
}
if(exr2 != NULL)
exr2->lien = r->fils[n[base - 'A']];
// printf("%p -> %p\n", exr2, r->fils[n[base - 'A']]);
if(top->profondeur == L)
top = top->lien;
else
top = top->fils[n[base - 'A']];

// printf("%p\n", top);
}
}

int main(void)
{
int N;
char* s;

scanf("%d\n", &N);
scanf("%d\n", &L);
s = calloc(N+1, sizeof(char));
fgets(s, N+1, stdin);

sous_sequence(N, L, s);
quiEst(gagnant->valeur);

return 0;
}

(dommage que ça ne passe pas tous les tests :P)

Edit : Ha ha, on perd les indentations ! J'ai mis des balises code pourtant… Ça ne doit pas supporter les textes trop longs. Bon ben… pastebin ! Ah non, ideone, c'est une sorte de pastebin, mais qui compile !
nucleotide.c :
http://ideone.com/TFu7DoTN
soussequence.c :
http://ideone.com/nlfQ9bQn

Mdr tu t'es un peu planté je pense :

case 'A': compteur[0]++; break; // Kazaa
beau 'C': compteur[1]++; break; // Beauté
agre 'G': compteur[2]++; break; // Agressé
agre 'T': compteur[3]++; break; // Agrégé

Ca serait pas plutôt :

case 'A': compteur[0]++; break; // Kazaa
beau 'T': compteur[1]++; break; // Beauté
agre 'C': compteur[2]++; break; // Agressé
agre 'G': compteur[3]++; break; // Agrégé

Ouais en fait j'ai remis les char dans l'ordre alphabétique pour que ce soit correct, mais je n'ai pas pensé à modifier les case (ça ne vient pas à l'esprit, quand même :P).

nbMaxDOccurrencesAnticonstitutionnellement, plusPresenteAvecAccentSurLeE

Ah ba ça c'est de la variable O_o !
J'espère que tu utilises le copier-coller

agranger36 → Non :D Je ne sais pas comment le faire avec Emacs (non, là, je déconne, en revanche :D).

Vous avez fini de faire vos bourgeois avec vos noms de domaine ? :P

@wuzumi : euh ca coute rien, ca dépend pour qui hein ... essaye d'acheter un unicorn.fr ou mieux un unicorn.com (à IBM) et on en reparle :p
Sinon pour le coté découverte, je suis heureux de t'entendre dire ça, c'est ce que l'on cherche à faire à travers le QCM et les exos d'algo de séléction ;)

@wumzi : vive l'hébergement chez soi ! il n'y a que comme ça que l'on fait vraiment de l'Internet...

Personnellement, je tourne avec un ancien portable (PIII@1GHz) plus un vieil onduleur piqué dans une boîte où j'ai travaillé.

lol, il y a des collectionneurs de composants c'est surprenant, ils ont de tonnes de composants récupérés sur des vieux ordis et il peuvent en faire de nouveaux ordis avec O_o

@jaloyan: faire du neuf avec du vieux ???

Si tu récupères un Pentium II, 32 Mo de SDRAM, un DD de 4 go, récuperés d'antiquités et qui marchent, ton nouveau PC n'est pas très neuf :D

« Allez exprès pour me vanter => htp://www.wumzi.info/dotclear/index.php?post/2009/12/12/FeedBack-part.-1%3A-SheevaPlug »
→ Déjà il y a « htp », ensuite il y a « Unable to connect to database » xD

« Sinon pour le coté découverte, je suis heureux de t'entendre dire ça, c'est ce que l'on cherche à faire à travers le QCM et les exos d'algo de séléction ;) »
→ Perso j'ai surtout appris que les orgas Prologin étaient scandaleux… Ah non je le savais déjà.

« Par contre, quand on voit les codes en C, on a envie de pleurer :'( (enfin pour JJ, c'est de rire hein :-P) »
→ En tout cas, j'ai appris ce qu'étaient les pointeurs :D Bon là j'exagère, mais ce qui est vrai c'est que c'était la première fois de ma vie que je codais un arbre en C.

« → En tout cas, j'ai appris ce qu'étaient les pointeurs :D Bon là j'exagère, mais ce qui est vrai c'est que c'était la première fois de ma vie que je codais un arbre en C. »

Notre prof nous oblige à parcourir tous nos tableaux avec des pointeurs, ca m'aide pas à apprendre à aimer le C ...

le_sphinx : euh ... ça coûte rien un nom de domaine :) 5 euros par an pour un .fr !!! Ça coûte le prix d'un repas à la cantine ou un aller-retour de 20 km en TER !

Ensuite un petit serveur à 100 euros dans le bureau familial et le tour est joué !

Allez exprès pour me vanter => http://www.wumzi.info/dotclear/index.php?post/2009/12/12/FeedBack-part.-1%3A-SheevaPlug

Au passage, un grand merci aux organisateurs pour ces exercices très instructifs, qui m'ont (permis) obligé d'explorer de nouveaux aspects de la programmation Python, de découvrir quelques algorithmes (Distance de Levenshtein, Dijkstra, A* et Bellman-Ford) !

Edit: URL modifiée pour être valide :D

Les pointeurs c'est marrant =D

JJ ton code pour la question 3 ne passe pas tous les tests ?
Thomas avait une solution en C utilisant des arbres et qui passe bien tous les tests.
Pour ma part j'ai proposé deux solutions à la question 3) : une en Caml avec des tables de hashage, et une en C sans table de hashage ni arbre. Et les deux passent tous les tests, mais le code C utilise un structure de donnée un peu capilotractée xD
Le code est un peu long, mais si ça intéresse des gens vous pouvez le trouver ici :

http://ideone.com/pd5eeGqB

(Avec les restrictions données sur le site d'entrainement je crois que la complexité est meilleure que la version avec les arbres, mais je ne sais pas si elle est plus efficace pour autant).

Pour la question 4 en revanche, j'ai utilisé du caml, plein de ref, et j'ai écrit un code moche, donc j'ai trop honte pour le poster =D
Mais globalement il est censé être assez efficace.

wah! Mais c'est quoi tout ca? On etait obligé d'ecrire des codes aussi long dans les autres langages? Pour les deux premiers algos, mes codes prennent beaucoup moins de place ( dans le 3 eme aussi mais comme il a pas passé tout les test ( temps d'execution)).
J'ai l'impression que certains sont allé chercher loin

lol le sphinx, si c'est pour embrouiller les debutants que tu as fait écrit ce code , c'est reussi lol (en meme temps fallait pas grand chose pour m'embrouiller, le C j'en ai pas fait depuis 2ans (ah ben en fait en relisant j'ai finalement compris le code))

Répondre au sujet

Vous devez vous enregistrer ou vous connecter pour poster des messages.