Dissidents - Algo

« Ca ne marchera pas ...

Dark-Side — Mon, 05 Nov 2007 16:16:00 +0100

... Vous savez pourquoi ? Parce que ça nous amuse. Vous trouvez quelque chose pour m’emmerder, je trouve quelque chose pour vous emmerder. C’est un jeu et je vais gagner. J’ai un coup d’avance. Vous êtes déjà emmerdé. »
Edité le 25/12/07
Je crois que je vais faire comme ça désormais, toujours commencer mes articles par une citation sans rapport (ou du moins sans rapport logique apparent).
Bref, je suis là parce que j'avais dis que je vous montrerai une IA en prolog. Donc voilà je vais vous en montrer une.
Pour qu'on soit d'accord tout de suite :

oui le code est sale
oui je m'en fous
non je n'accepterai aucune remarque

Bien. Ceci mis au clair, voici le code :

est_vainqueur(papier, pierre).
est_vainqueur(pierre, ciseaux).
est_vainqueur(ciseaux, papier).

corres(pierre, 1).
corres(papier, 2).
corres(ciseaux, 3).

corresp(perdu, 0).
corresp(nul, 1).
corresp(gagne, 2).

same(X, X).

plus_joue([Papier,Pierre,Ciseaux], X) :- Pierre >= Papier, Pierre >= Ciseaux, same(X, pierre).
plus_joue([Papier,Pierre,Ciseaux], X):- Pierre =< Papier, Papier >= Ciseaux, same(X, papier).
plus_joue([Papier,Pierre,Ciseaux], X) :- Ciseaux >= Papier, Pierre =< Ciseaux, same(X, ciseaux).
 
traiter(perdu, pierre, [Papier, Pierre, Ciseaux], X) :- P is Papier + 1, same(X, [P,Pierre, Ciseaux]).
traiter(perdu, ciseaux, [Papier, Pierre, Ciseaux], X) :- P is Pierre + 1, same(X, [Papier,P, Ciseaux]).
traiter(perdu, papier, [Papier, Pierre, Ciseaux], X) :- C is Ciseaux + 1, same(X, [P,Pierre, C]).
 
traiter(nul, papier, [Papier, Pierre, Ciseaux], X) :- P is Papier + 1, same(X, [P,Pierre, Ciseaux]).
traiter(nul, pierre, [Papier, Pierre, Ciseaux], X) :- P is Pierre + 1, same(X, [Papier,P, Ciseaux]).
traiter(nul, ciseaux, [Papier, Pierre, Ciseaux], X) :- C is Ciseaux + 1, same(X, [P,Pierre, C]).
 
traiter(gagne, ciseaux, [Papier, Pierre, Ciseaux], X) :- P is Papier + 1, same(X, [P,Pierre, Ciseaux]).
traiter(gagne, papier, [Papier, Pierre, Ciseaux], X) :- P is Pierre + 1, same(X, [Papier,P, Ciseaux]).
traiter(gagne, pierre, [Papier, Pierre, Ciseaux], X) :- C is Ciseaux + 1, same(X, [P,Pierre, C]).
 
alea(X) :- random(1,4, X).

stat(Coups, Nb) :- 
	plus_joue(Coups, Adv),
	est_vainqueur(Coup, Adv),
        corres(Coup, Nb).

jouer(Coups, X) :- 
	random(1, 11, Al),
	(Al =:= 1 -> alea(Nb);
	stat(Coups, Nb)),
	write(Nb), nl,
	write('Gagné, nul ou perdu ?'), nl,
	read(Score),
	corresp(S, Score),
	traiter(S, Coup, Coups, X).

boucle(Coups) :-
	jouer(Coups, N_coups),
	write('1 pour rejouer, 0 pour arreter.'), nl,
	read(X),
	X =:= 1,
	boucle(N_coups).
	
init :- boucle([0,0,0]).

Naturellement je vais faire quelques remarque, alors il faut savoir que c'est mon premier code en prolog, c'est pour ça qu'il est sale. Ensuite : ce code est surement optimisable (surtout au niveau des fonctions traiter) mais ce n'est pas important, ce qu'il faut voir c'est que même si ce code est un peu plus long qu'un code OCaml bien optimisé il est quand même bien plus facile à comprendre par un non initié. Et c'est ça l'important !

Voilà, bonne journée !

Chiffrement de Vigenère

Dark-Side — Sat, 15 Sep 2007 21:58:00 +0000

Une brêve présentation de l'algorithme de cryptage inventé par Blaise de Vigenère au XVIe siècle. Bon, je vais pas faire comme quelques rédacteurs de ce blog bien connu et vous dire que je vais vous sortir un article sur la cryptologie chaque semaine, déjà parce que je sais que je ne tiendrais jamais cet objectif, ensuite car je me doutes que ça va vite lasser tout le monde :-°

Mais bon comme le sujet m'interesse un temps soit peu et que je ne me préoccupes pas particulièrement de l'interêt que les visiteurs réguliers (alias les autres rédacteurs) peuvent lui porter je vais surement vous sortir quelques articles dessus ^_^

Pour ce premier article je vais vous parler du Chiffrement de Vigenère. Ceux qui connaissent un peu cette technique doivent s'attendra à voir apparaître ce tableau.
Mais ce ne sera pas le cas (enfin si mais c'est juste pour vous dire qu'osef en fait :D ).

Non nous on va parler de la méthode mathématique, facilement implémentable dans un algorithme (plus facilement tu meurs d'ailleurs).
Le principe est très simple en mathématique les lettres de l'alphabet sont numérotées de 0 à 25 (oui toujours cette manie de mettre le premier index à 0), il devient alors très facile de crypter un texte lettre par lettre (comme ça va être le cas pour cette algorithme). Pour ce chiffrement on va devoir utiliser une clé de chiffrement et pour chaque lettre en clair va correspondre une lettre cryptée qui varie en fonction de la clé utilisée, et de la position de la lettre dans le texte.
En effet à chaque lettre va correspondre une lettre de la clé à partir de laquelle on trouvera la lettre cryptée. Comme je me doute que ce n'est pas très clair voici un exemple :

Texte de départ    : MOT
Clé de chiffrement : CLE

C'est assez basique comme exemple me direz vous mais on voit bien qu'à chaque lettre du mot MOT corresponds une lettre de la clé, vous pouvez alors vous demander : mais comment faire si le texte comporte plusieurs mots voir phrases, paragraphes ? La clé doit être de la même longueur ? (c'est bien ces petites question ça montre pas du tout que je vous prends pour des cons et ça met une ambiance bonne enfant comme celle du site du zéro :-° )
Et bien je vais me faire un plaisir de vous répondre que non, il vous suffit de répeter la clé (*exclamations de surprise parmi la foule de lecteurs*), exemple :

j'ai plusieurs mots dans mon texte
clec lecleclec lecl ecle cle clecl

Bon et maintenant qu'on a ça on fait quoi ?

Et bien on utilise la fonction mathématique (hyper compliquée soit dit en passant) que je vais vous montrer sous peu, ou alors on regarde dans le tableau la cellule présente à la colonne de la lettre à crypter et à la ligne de la lettre de la clé utilisée.
Avouez que ça devient vite lent et rébarbatif, au lieu de faire ça vous pouvez aussi utiliser le fait que chaque lettre qu'elle fasse partie de la clé, du texte à crypter ou du texte crypté a un index compris entre 0 et 25 (comme je vous l'ai appris précédement). Une fois qu'on a bien enregistré ce principe on a plus qu'à additionner pour chaque lettre du texte en clair : son index et l'index de la lettre de la clé correspondante, le résultat sera l'index de la lettre cryptée. Le problème une fois qu'on a fait ça c'est que par exemple si un z est associé à un y on a : 25+24 ce qui donne 49, c'est marrant on dirait que ça corresponds pas à une lettre cet index. :S
Ce qu'on peut faire c'est appliquer un modulo 26 à ce résultat, on obtient ainsi 49%26 = 23. Et 23 ça correspond à quoi ? A un 'x', c'est bon on a ce qu'on voulait !!!
Pour résumer on a la fonction suivante : crypté = (clair + cle) % 26

Have fun ! (ou pas)

Un langage d'homme, un vrai ...

Dark-Side — Mon, 27 Aug 2007 21:55:00 +0000

Parce que y'en a marre de ces langages d'hérétiques ! (cf: billets précédents)
On va enfin pouvoir regarder un langage pur (et sayx) : l'ocaml ... Je ne vais pas passer trois heures à vous présenter le caml vous avez déjà tous du écouter bluestorm moi je vais vous donner des exemples (des vrais) de la supériorité du caml sur les langages impurs.
Celà va d'un simple "hello world ! " à un bot irc §§

Les différents exemples

"Hello, World !"
Code ocaml :

print_string "Hello, World !"

Code C:

#include 
#include 
int main(int argc, char *argv[])
{
printf("Bonjour");
return 0;
}

La lourdeur d'un langage impératif/impur n'est pas à démontrer plus avant sur cette exemple on va donc passer au suivant si vous le voulez bien !

Un algorithme de cryptage simple : le césar
Le code en ocaml :

let rec replace crypted initial cle i long=
    if i >= long then crypted
    else 
      let cc = Char.chr (cle + Char.code initial.[i]) in
      let sc = String.make 1 cc in replace (crypted ^ sc) initial cle (i+1) long
;;

let encrypt (mot: string) (cle: int) =
  let long = String.length mot in
  (replace "" mot cle 0 long)
;;

let string = read_line() in
let cle = read_int ()in
print_endline (encrypt string cle)

Le code en C :

#include 
#include 
#include 
#define MAX_BUF 50
void encrypt (char *chaine, int cle)
{
char *p;
for (p=chaine; *p != '\0'; ++p)
{
if(isalpha(*p+cle))
*p += cle;
}
printf ("%s\n", chaine);
}
void clear(char* s, FILE* buffer)
{
char *p = NULL;
if((p = strchr(s, '\n')) != NULL)
*p = '\0';
else
while(getc(buffer) != '\n');
}
int main(int argc, char *argv[])
{
char chaine[MAX_BUF];
int cle;
fgets (chaine, MAX_BUF - 1, stdin);
clear(chaine, stdin);
scanf("%i", &cle);
encrypt (chaine, cle);
return 0;
}

Une fois de plus le code C est plus long que le code en ocaml §§

Conway's game of life
Le code en ocaml : jeu_de_la_vie.ml
Le code en C : jeu_de_la_vie.c (merci à Cygal pour ce code gracieusement fournis, il ne se doutais pas de ce à quoi allait servir sinon je ne l'aurais surement jamais eu en fait :p)
Concernant le code de Cygal vous pouvez enlever si vous le souhaitez tous les beaux commentaires qui ne servent à rien dans le contexte de cet article il n'en demeurera pas moins plus long, après certains pourront dire qu'il est mieux, le rendu plus jolie, etc etc mais reconnaissez que tous ces commentaires seraient dénués de bonne fois :p (tous comme ce billet ? :-° )

Le bot IRC
Euh ... disons qu'on en parlera à l'occasion d'un autre article :D

Conclusion:

Bon vous direz que ce billet pue (mais bon on a vu pire hein :p ) et que y'a des langages surement mieux que le caml mais sans exemples concrets vous resterez sous sa domination (mouhahahaha ? :-° ) si jamais vous avez envie de rajouter des exemples en python, en ruby voir en Obj-C n'hésitez pas à ~~éditer ce billet~~ à me les passer afin que je les soumettent à la censure/dégradent/refuse.
Merci de votre attention.
Vous pouvez désormais fermer votre navigateur et reprendre une activité normale ... :p

PS: je promet de trouver une vrai idée pour les autres billets et de les rédiger un tant soit peu :p
PS 2: Et dire que j'ai emmerdé Poulet toute la journée pour ce billet, quand il va le voir il va être deg :D

Superformula

lasts — Mon, 21 May 2007 17:15:00 +0200

Dans la continuité du Perlin Noise, une formule magique pour générer des courbes capables d'imiter celles qu'on trouve dans la nature (selon son inventeur, Johan Gielis, un biologiste à la con qui a généralisé le principe des superellipses).

La formule permet de déterminer en coordonnées polaires (rayon, angle) le point de la courbe en fonction de six paramètres (a, b, m, n1, n2 et n3). A vue de nez, les paramètres a et b déterminent la forme générale (cercle / ellipse) tandis qu'm influence plutôt le nombre de pics. 'Fin bref, c'est pas très compliqué, les intérêts sont multiples, typiquement pour stoquer des formes complexes dans un format léger ou avoir des courbes esthétiques à disposition.

La page wikipedia fournit également des exemples de valeurs à donner aux paramètres m, n1/2/3 (avec a = b = 1).

Et la source en c++/qt (ainsi que des screenshots) fait maison pour expérimenter un peu dans son coin (super, super, me direz vous; la suite en 3d sera pour un autre jour).

Perlin Noise

lasts — Sun, 20 May 2007 16:12:37 +0000

Ou comment générer des courbes aléatoires jolies qui peuvent servir à un peu n'importe quoi, comme fabriquer des textures à bas prix, dessiner des trucs qu'on dirait que ça a été fait à la main ou générer des terrains / nuages à la terragen. Bref, une réponse possible à la question du réalisme en informatique dans des domaines assez diversifiés.

Le Perlin Noise (ouais, ça veut dire bruit de Perlin, mais merde) est une fractale qui permet de rendre plus naturelle une série aléatoire. Le principe est assez simple : prendez n valeurs aléatoires oscillant entre 0 et k et interpolez-les. Vous obtenez un résultat immonde et somme toute très banal. Re-prendez 2*n valeurs aléatoires oscillant entre 0 et k/2 et interpolez-les. Ajoutez le résultat obtenu à la courbe précédente. Recommencez autant de fois que voulu. Servir chaud.

+ + + + + =

Bien, on reprends avec des vrais mots : appelons n la fréquence et k l'amplitude. Plus l'amplitude diminue, moins la courbe a d'influence sur le résultat final. Plus la fréquence augmente, plus la courbe est saccadée. On arrête naturellement l'itération lorsque l'amplitude est trop faible pour être visible.

Concernant le passage sur l'interpolation, juste histoire de vous rafraîchir la mémoire : l'interpolation consiste à construire une courbe à partir de n points donnés. On citera notamment l'interpolation linéaire, qui consiste à relier chaque point par une ligne, l'interpolation sinusoïdale (la même chose, avec des sinus, si si), cubique ou lagrangienne (mais en pratique, tout le monde vous dira de favoriser l'avant-dernière).

linéaire / sinusoïdale / cubique

Le perlin noise en une dimension, c'est déjà super pratique pour tracer des traits à la main informatiquement (principe qui est notamment utilisé dans l'industrie logiciel pour donner un coté esquisse à l'apparence des gui et bien faire comprendre aux clients que le produit qu'ils voient n'est pas terminé - cf Creating Informal Looking Interfaces). Lorsqu'on bascule en 2d, ça permet de générer des textures originales qui rendent super bien (marbre, bois, whatever en fait, il suffit d'appliquer un filtre sur le rendu) et qui ne consomment pas des masses. Lorsqu'on bascule en 3d, ça permet de donner plus de consistance à une map, à faire des jolis nuages, etc.

Et pour conclure, une implémentation en c++/qt vraiment lente ainsi qu'un joli lien vers un monsieur qui en parle mieux que moi (ouais, c'est minable comme redirection, le but était juste de vous présenter le concept).

A noter que ça donne des bugs intéressants aussi.

Project Euler

Cygal — Sat, 19 May 2007 16:47:00 +0000

De la présentation d'un « projet » qu'il est bien.

Ou comment résoudre des problèmes mathématiques avec les outils qui vous plaisent, quels qu'ils soient.

Le principe de Project Euler est très simple : vous vous inscrivez (c'est rapide), et vous avez à votre disposition de nombreux problèmes « mathématiques » (155 à l'heure où je vous écris), pour la plupart assez originaux, et en tout cas assez amusants, des plus simples aux plus ardus. Les premiers permettent de se mettre en jambe, voyez vous-même (ceci est le problème classé comme le plus facile) :

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Pour les anglophobes, sachez que le but est de trouver la somme de tous les multiples de 3 et 5 inférieurs à 1000. Vous l'aurez remarqué : faire ce calcul à la main peut s'avérer difficile. Tout l'intérêt est de trouver un autre moyen, qu'il soit plutôt mathématique ou informatique. Au fur et à mesure des problèmes, la difficulté augmente, dans le sens où un calcul non réfléchi ou qui utilise la force brute ne suffit tout simplement pas car le calcul serait bien trop long. Les concepteurs des problèmes le font parfois remarquer lourdement :

It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

Note : Vous n'aurez pas le droit à une traduction cette fois, bien fait pour vous !

Vous êtes donc obligés, en raison des nombres relativement élevés, de chercher une optimisation de l'implémentation naïve. Le plus impressionnant est que les concepteurs assurent que tous les problèmes peuvent être résolus sur une machine modeste en moins d'une minute. Tout le fun est alors dans la recherche de l'algorithme ! Celle-ci n'est parfois pas simple, et c'est là tout l'intérêt. Alors que trouver la somme de tous les multiples de 3 et 5 inférieurs à 1000 est trivial, trouver les 40 premiers facteurs du nombre constitué d'un milliard de 1 l'est déja moins. :P

Le but avoué est de permettre à n'importe quel public de découvrir de nouveaux concepts, et de faire ceci tout en s'amusant avec son langage préféré. C'est un des aspects les plus intéressants : le moyen utilisé importe peu, et cette liberté permet de comparer différentes manières de résoudre un même problème. Lorsque vous avez résolu un problème, il est possible de voir les solutions des autres membres (qui sont nombreux), ce qui est parfois très enrichissant (surtout quand c'est de l'asm x86 :D). Au vu de ce succès, le Project Euler est un projet réussi.