SUITE DE CONWAY (LOOK AND SAY SEQUENCE) - GENERATEUR

Commentaire de cirec le 12/08/2006 16:34:51 administrateur CS

Ben ouais c'est d'une logique ...

Bon on me l'avais déjà fait :-)
mais c'est d'un "con"
si je ne suis pas trompé ce devrait être la ligne suivante :
11131221131211131231121113112221121321132132211331222113112211

bien :-)
@+

Commentaire de Forman le 12/08/2006 20:27:41

Je la connaissais aussi déjà celle là      ;)
Mais étudier la suite ainsi définie est un vrai casse-tête:
je m'étais posé des questions dessus il y a quelques années: peut-on exprimer la longueur du n-ième terme de la suite en fonction de n? Ou au moins trouver un équivalent vers l'infini?

La conclusion est: je ne sais ni démontrer que la suite est de longueur croissante (en effet, sans rien dévoiler, on peut imaginer des termes tels qu'en calculant le terme suivant la longueur obtenue est strictement inférieure, par exemple 111333) ni même qu'elle n'est pas périodique (il existe en effet par exemple un mot de 2 caractères tel que le mot suivant est le même: 22). Et pourtant, j'y ai passé du temps, mdr...

Les seules choses que je sais démontrer sur cette suite (et c'est très facile à faire, ce sont des propriétés immédiates) c'est:
-elle ne contient que les 3 chiffres 1,2 et 3
-la longueur du n-ième terme est plus petite que (ou égale à) 2^n

J'ai réécrit l'algorithme pour calculer un des termes à partir du précédant, de façon à ce qu'il aille plus vite (moins de réallocation de mémoire):

function f(s:string):string;
var
  p,q:PChar;
  c,d,e:Char;
begin
  SetLength(Result,2*Length(s));
  p:=PChar(s);
  q:=PChar(Result);
  c:=p^;
  repeat
    e:='0';
    repeat
      Inc(p);
      d:=p^;
      Inc(e);
    until d<>c;
    q^:=e;
    PChar(q+1)^:=c;
    q:=q+2;
    c:=d;
  until c=#0;
  SetLength(Result,Integer(q)-Integer(PChar(Result)));
end;

procedure FastGenereEnigme(const TS:TStrings;const n:Word=12);
var
  a:Integer;
begin
  TS.Clear;
  TS.Add('1');
  for a:=0 to n-1 do
    TS.Add(f(TS[a]));
end;

Ca fonctionne si on considère que calculer le terme suivant de la suite va au plus doubler la longueur (d'où l'explication du SetLength(Result,2*Length(s))). Pour calculer le 50ième terme, GenerateEnigme met 25 secondes alors que FastGenereEnigme met 32 millisecondes... Ca démontre encore, s'il en était besoin, que les allocations de mémoire cachées rallentissent énormément le code: lorsqu'on écrit a+b (où a et b sont des chaînes de caractères) il y a une réallocation de mémoire pour stocker le résultat de la concaténation.

L'algorithme à optimiser est un bon exemple: je propose le challenge de celui qui donnera un algorithme (pour la fonction f) calculant le plus vite possible le 71ième terme de la suite (à partir du 72ème, le terme devient trop grand et provoque une exception EOutOfMemory chez moi). Record à battre: 7062 millisecondes pour calculer le 71ième terme de la suite. Bien sûr, pour que ça compte, il faut que les 2 algo soient lancés sur la même machine!

A vos claviers       ;-)

Commentaire de Forman le 12/08/2006 22:14:02

> Visiblement, Forman, tu es le gars qui aime aller au fond des choses.
Lol, ça doit être une déformation professionnelle, à force de faire des maths...

Commentaire de japee le 12/08/2006 23:26:52 administrateur CS

Un duel au lever du jour ?

Il était une fois à l'ouest de DelphiFr.com...
On dirait que les flingues vont parler.
Ames sensibles, passez votre chemin ! ;-)

Commentaire de Forman le 13/08/2006 11:49:51

Il suffit de faire Memo1.Lines.BeginUpdate avant de commencer à manipuler Memo1.Lines et ne pas oublier Memo1.Lines.EndUpdate après avoir fini de changer les lignes du mémo. De cette façon, tu empèches la fenêtre de se réafficher 50 fois de suite, ce qui gagne du temps.

Commentaire de Caribensila le 13/08/2006 14:21:33

Horreur!!!!  J'ai tout de suite trouvé la logique.
Et maintenant je suis tourmenté par une profonde angoisse quant à mon age mental ou mon incurie en math.
Et même, par moment, une tragique question me hante: et si c'était les deux?!
mdr
En tout cas, c'est bien plus rigolo et plus beau que la suite de Steinhaus...
( Qui a demandé: "c'est quoi la beauté en math"? ;)

Commentaire de f0xi le 13/08/2006 17:09:04 administrateur CS

WHOAAAAAA! J'ai compris!

en fait, chaque suite et le logarythme naturel exposant 4 au carré plus pi sinus 2 fois 16 divisé  par 666.

ch'est pa cha ?

@florenth : gettickcount ça pue. c'est aussi précis qu'un lancé de vache avec un train qui roule a 120Km/h

Commentaire de japee le 13/08/2006 17:13:54 administrateur CS

"aussi précis qu'un lancé de vache avec un train qui roule a 120Km/h"
Ca a rapport avec la théorie relativité restreinte ? ptdr...

Commentaire de Caribensila le 13/08/2006 18:17:57

Z'avez vu ça?

truc
1t1r1u1c
111t111r111u111c
311t311r311u311c
13211t13211r13211u13211c
111312211t111312211r111312211u111312211c
Mathématiquement parlant, c'est rigolo...
'sais pas quoi en conclure, mais certains matheux y trouveront certainement du grain à moudre... ;)

Commentaire de Caribensila le 13/08/2006 18:49:43

Plus clair comme ça, peut-être:




truc
1t 1r 1u 1c
111t 111r 111u 111c
311t 311r 311u 311c
13211t 13211r 13211u 13211c
111312211t 111312211r 111312211u 111312211c

Commentaire de japee le 13/08/2006 19:17:54 administrateur CS

Il semblerait que là non plus on ne puisse pas dépasser le chiffre 3.
Mais à mon goût, la progression est trop régulière et prévisible à des kilomètres... ;-)

Commentaire de f0xi le 13/08/2006 19:23:04 administrateur CS

bon, je participe au defi :

Delphi 7,
Atlhon XP 2700+ 2166Mhz (13x167) Thoroughbred-B,
MSI KT4VL chip VIA Apollo KT400,
DDR PC2700 @ 333Mhz 2.5-3-3-7 CR2T
Windows XP Pro SP1, 23 processus, CPU Load 0-2%, Avast/Firefox/Delphi 7

Compteur de temps : HPC millisecondes
Taille du buffer  : 2048 bytes

40 Wakygneuts / Temps : 1,9776 ms / Taille : 7,87 Ko
70 Wakygneuts / Temps : 3,4915 ms / Taille : 17,79 Ko
140 Wakygneuts / Temps : 7,0836 ms / Taille : 40,95 Ko
280 Wakygneuts / Temps : 14,0205 ms / Taille : 87,24 Ko
560 Wakygneuts / Temps : 28,5095 ms / Taille : 179,86 Ko
1120 Wakygneuts / Temps : 56,6877 ms / Taille : 365,06 Ko
2240 Wakygneuts / Temps : 115,0914 ms / Taille : 735,48 Ko

Commentaire de Caribensila le 13/08/2006 19:31:40

J'ai rien dit, ok?  lol

Commentaire de f0xi le 13/08/2006 19:51:31 administrateur CS

par contre y'a deux choses amusantes dans cette enigme,
non seulement ça ne compte que jusque 3,
mais en plus la taille des reponses ne peu pas depasser 350 chiffres.
ce qui permet d'ajuster mon buffer a 351 au lieu de 2048 ...

5000 Wakygneuts / Temps : 254,7406 ms / Taille : 1648,29 Ko

quelques diziemes de millisecondes en moins ...


procedure MakeWakyStrings(const AStrings : TStrings; const ACount : integer = 70);
   function GetNextWaky(const SFrom : string) : string;
   var
     PResult : PChar;
     c, e    : Char;
     i       : byte;
   begin
     SetLength(Result,351);
     PResult := PChar(Result);
     i := 1;
     c := SFrom[i];
     repeat
       e:='0';
       repeat
         Inc(i);
         Inc(e);
       until c <> SFrom[i];
       PResult[0] := e;
       PResult[1] := c;
       inc(PResult,2);
       c := SFrom[i];
     until c = #0;
     SetLength(Result,Integer(PResult)-Integer(PChar(Result)));
   end;
var
  i : Integer;
begin
  with AStrings do begin
       Clear;
       BeginUpdate;
       Add('1');
       for i := 0 to ACount-2 do
           add(GetNextWaky(Strings[i]));
       EndUpdate;
  end;
end;

Commentaire de japee le 14/08/2006 20:15:38 administrateur CS

Salut Kenavo,

Ouais, bien vu : 111333 ne peut être valide ou je n'ai rien compris non plus...

Bon, on dirait que l'ambiance est un peu retombée depuis hier. Ils sont tous partis en laissant la lumière allumée. ;-)

Commentaire de japee le 14/08/2006 21:28:05 administrateur CS

"Laisse donc la lumière allumée !"
Mais bon, tu comprends, déjà ils rentrent sur la page, ils s'essuient même pas les pieds. Premièrement.
Et puis on fait la fête, tout ça, on rigole bien, mais je sais déjà qui va se taper le ménage, hein ?
Enfin, je râle, mais je suis bonne pâte, dans le fond. Oh, ils le savent bien va !
Et y'en a qui en profitent. Qui abusent, quoi...

Commentaire de japee le 15/08/2006 01:20:37 administrateur CS

Oui, j'avais commencé un programme de test plus élaboré que celui que j'ai envoyé ici, mais qui n'est pas terminé.
Il apparaît que la ligne 25 est tronquée, sans doute un problème de longueur, mon programme de test vérifiera ça quand il sera achevé :
ligne 25 : 13211321
"fausse" ligne 26 : 13112221
ligne 27 (en fait la ligne 26) : 111312211312
Pfff... en fait, je suis complètement paumé, je crois que je vais voir ça demain... ça a l'air moins simple que je ne le pensais au premier abord.
A +

Commentaire de CptPingu le 16/08/2006 03:47:28 administrateur CS

Cette suite s'appelle la suite de Conway.

De nombreuse informations sont présente ici:
http://fr.wikipedia.org/wiki/Suite_de_Conway

Commentaire de japee le 16/08/2006 10:32:23 administrateur CS

Merci, CptPingu, je rajouterai cette information dans la présentation (et dans le titre).

Commentaire de Forman le 16/08/2006 16:48:37

Joli et élégant! (même si à la fin le code devient difficilement compréhensible...)

Commentaire de f0xi le 16/08/2006 18:09:58 administrateur CS

procedure MakeWakyStrings(const AStrings : TStrings; const ACount : byte = 1);
   function GetNextWaky(const SFrom : string) : string;
   var
     PResult : PChar;
     c, e    : Char;
     i       : Cardinal;
   begin
     SetLength(Result,65536 shl 9);
     PResult := PChar(Result);
     i := 1;
     c := SFrom[i];
     repeat
       e:='0';
       repeat
         Inc(i);
         Inc(e);
       until c <> SFrom[i];
       PResult[0] := e;
       PResult[1] := c;
       inc(PResult,2);
       c := SFrom[i];
     until c = #0;
     SetLength(Result,Integer(PResult)-Integer(PChar(Result)));
   end;
var
  n : Integer;
begin
  if ACount > 60 then exit;
  with AStrings do begin
       Clear;
       BeginUpdate;
       //HPC := ExtSystem.GetHPClock;
       Add('1');
       for n := 0 to ACount-2 do begin
           add(GetNextWaky(Strings[n]));
       end;
       //HPC := ExtSystem.GetHPClock - HPC;
       EndUpdate;
       //waket := 0;
       //for n := 0 to Count-1 do
       //    if Length(Strings[n]) > Waket then Waket := Length(Strings[n]);
  end;
end;

Commentaire de japee le 16/08/2006 20:46:23 administrateur CS

Salut, JulioDelphi.

And my dream comes true...
Y'en a qui vont penser que je suis pistonné, lol ;-)
Faudra aussi que je rajoute un BeginUpdate et EndUpdate à mon pauvre code poussif, ça améliore gravement la vitesse.
Même si ça n'était pas mon but initial, mais bon, il commence à avoir l'air minable, le pauvre...

Commentaire de japee le 17/08/2006 22:51:14 administrateur CS

Ca m'a l'air net et sans bavures, avantage Florenth.
Mon code est largué, mais alors très très loin derrière.
Je laisse à ceux qui ont des configs musclées le soin d'analyser finement.
Chez moi, à partir de 40 lignes, mon proc' est à deux doigts de l'infarctus...