Challenge 21

[(gile)]

Salut,

 

Ça faisait longtemps, alors un sujet sur un forum étranger m'a donné une idée.

 

Faire une routine pour remplacer toutes les occurrences d'un élément (atom) dans une liste et dans les sous listes qu'elle peut contenir quelque soit leur niveau d'imbrication.

Pour être polyvalente, la routine pourra admettre 3 arguments comme la fonction subst :

- le nouvel élément

- l'élément à remplacer

- la liste

 

Exemple, remplacer tous les 1 par des 2 dans les listes suivantes :

 

(toto 2 1 '((1 4) (1 3) (5 5) (1 1))) --> ((2 4) (2 3) (5 5) (2 2))

(toto 2 1 '(1 (4 (1 (3 1)) 1) 1 2 1)) --> (2 (4 (2 (3 2)) 2) 2 2 2)

 

 

[lovecraft]

bonsoir,

 

Quelle bonne nouvelle, ca fait longtemps que l'on n'a pas eu ce genre de challenge.

je vais essayer de regarder mais , je compte sur votre aide.

 

@plus

 

LB

[Matt666]

Salut Gile

Cool un challenge !

 

Voici un truc récursif qui devrait fonctionner...

(defun c21 (n o l / tmp)
   (setq 
       tmp l 
       l nil
   )
   (while tmp
       (if (eq (type (car tmp)) 'LIST)
           (setq l (cons (c21 n o (car tmp)) l))
           (if (eq o (car tmp))
               (setq l (cons n l))
               (setq l (cons (car tmp) l))
           )
       )
       (setq tmp (cdr tmp))
   )
  (reverse l)
)

 

Je n'ai pas réussi à le faire avec mapcar, mais je tente !!

 

A bientot.

Matt.

 

[Edité le 30/6/2008 par Matt666]

[Bred]

:D :D :D

Bravo Matt666 !!!!

http://images.tribe.net/tribe/upload/photo/d8f/db6/d8fdb623-c3ef-41ea-ab42-cb6105a1b0bf

 

J'y ai passé quelques heures... et la seule chose que j'ai réussis c'est à me coucher beaucoup trop tard...

 

[Matt666]

Merci Bred :red: :red: :red: :red:

[(gile)]

Salut,

 

Bien vu Matt666, ta solution ressemble à la mienne.

Je pense aussi que la récursivité s'impose pour ce type de problème (niveau d'imbrication des liste variable).

 

Deux petites remarques :

- il me semble qu'il manque un (reverse ...)

- tu dois pouvoir simplifier la façon dont tu vides et remplis les listes (tmp et l)

[(gile)]

Re,

 

Pour Matt666, je précise ma deuxième remarque. Tu commences par remplir tmp avec le contenu de l et tu vides l. Et dans la boucle (while ...) tu vides tmp pour reconstituer[ b]l[/b] avec les nouvelles valeurs. Tu pourrais directement "transvaser" l dans une nouvelle liste qui aprés un reverse serait le résultat.

 

Deux pistes différentes :

 

Les formes récursives permettent d'effectuer l'équivalent de ce que fait la boucle dans le code de Matt666 sans avoir à créer de nouvelle liste ni faire de reverse à la fin (voir remove_doubles, par exemple)

 

L'utilisation d'un appel récursif dans une expression mapcar permet, il me semble, de faire une routine plus concise et peut-être plus "compréhensible", mais moins rapide qu'une routine "tout récursif".

 

 

[Matt666]

Tu commences par remplir tmp avec le contenu de l et tu vides l. Et dans la boucle (while ...) tu vides tmp pour reconstituer[ b]l avec les nouvelles valeurs. Tu pourrais directement "transvaser" l dans une nouvelle liste qui aprés un reverse serait le résultat.

Je vois ce que tu veux faire... Je vais voir ça...

 

L'utilisation d'un appel récursif dans une expression mapcar permet, il me semble, de faire une routine plus concise et peut-être plus "compréhensible", mais moins rapide qu'une routine "tout récursif".

Oui, j'ai tenté de faire un routine avec mapcar... Mais je n'arrive pas à modifier la valeur à changer... Je ne trouve rien qui le permette, à part un bricolage moche auquel je viens de penser... genre (car (subst n (list o) (list x)))... Je sais pas si ça fonctionne, mais je trouve cela un peu trop bricolé...

 

ta solution ressemble à la mienne.

Ca ne m'étonne pas ! Tes routines sont mes modèles de code simple, concis, efficace, et beau aussi. Forcément, cela transpire dans mes routines :)

 

Je continue à m'arracher les cheveux : :P

[Matt666]

Ca a l'air de fonctionner... :D :D :D

;;;Routine while
(defun c21_w (n o l / tmp)
   (while l
       (if (eq (type (car l)) 'LIST)
           (setq tmp (cons (c21 n o (car l)) tmp))
           (if (eq o (car l))
               (setq tmp (cons n tmp))
               (setq tmp (cons (car l) tmp))
           )
       )
       (setq l (cdr l))
   )
   (reverse tmp)
)

;;;Routine mapcar
(defun c21_m (n o l)
   (mapcar 
       '(lambda (x)
           (if (eq (type x) 'LIST)
               (c21 n o x)
               (if (eq o x)
                   [surligneur] (car (subst n o (list x)))  [/surligneur]
                   x
               )
           )
       )
       l
   )
)

C'est juste le truc surligné qui n'est pas très élégant...

Merci Gile pour tes conseils ! :) :)

 

[Edité le 1/7/2008 par Matt666]

[(gile)]

Tu n'est vraiment pas loin avec mapcar (trop fatigué ou pas bien réveillé ?)

 

Effectivement (car (subst n o (list x))) est moins élégant que le résultat de l'expression...

[Matt666]

(defun c21_m (n o l)
   (mapcar 
       '(lambda (x)
           (if (eq (type x) 'LIST)
               (c21 n o x)
               (if (eq o x) n x)
           )
       )
       l
   )
)

!!!!

 

trop fatigué ou pas bien réveillé ?

Ah... Grillé...

 

Ya des fois où on réfléchit trop !

[(gile)]

Salut,

 

Je donne ici la solution que j'avais donné là.

Elle est entièrement récursive (pas de while ni mapcar) et semble légèrement plus rapide, du moins sur le type de liste donné en exemple.

 

(defun nested-subst (new old lst)
 (if lst
   (if	(listp (car lst))
     (cons (nested-subst new old (car lst))
    (nested-subst new old (cdr lst))
     )
     (if (equal old (car lst))
(cons new (nested-subst new old (cdr lst)))
(cons (car lst) (nested-subst new old (cdr lst)))
     )
   )
 )
) 

[Matt666]

Très intéressant Gile ! Merci pour cette routine...