Petit challenge de manipulation de chaine

[VDH-Bruno]

Bonjour,

 

Par erreur je suis tombé sur les codes de (gile), avant de consulter ce post et comme je suis persuadé que j’aurais écrit sensiblement le même code sur l’algorithme proposé. Je ne vais pas aller sur cette voie (et faire moins bien), donc pour le jeu de la concision je ferai remarquer que :

Inverser une donné puis permuter ses termes 2 à 2, revient à grouper les termes 2 à 2 puis à inverser le résultat. ;)

 

Dans cet esprit et très rapidement ma proposition par composition de fonctions :

(defun f (s)
 (vl-list->string (apply 'append (reverse (grp2 (vl-string->list s)))))
)

Avec la fonction grp2 définie comme suit :

;; groupe les éléments 2 à 2 
(defun grp2 (l)
 (if l (cons (list (car l) (cadr l)) (grp2 (cddr l))))
)

 

@+ Bruno

[lecrabe]

Hello Mr 3001eme Routine Lisp pour lecrabe

 

WAOUH je suis IMPRESSIONNE !

 

La Sante, Bye, lecrabe "fatigue"

[VDH-Bruno]

Hello Mr 3001eme Routine Lisp pour lecrabe

 

WAOUH je suis IMPRESSIONNE !

 

La Sante, Bye, lecrabe "fatigue"

Salut Patrice

La concision a un coût, c'est pas la plus rapide et en plus j'ai triché en prenant quelques liberté avec l’énoncé :P

Amicalement Bruno

[VDH-Bruno]

Très rapidement une autre, et je m’arrête là car je vais me mettre dans le rouge sur mon dossier en cour....

(defun f (s)
 (if (= s "")
   s
   (strcat (f (substr s 3)) (substr s 1 2)))  
)

A+ Bruno

[DenisHen]

Salut à vous tous...

 

Vous avez répondu à mon offre, et j'en suis ravi, vous me remplissez de plaisir...

 

Mais curieusement, j'attendais des MapCar ou Lambda à foison...

 

Je suis interloqué...

 

Et merci à vous, je vais vérifier et analyser vos réponses... Vous n'êtes pas sorties d'affaire.. ;)

 

J'ai l'impression que vous vous êtes réservés... Car le minimum est de 3 lignes, et ça revient à VDH, Bravo Maître...

 

Mais on attend toujours les deux lignes de maître Gilles (pardon, (gile))...

[(gile)]

Ce matin quand j'ai vu ce sujet, je me suis dit : "Super, un challenge en LISP, ça faisait longtemps."

Qui dit LISP dit liste, qui dit concision dit recursion.

Mon premier jet est donc une fonction qui utilise la chaîne sous forme de liste de caractères (codes ascii) de manière récursive.

(defun jeu (s / f)
 (defun f (l)
   (if	(cdr l)
     (vl-list* (cadr l) (car l) (f (cddr l)))
   )
 )
 (vl-list->string (f (reverse (vl-string->list s))))
)

Mais, comme l'a dit VDH-Bruno :

1. inverser les caractères

2. les grouper par paires

3. inverser les caractères de chaque paire

est équivalent à :

1. grouper les caractères par paires

2. inverser la liste des paires

Ni une ni deux, je modifie le code et l'utilisation d'un accumulateur dans la fonction récursive permet d'éviter le reverse.

Le code F# de la réponse #10 est équivalente.

(defun jeu1 (s / f)
 (defun f (l a)
   (if	(cdr l)
     (f (cddr l) (vl-list* (car l) (cadr l) a))
     a
   )
 )
 (vl-list->string (f (vl-string->list s) nil))
)

L'équivalent en style impératif (avec itération) est un peu moins concis (à peine à cause de l'utilisation d'une fonction auxiliaire.

(defun jeu2 (s / l r)
 (setq l (vl-string->list s))
 (while (cdr l)
   (setq r (vl-list* (car l) (cadr l) r)
  l (cddr l)
   )
 )
 (vl-list->string r)
)

Cherchant toujours plus de concision, j'ai pensé aux opérateurs F# qui permettent de traiter les chaînes et sous-chaînes directement comme des collections de caractères ce qui donnera la le code de la réponse #21.

L'équivalent en LISP ne fait pas gagner grand chose en terme de concision et devrait être moins efficient (LISP est meilleur avec les liste qu'avec les chaînes).

(defun jeu3 (str / f)
 (defun f (s r)
   (if	(< 1 (strlen s))
     (f (substr s 3) (strcat (substr s 1 2) r))
     r
   )
 )
 (f str "")
)

Et l'équivalent avec while.

(defun jeu4 (s / r)
 (setq r "")
 (while (< 1 (strlen s))
   (setq r (strcat (substr s 1 2) r)
  s (substr s 3)
   )
 )
 r
)

 

Voilà, un grand bravo à VDH-Bruno ! Je suis resté bloqué sur une fonction auxiliaire inutile si on traite directement la chaîne.

Je ne peux que le parodier en F# pour être à peine plus concis.

let rec f s =
   if s = "" then  s
   else  f s.[2 ..] + s.[.. 1]

 

PS: le nombre de lignes de code n'est pas un critère fiable de concision, il dépend de la façon dont le code est formaté.

[DenisHen]

PS: le nombre de lignes de code n'est pas un critère fiable de concision, il dépend de la façon dont le code est formaté.

Et surtout si on prend en compte que x lignes (voir des millions) de lisp soient interprétées comme une seule...

 

On est d'accord, le nombre de ligne n'est qu'une formalité pour mieux l'appréhender...

 

Mais c'était le challenge, je remarque que vous êtes à 8 lignes en Lisp et 3 en F#...

 

Le Lisp serait-t-il à la traine ? ? ? J'en doute... Allez, Maître Gilles, explique-nous...

 

Mais je n'ai pas testé la validité des codes... Je n'en ai pas la possibilité...

 

J'étais persuadé qu'un maître m'aurait pondu un code en deux ou trois lignes, et en Lisp... Je suis sur le cul...

 

Ce challenge serait-il "balaise" ?

[Fraid]

en php

 

<?php
      function chal($txt)
{
	 $ret = "";
	 while (1 < strlen ($txt))
	{
		 $ret = substr($txt,0, 2) . $ret;
		 $txt = substr($txt,2);
	}
    echo $ret;
 }
 echo chal("5637159071856346");
?>
Result:
4663857190153756

[DenisHen]

Oh la vache, ça fait 15 lignes, le PHP serait-il le grand perdant ? ? ?

[Fraid]

tu cherche à comparer l'efficience d'un aspirateur avec celle d'un mixeur et d'un grille pain...

 

le grand perdant sera toujours Autolisp (en temps d’exécution).

il est interprété avant d’être exécuté.

 

F# ou Java étant compilés, sont super rapides.

 

php, c'est à part, il s'exécute sur un serveur, modifiant une page internet avant que le client le reçoive.

 

javascript est comme Autolisp, embarqué dans une application.(navigateur internet, Photoshop, Autocad...)

mais incomparable nom plus

 

en fait il n'y a pas vraiment de compétition (si f# vs Java) et le nombre de ligne de code n'a pas d'importance.

c'est le nombre de commandes et d'itérations.

[(gile)]

Encore une fois, le nombre de lignes n'est pas un critère, d'autant plus que Fraid ajoute au code la fonction son environnement et un appel à la fonction.

Pour comparer avec les fonctions LISP, C# ou F# ci dessus, il faut ne considérer que :

Java (réponse #24)

    public static String chal( String txt){
    String ret = "";
    while (1 < txt.length())
   {
       ret = txt.substring(0, 2) + ret;
       txt = txt.substring(2);
   } 
       return ret;
   }

ou PHP (réponse #33)

       function chal($txt)
       {
                $ret = "";
                while (1 < strlen ($txt))
               {
                        $ret = substr($txt,0, 2) . $ret;
                        $txt = substr($txt,2);
               }
           echo $ret;
        }

Dans tous les cas, ce qui fera la concision (hormis le nombre de lettres des symboles) c'est le nombre d'expressions.

Par exemple les fonctions récursives permettent d'éviter nombre de (setq ...).

Les langages fonctionnels (F# ou LISP) renvoie le résultat de la dernière expression sans avoir besoin d'un : return ...

D'autre part, certains langages (comme F# ou Python) sont moins bruyants (noisy) en utilisant l'indentation plutôt que des parenthèses, des accolades, des points-virgules ou des End... pour délimiter les blocs de code.

 

Ceci dit, comme le disaient Fraid et Bruno, la concision n'est pas toujours synonyme de performance.

 

En LISP les fonctions récursives sont en général moins rapides que les fonctions itératives équivalentes. Et dans ce cas précis, celles qui traitent les listes de caractères seront plus rapides que celles qui traitent directement les chaînes.

En résumé, si la dernière fonction postée par Bruno est de loin celle que je préfère pour sa concision et son élégance, c'est probablement la fonction jeu2 de la réponse #31 qui est la plus rapide.

[Fraid]

pour la comparaison Java / Javascript

 

sans rentrer dans les détails techniques, je vais parler de mes ressentis.

 

Java,

déjà, il faut quelque mois pour vraiment arriver à quelque chose.

Trois apprentissages minimum en parallèle.

Le langage (super fournis)

l'IDE (le logiciel qui te permet de programmer, netbeans ou eclipse par exemple)

la JavaDoc, la documentation officielle tellement tordue qu'elle demande vraiment une attention particulière.

C'est un langage relié quasiment à toutes les technologies.

Donc, si tu dois en utiliser une (ex: xml, html, sql...)

tu peux la rajouter, car cela demande une bonne connaissance de cette dernière.

le html est incontournable, Java l'utilise pour ces boites de dialogue par exemple.

Cela m'a servi à apprendre un langage orienté objet.

Vraiment super rapide.

Pour traiter des fichiers textes monstreux avec plus de 36000 lignes

1 seconde en java

30 en Autolisp...

Idéal pour des gros projets avec beaucoup d'objets (Minecraft par exemple est en Java)

 

Javascript

L'ovni des langages

Dans mes préférences, il vient juste après Autolisp.

Evidemment, Il ne sert à rien de vouloir écrire du javascipt dans Photoshop si tu ne le connais pas bien.

Pareil pour les pages internet, il faut connaitre html et css.

un point commun avec java, sauf que lui il travail avec alors que javascript dedans.

C'est toujours une aventure de programmer en Javascript.

Tout est permis, ou presque.

un énorme background sur le net, comme Java (heureusement)

pas besoin d'IDE

on peut tout de même écrire des programmes importants, pas que des script.

orienté objet ou non, comme on veut.

procédurale, fonctionnel c'est comme on préfère.

 

il faut tester

[nazemrap]

Bonjour,

 

j'ai fait un essai en ruby

 

str="5637159071856346"

str_rev_two=((str.reverse!).scan(/../).each{|el| el.reverse!}).join

[(gile)]

Impressionant !

Ruby semble bien équipé pour le traitement des chaînes.

Et si on fait directement :

str_rev_two=(str.scan(/../).reverse!).join 

ça donne quoi ?

[nazemrap]

Super !!!

[lecrabe]

Hello Gilles

L adaptabilite de tes vieux neurones a de multiples langages de programmation, m'enerve !

BRAVO, La Sante, Bye, lecrabe "fatigue"

[(gile)]

J'ai essayé un truc en Python sur le même principe que le code en Ruby (d'après ce que j'ai compris), mais je connais très mal ce langage.

def pyChallenge(str):
   lst = re.findall(r'..', str)
   lst.reverse()
   return ''.join(lst)

>>> pyChallenge('5637159071856346')

'4663857190153756'

[(gile)]

L adaptabilite de tes vieux neurones a de multiples langages de programmation, m'enerve !

En même temps ce n'est pas bien compliqué, le code de nazemrap est identique à l'algorithme du premier message :

str_rev_two=((str.reverse!).scan(/../).each{|el| el.reverse!}).join

1. Inverser les caractères : (str.reverse!)

2. Les grouper par 2 : .scan(/../)

3. Inverser les caractères dans chaque paire : .each{|el| el.reverse!})

 

Comme on a vu qu'on pouvait simplifier l'algorithme en :

1. Grouper les caractères par 2 : str.scan(/../)

2. Inverser la liste de paires : .reverse!

Ce n'était pas complique de réécrire le code :

str_rev_two=(str.scan(/../).reverse!).join

 

Un dernier jet en F#, je ne pense pas pouvoir faire plus concis :

let rec f = function "" -> "" | s -> f s.[2 ..] + s.[.. 1]

[VDH-Bruno]

Grand bravo à toi (gile), j'admire ton aisance et ta polyvalence :)

Bruno

[bonuscad]

Grand bravo à toi (gile), j'admire ton aisance et ta polyvalence :)

Bruno

 

C'est comme Obelix , il est tombé dedans étant petit !

[VDH-Bruno]

Voilà, un grand bravo à VDH-Bruno ! Je suis resté bloqué sur une fonction auxiliaire inutile si on traite directement la chaîne.

Bonjour à tous,

 

Merci, je profite de l’occasion pour développer un peu la réponse de (gile), sur les fonctions auxiliaires et les accumulateurs, en limitant la portée de mon propos au Lisp (je laisse à chacun d’étendre cela à son propre langage en étant bien incapable).

 

En général lorsque l’on dit récursion, 2 choix s’offre à nous la "récursion enveloppante", qui retourne les données dans le même ordre, et la "récursion terminal" qui stocke les résultats dans le corps de la fonction, puis retourne les résultats inversés (un peu comme le fais une boucle while).

 

AutoLisp n’optimisant pas la récursion terminal et ne permettant pas les arguments optionnels, en général si l’ordre des termes en retour de fonction n’a pas d’importance, on privilégie la première forme considérée comme plus concise et plus élégante. En revanche si l’ordre des termes en retour nécessite une inversion pour économiser un reverse, on privilégie la récursion terminale avec l'emploi d’une fonction auxiliaire (defun ou lambda) afin d’introduire un accumulateur (à l'occasion on peut aussi être moins puriste en déclarant une variable globale).

 

Dans notre cas :

(defun f (s)
 (if (= s "")
   s
   (strcat (f (substr s 3)) (substr s 1 2)))  
)

 

Ce qui fait la concision de cette expression, n’est pas tant le fait de traiter directement la chaine, mais plus le fait d’utiliser une fonction de concaténation, pour s’affranchir de l’utilisation d’un accumulateur et d'une fonction auxiliaire.

 

Les fonctions de concaténation de chaine, liste etc… , Comme strcat ou append porte déjà un accumulateur implicite dans leur définition.

 

Par exemple si le problème posé l’avait été sous forme de liste :

(setq l '(5 6 3 7 1 5 9 0 7 1 8 5 6 3 4 6))

 

En reprenant la fonction jeu1 donnée par (gile), avec l’emploi d’un accumulateur, on aurait :

(defun jeu1 (l / f)
 (defun f (l a)
   (if	(cdr l)
     (f (cddr l) (vl-list* (car l) (cadr l) a))
     a
   )
 )
 (f l nil)
)

_$ (jeu1 l)
(4 6 6 3 8 5 7 1 9 0 1 5 3 7 5 6)

 

Maintenant au jeu de la concision, lorsque la structure de donnée le permet et par analogie, on peut s’affranchir de la fonction auxiliaire qui n’a pour but que d’implémenter un accumulateur. En utilisant la fonction append :

(defun f (l)
 (if l
   (append (f (cddr l)) (list (car l) (cadr l)))
 )
)

_$ (f l)
(4 6 6 3 8 5 7 1 9 0 1 5 3 7 5 6)

 

Avec ce type de fonction, on passe de la récursion terminal à enveloppant et vice-versa juste en changeant la position des appels à la fonction définie récursivement.

Pour l’exemple la même fonction en modifiant la position des arguments dans la fonction append, la fonction retourne les données sans en modifier l’ordre:

(defun g (l)
 (if l
   (append (list (car l) (cadr l)) (g (cddr l)))
 )
)

_$ (g l)
(5 6 3 7 1 5 9 0 7 1 8 5 6 3 4 6)

 

Bonne lecture

Bruno

[VDH-Bruno]

C'est comme Obelix , il est tombé dedans étant petit !

 

Je crois qu'il est tombé dedans quant il était grand, car il est arrivé sur le tard, c'est d'autant plus remarquable :)

[Curlygoth]

1°) choix du nombre à traiter

2°) vérification si le nombre a 16 caracteres et est un nombre ou non

3°) Traitement

4°) Résultat dans Message box

 

Sub Challenge_VBA()
nombre = "5637159071856346"
T_NOMBRE = 16
nombre = InputBox("Entrer un nombre de 16 caractères : ", "Entré un nombre", nombre)
If Len(nombre) <> T_NOMBRE Or IsError(cdbl(nombre)) = True Then MsgBox ("Nombre non valide"): Exit Sub
nombre = StrReverse(nombre)
For i = 1 To T_NOMBRE - 1
DEB_ = Left(nombre, i - 1)
FIN_ = Right(nombre, T_NOMBRE - i - 1)
L1 = Mid(nombre, i, 1)
L2 = Mid(nombre, i + 1, 1)
If L1 Mod 2 = 0 And L2 Mod 2 = 0 Then
   nombre = DEB_ & L2 & L1 & FIN_
   Else
End If
Next i
X = MsgBox("Résultat : " & nombre, vbOKOnly, "Résultat du traitement")
End Sub

 

Merci de m'avoir finalement autorisé à participer !

[(gile)]

Je me doutais bien qu'on pouvait faire plus concis avec Python :

def pyChallenge(str):
   return ''.join(reversed(re.findall(r'..', str)))

[VDH-Bruno]

Je me doutais bien qu'on pouvait faire plus concis avec Python :

def pyChallenge(str):
   return ''.join(reversed(re.findall(r'..', str)))

Chapeau bas, très intéressant, j’ai récemment installer l’interpréteur Python sur mon ordi perso, pour le suivie scolaire de ma fille qui rentrera au Lycée l’année prochaine, mais j’avoue ne pas encore avoir trop regardé comment cela fonctionne, j’espère pouvoir me libérer un peu de temps pour ça cette été… A par AutoLisp, il n’y a que sur Scratch ou j’ai développé quelques compétences (Scratch c’est que de la programmation impérative et procédurale… Une horreur pour mon cerveau je suis vraiment pas outillé pour ça, mais au collège la barre et pas trop haute j'arrive encore à suivre ).

 

Peut être que l'année prochaine je saurai dire si il y a moyen de faire mieux... en Python