Challenge récursive.

[Patrick_35]

Bonjour

 

Pour faire suite à ce sujet, rien ne vaut un bon exercice.

L'idée est de déterminer si j'ai un double dans une liste, et de manière récursive.

(gile), comme tu es notre maitre à tous, tu as un handicap d'une journée ;)

 

Exemples :

(doublon '(1 2 3 4 5 6 7 8 9)) --> nil

(doublon '(1 2 3 4 5 6 7 8 9 1)) --> T

(doublon '(1 2 3 4 5 1 6 7 8 9)) --> T

 

(doublon '((1 2) (2 3) (4 5) (6 7) (8 9))) --> nil

(doublon '((1 2) (2 3) (4 5) (6 7) (8 9) (1 2))) --> T

 

(doublon '((1 2 3) (2 3) (4 5) (6 7) (8 9) (1 2))) --> nil

(doublon '((1 2 3) (2 3) (4 5) (6 7) (8 9) (1 2 3))) --> T

 

@+

[GEGEMATIC]

Salut Patrick,

dans ton exemple, je ne vois pas où tu as besoin de la récursivité ?

donc je propose ça, hors sujet car non récursif, mais qui donne le même résultat que toi:

(defun doublon (lst / true 1er mb)
 (while (and lst (not true))
   (setq 1er (car lst))

   (setq true (and (setq mb (member 1er lst))
	    (member 1er (cdr mb))))
   	 (setq lst (cdr lst))
 )
   true
)

Pour avoir besoin de la récursivité je pense qu'on serai dans:

(ContientDoublon '((1 2 3) (2 3 3) (4 5) (6 7) (8 9) (1 2 3)))-> T

dis moi si quelque chose m'échappe ?

a+

gégé

[Patrick_35]

dans ton exemple, je ne vois pas où tu as besoin de la récursivité ?

Tu peux toujours utiliser l'itératif. C'était plus pour éviter l'utilisation des variables et c'est aussi pour travailler sur le récursif. Essaye une itérative sans variable.

 

Il n'y a qu'un seul cas à ma connaissance qui nécessite le récursif, c'est l'arborescence.

 

@+

[(gile)]

Il n'y a qu'un seul cas à ma connaissance qui nécessite le récursif, c'est l'arborescence.

 

1+ avec Patrick_35 seul le traitement des structures de données récursives (typiquement les arborescences) nécessite un traitement récursif.

Mais parfois la récursivité permet de résoudre simplement des problèmes complexes (fonction factorielle ou suite de Fibonacci pour les exemples les plus courant).

Et il est des individus qui "pensent récursif" ou pour qui l'approche récursive récursive est plus immédiate que l'approche itérative. À ce propos, je pense que tu peux aussi mettre un handicap d'une journée à VDH-bruno.

 

Pour plus coller au sujet qui a motivé ce challenge je vais en proposer un autre facile.

[Patrick_35]

À ce propos, je pense que tu peux aussi mettre un handicap d'une journée à VDH-bruno.

Oui, tu as raison. Et à tous ceux qui pensent facilement récursif.

 

@+

[(gile)]

Je pense que ce challenge est suffisamment facile pour que ceux-là se retiennent.

[GEGEMATIC]

Je pense que ce challenge est suffisamment facile pour que ceux-là se retiennent.

facile ?

j'utilise souvent la récursivité pour parcourir des arborescences de fichier xml, parcourir des listes de liste,

et là ça m'inspire.

la je vois pas l’intérêt donc pour moi c'est carrément impossible, je jette l'éponge ...

je regarderai la solution demain !

a+

gégé

[bonuscad]

Essaye une itérative sans variable.

 

Bonjour,

Je triche un peu, mais avec une fonction anonyme? pas de variable!

(defun doublon (lst / )
(apply 'or (mapcar '(lambda (x) (if (member x (cdr (member x lst))) T)) lst))
)

[x_all]

Punaise les gars... avec votre manie de nous apprendre à pécher plutôt que de nous donner un poisson, vous allez nous filer mal à la tête...

[DenisHen]

...vous allez nous filer mal à la tête...

C'est déjà fait... ;)

[Fraid]

j'vais etre en retard pour mes plans...

je remet cela pour à ce soir, j'y arrive pas non plus

[(gile)]

facile ?

j'utilise souvent la récursivité pour parcourir des arborescences de fichier xml, parcourir des listes de liste,

et là ça m'inspire.

la je vois pas l’intérêt donc pour moi c'est carrément impossible, je jette l'éponge ...

je regarderai la solution demain !

a+

gégé

 

Et pourtant, une liste LISP est une liste chaînée, structure qui est une forme d'arbre binaire (voir ici).

[Patrick_35]

Bonjour,

Je triche un peu, mais avec une fonction anonyme? pas de variable!

(defun doublon (lst / )
(apply 'or (mapcar '(lambda (x) (if (member x (cdr (member x lst))) T)) lst))
)

Bravo Bonus. je ne l'avais pas vu comme ça, mais chapeau :D

 

@+

[GEGEMATIC]

Bravo Bonus. je ne l'avais pas vu comme ça, mais chapeau :D

Patrick,

je comprends de moins en moins:

pour moi ton challenge, c'est bien d'avoir une routine doublons qui s'appelle en récursivité ?

[Patrick_35]

Patrick,

je comprends de moins en moins:

pour moi ton challenge, c'est bien d'avoir une routine doublons qui s'appelle en récursivité ?

Oui, mais cela ne m'empêche pas d'apprécier une autre manière de faire.

Le challenge reste une récursive.

 

@+

[x_all]

bah! le but n'est pas de résoudre le problème mais le challenge...

 

malheureusement, journée chargée

[GEGEMATIC]

Patrick, il est tard et je te maudis !

ne me fais plus jamais ça, pas pu me sortir cette histoire de la tête !

c'est peut être pas la bonne version ,mais ça marche

 

Commande: (doublon '(1 2 3 4 5 6 7 8 9))

nil

Commande: (doublon '(1 2 3 4 5 6 7 8 9 1))

T

Commande: (doublon '(1 2 3 4 5 1 6 7 8 9))

T

Commande: (doublon '((1 2) (2 3) (4 5) (6 7) (8 9)))

nil

Commande: (doublon '((1 2) (2 3) (4 5) (6 7) (8 9) (1 2)))

T

Commande: (doublon '((1 2 3) (2 3) (4 5) (6 7) (8 9) (1 2)))

nil

Commande: (doublon '((1 2 3) (2 3) (4 5) (6 7) (8 9) (1 2 3)))

T

(defun doublon (lst)
(cond
 ((and lst
  (listp lst)	
  (member (car lst) (cdr lst)))
 t)
 ((and lst
  (listp lst)	
  )
 (doublon (cdr lst))
)
)
)

[(gile)]

Tu vois que c'est possible ;)

[GEGEMATIC]

Tu vois que c'est possible ;)

Oui mais vous êtes tous les 2 de dangereux pousse au divorce !

sans rancune !

pire qu'une chanson de Claude François au petit déjeuner !

a+

Gégé

[x_all]

le mienne est moins jolie

(defun doublon (lstR / rep)

(if	(and (cdr lstR) (member (car lstR) (cdr lstR)))
 	(setq rep T)
 	(doublon (cdr lstR))
)

rep
 
 )

[(gile)]

Bravo à tous les deux, vous avez répondu à la demande, après, c'est juste une question d'élégance du code.

 

@GEGEMATIC, on doit pouvoir supprimer certaines redondances

 

@x_all, tu peux éviter tous les (setq ...), par exemple :

(progn
 (setq lstR (cdr lstR))
 (doublon lstR)
)

peut s'écrire beaucoup plus simplement.

[x_all]

@ (gile)j'arrive tout juste à marcher et tu veux me faire courir...

 

(edit)

@patrick

merci pour l'exercice, ça m'a décoincé une vertèbre, je vais pouvoir dormir..

[Fraid]

Décidément, je bute, j'ai finis par regarder, je n’étais pas loin.

et celle que je préfère pour sa concision est celle de Bonuscad.

sinon hors challenge je pense que j'aurais fait cela.

(defun doublon (lst)
(if (/= (length lst) (length (remove-doubles lst))) T) 
)

(defun remove-doubles (lst);de Gile
 (if lst (cons (car lst) (remove-doubles (vl-remove (car lst) lst))))
)

 

hihihi

[(gile)]

@x_all, plutôt qu'utiliser une variable inutile, ce qui t'oblige à utiliser (progn ...)

(progn
 (setq lstR (cdr lstR))
 (doublon lstR)
)

tu peux écrire simplement :

(doublon (cdr lstR))

 

@Fraid, celle là je l'adore (d'habitude c'est plutôt en VB qu'on voit ça), tant qu'à faire dans le verbeux, vas-y carrément :

(if (/= (length lst) (length (remove-doubles lst))) 
 T
 nil
)

qui est exactement équivalent à :

(/= (length lst) (length (remove-doubles lst)))

[(gile)]

Hors challenge, dans l'esprit de ce qu'a donné bonuscad :

 

(defun doublon (l)
 (or (vl-some '(lambda (x) (member x (cdr (member x l)))) l))
)

 

L'utilisation de (or ...) sert juste à renvoyer T au lieu de la première occurrence de (member x (cdr (member x l))). C'est uniquement pour respecter une règle du challenge, et ça serait inutile dans un autre cadre : pour les conditionnelles LISP tout ce qui n'est pas nil est considéré comme vrai.