Ton nom en éléments chimiques

Dimanche 20 juillet 2008 à 2h32

Cette année, alors que je me faisais grave chier pendant un A.D.S j’écoutais attentivement l’exposé d’A.D.S. (Analyse de Dossier Scientifique) d’un de mes camarades de classe, j’ai eu une super idée en regardant le tableau de classification périodique des éléments accroché au mur.
Cette idée, c’est de décomposer un mot en symboles d’éléments chimiques, par exemple, patate devient Pa Ta Te (Protactinium, Tantale, Tellure) puis de prendre les numéros atomiques correspondant : 91 73 52. (Bien sûr, cette décomposition n’est pas unique et tous les mots n’en ont pas une.) Quel jeu amusant, n’est-ce pas ? Amusant à coder aussi… (Clique sur « lire la suite » pour la partie intéressante: l’algorithmique).
Tu peux aussi essayer quelques mots si ça t’amuse :



Comme je suis fainéant et que ça m’usait le cerveau de réfléchir en fixant le tableau périodique, je me suis dit qu’il était bien plus pratique et bien plus fun de coder un algo qui me faisait tout ça. Je l’ai fait en C.
Après avoir fait mon algorithme, j’ai « traduit » le dico qui se trouve dans /usr/share/dict/french (au total 139704 mots). Résultat : 13020 mots ont une traduction en symboles d’éléments chimiques, le tout calculé en moins d’une demi seconde ! Voici le code, commenté :

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

#include <stdio.h>
#include <string.h>
 
#define TAILLE_TABLEAU	111
#define TAILLE_MOT	64 // taille maximale du mot à chercher
char tableau[TAILLE_TABLEAU][3] = {"h", "he", "li", "be", "b", "c", "n", 
"o", "f", "ne", "na", "mg", "al", "si", "p", "s", "cl", "ar", "k", "ca", 
"sc", "ti", "v", "cr", "mn", "fe", "co", "ni", "cu", "zn", "ga", "ge", 
"as", "se", "br", "kr", "rb", "sr", "y", "zr", "nb", "mo", "tc", "ru", 
"rh", "pd", "ag", "cd", "in", "sn", "sb", "te", "i", "xe", "cs", "ba", 
"la", "ce", "pr", "nd", "pm", "sm", "eu", "gd", "tb", "dy", "ho", "er", 
"tm", "yb", "lu", "hf", "ta", "w", "re", "os", "ir", "pt", "au", "hg", 
"tl", "pb", "bi", "po", "at", "rn", "fr", "ra", "ac", "th", "pa", "u", 
"np", "pu", "am", "cm", "bk", "cf", "es", "fm", "md", "no", "lr", "rf", 
"db", "sg", "bh", "hs", "mt", "ds", "rg"};
 
// Note: liste contient des listes de numéros atomiques, mais comme c'est un tableau de char
// qui finit par 0 (aucun élément chimique n'a pour numéro 0), il suffit de faire un strlen
// pour savoir le nombre d'éléments d'une liste ou strcpy pour la copier.
 
unsigned int elchi(char *mot, unsigned char *liste)
{
	unsigned int i;
	unsigned int resultat = 0;
	if (mot[0] == 0)
		return 1;
	for (i=0;i<TAILLE_TABLEAU;i++)
	{
		if (tableau[i][0] == mot[0])
		{
			unsigned int resultat_local = 0;
			if (tableau[i][1]==0) // c'est un élément à un caractère
			{
				resultat_local = elchi(mot+1, liste+resultat*TAILLE_MOT+1);
			}
			else if (strlen(mot) >= 2)
			{
				if (tableau[i][1]==mot[1]) // élément à deux caractères
				{
					resultat_local = elchi(mot+2, liste+resultat*TAILLE_MOT+1);
				}
			}
			if (resultat_local) // il y a un résultat pour l'élément i
			{
				if (resultat) // on avait déjà trouvé un autre résultat avant
				{
					if (strlen((char *)(liste+TAILLE_MOT+1)) < strlen((char *)(liste+1))) // si le nouveau résultat est plus court, on l'utilise
					{
						strcpy((char *)(liste+1), (char *)(liste+TAILLE_MOT+1));
						*(liste) = i+1;
					} // sinon on l'oublie
				}
				else // c'est le premier résultat qu'on trouve
				{
					*(liste) = i+1;
					resultat++;
				}
			}
		}
	}
	return resultat; // en pratique, il y a 0 ou 1 résultat, puisqu'on ne garde que le résultat le plus court
}
 
int main()
{
	char mot[TAILLE_MOT];
	unsigned char liste[TAILLE_MOT*TAILLE_MOT];
	unsigned int i=0;
	memset(liste, 0, TAILLE_MOT*TAILLE_MOT);
	while (scanf("%s", mot) == 1)
	{
		if (elchi(mot, liste))
		{
			printf("%s: ", mot);
			for (i=0;*(liste+i)!=0;i++)
			{
				printf("%d ", *(liste+i));
			}
			printf("
");
		}
		memset(liste, 0, TAILLE_MOT*TAILLE_MOT);
	}
	return 0;
}

La fonction est bien sûr récursive, et lorsqu’il y a plusieurs résultats, seul le plus court est gardé. S’il y a plusieurs résultats de la même longueur, un seul est gardé.
Pour le compiler, il suffit de faire un petit :
# gcc -Wall -O3 el_chim.c -o el_chim
Puis pour traduire le dico et connaître le temps que cela prend :
# time el_chim < /usr/share/dict/french > mots
Note: le code traduit tous les mots un à un (ou du moins tout ce que scanf considère comme étant un mot) et affiche les résultats sur la sortie standard, jusqu’à EOF (End Of File ou Ctrl-D dans un terminal). J’ai un P4 à 3Ghz, voici le résultat :
real 0m0.431s
user 0m0.388s
sys 0m0.008s
Pour connaitre le nombre de mots traduits (affiche le nombre de lignes):
# wc -l mots

Au début j’avais programmé ça en TI-Basic sur ma Ti-89, ça prenait en général plus de 30 secondes pour traduire un seul mot. Voilà, je me suis bien amusé :)

Classé dans Programmation

1 Commentaire »

Une Réponse à “Ton nom en éléments chimiques”

  1. Jésus le cookie Dit:
    24 juillet, 2008 à 20:58

    83, 52

    C’est tout.

Répondre