Challenge 26

[ElpanovEvgeniy]

Je propose d'écrire trois différents programmes, mais ils sont semblables.

C'est une tâche très intéressante - on peut la décider par la quantité immense de moyens.

 

1. (Union lst1 lst2)

2. (Intersection lst1 lst2)

3. (Subtraction lst1 lst2)

 

L'exemple

 

(setq lst1 '((1 . 5) (8 . 10) (20 . 20))

lst2 '((2 . 2) (4 . 6) (9 . 30))

) ;_ setq

 

(Union lst1 lst2) => '((1 . 6) (8 . 30))

(Intersection lst1 lst2) => '((2 . 2) (4 . 5) (9 . 10) (20 . 20))

(Subtraction lst1 lst2) => '((1 . 1) (3 . 3) (8 . 8))

[bseb67]

:casstet:

Là moi je n'y comprend rien .

[ElpanovEvgeniy]

:casstet:

Là moi je n'y comprend rien .

 

On regrette, je ne connais pas la langue française...

union == Le groupement

 

(Union '((2 . 4)) '((3 . 6))) >> '((2 . 6))

(Union '((2 . 4)) '((6 . 8))) >> '((2 . 4) (6 . 8))

(Union '((2 . 6)) '((2 . 4))) >> '((2 . 6))

(Union '((2 . 4) (6 . 8)) '((2 . 4))) >> '((2 . 4) (6 . 8))

(Union '((2 . 4) (6 . 8)) '((2 . 5))) >> '((2 . 8))

 

Il est si plus compréhensible ?

 

[Edité le 10/9/2008 par ElpanovEvgeniy]

[bseb67]

:D ok, ben là je comprend.

en fait tes (x y) sont des intervalles, je ne sais pas ce que j'ai aujourd'hui,

mais j'ai le cerveau complètement à l'envers :P

[ElpanovEvgeniy]

:D ok, ben là je comprend.

en fait tes (x y) sont des intervalles, je ne sais pas ce que j'ai aujourd'hui,

mais j'ai le cerveau complètement à l'envers :P

 

Chez moi seulement X:

' (("le début" . "La fin") ("le début" . "La fin") ... ("le début" . "La fin"))

[ElpanovEvgeniy]

>all

J'ai pu expliquer?

[bseb67]

ElpanovEvgeniy=> it's ok, if i wrote (x y) it was to say x=begin y=end,

not x and y for position.

I think that i have a same program which do this, but in c++ or in java.

 

 

[(gile)]

Salut

 

EDIT : je pense avoir compris...

 

Donc, si j'ai bien compris, un premier jet pour UNION, mais on doit pouvoir faire mieux, je suis fatigué ce soir...

 

(defun union (l1 l2)
 (cond
   ((null l1)
    (if (cdr l2)
      (union (list (car l2)) (cdr l2))
      l2
    )
   )
   ((null l2)
    (if (cdr l1)
      (union (list (car l1)) (cdr l1))
      l1
    )
   )
   ((     (cons (car l1) (union (cdr l1) l2))
   )
   ((     (cons (car l2) (union l1 (cdr l2)))
   )
   (T
    (union
      (cons (cons (min (caar l1) (caar l2)) (max (cdar l1) (cdar l2)))
     (cdr l1)
      )
      (cdr l2)
    )
   )
 )
) 

 

[Edité le 12/9/2008 par (gile)]

[(gile)]

Une autre méthode pour Union.

 

(defun union (l1 l2)
 (setq	l1 (vl-sort
     (append l1 l2)
     (function
       (lambda (x1 x2) (	     )
   )
l2 nil
 )
 (while (cdr l1)
   (if	(or (	    (	)
     (setq l1 (cons (cons (min (caar l1) (caadr l1))
		   (max (cdar l1) (cdadr l1))
	     )
	     (cddr l1)
       )
     )
     (setq l2 (cons (car l1) l2)
    l1 (cdr l1)
     )
   )
 )
 (reverse (cons (car l1) l2))
) 

 

[Edité le 12/9/2008 par (gile)]

[Patrick_35]

Bonjour

 

Génial, un challenge d'ElpanovEvgeniy :D

Le seul problème est de le comprendre :(

 

 

Hello

Great, a challenge of ElpanovEvgeniy :D

The only problem is to understand :(

 

@+

[(gile)]

En analysant plus attentivement les exemples, je pense avoir finalement compris.

 

Il s'agirait de ne considérer que les entiers, chaque paire indique le premier et le dernier terme d'une suite incrémentée de 1.

on pourrait, par exemple, transcrire : ((2 . 4) (6 . 8)) en ((2 3 4) (6 7 8))

 

Un petit graphique explicatif :

 

http://img383.imageshack.us/img383/4576/challenge26vq7.png

 

[Edité le 12/9/2008 par (gile)]

[(gile)]

J'ai modifié les 2 routines "union" ci-dessus, elles fonctionnent désormais avec tous les exemples données par Evgeniy.

 

J'entrevois d'autres façons de procéder et il reste intersection et soustraction, ce qui laisse pas mal de champ à d'autres solutions...

 

J'espère avoir débroussaillé un peu le terrain.

[bonuscad]

Il s'agirait de ne considérer que les entiers, chaque paire indique le premier et le dernier terme d'une suite

 

Personnellement j'avais compris la même chose d'après les exemples, en tout cas pour l'union.

 

Tes graphiques m'ont aidé pour l'intersection et la soustraction, à la lecture je n'avais pas vraiment saisi ceux-ci.

 

En aparté: Ces challenge bien qu'intéressant ne me motive pas trop car je ne vois jamais une application concrète à mes problèmes que je peux rencontrer lors d'un développement.

En plus ceux-ci gravitent toujours sur les fonctions récursives ou les boucles conditionnelles.

 

C'est peut être parce que je ne suis pas très doué avec ses fonctions récursives... :calim:

[bseb67]

Le concept est simple:

union = or

intersection = and

différence = xor

 

Mais reste toujours la difficulté de l'implémentation.

[ElpanovEvgeniy]

En analysant plus attentivement les exemples, je pense avoir finalement compris.

 

Il s'agirait de ne considérer que les entiers, chaque paire indique le premier et le dernier terme d'une suite incrémentée de 1.

on pourrait, par exemple, transcrire : ((2 . 4) (6 . 8)) en ((2 3 4) (6 7 8))

 

Un petit graphique explicatif :

 

http://img383.imageshack.us/img383/4576/challenge26vq7.png

 

[Edité le 12/9/2008 par (gile)]

 

Le concept est simple:

union = or

intersection = and

différence = xor

 

Mais reste toujours la difficulté de l'implémentation.

 

Oui!

Vous ont écrit exactement.

Notamment les programmes si doivent travailler...

[Patrick_35]

Ah ok, je commence à comprendre.

 

Reste à prendre le temps pour répondre au challenge

 

@+

[(gile)]

Salut,

 

Voilà 6 jours que Evgeniy a proposé un challenge et toujours pas de réponse (à part mes 2 premières tentatives)...

 

Eut égard à la qualité des routines qu'il a pu donner dans d'autres challenges et aux efforts qu'il fait pour participer à un forum francophone, le pense qu'on devrait faire un effort pour essayer de répondre à ce challenge, d'autant que l'exercice est intéressant et très "ouvert" (beaucoup d'algorithmes et de solutions possible).

 

Je n'ai pas beaucoup de temps ces jours ci, mais voici quand même une troisième méthode.

les listes de paires sont "décompilées" (transformées en une liste unique) avant traitement puis "recompilées" ensuite.

 

;; "décompile" une liste de paires pointées en un liste unique
;; (pairs2lst '((1 . 5) (8 . 10) (16 . 16))) -> (1 2 3 4 5 8 9 10 16)
(defun pairs2lst (l / a b r)
 (foreach p l
   (setq a (car p)
  b (cdr p)
   )
   (while (      (setq r (cons a r)
    a (1+ a)
     )
   )
 )
 (reverse r)
)

;; "compile" une liste en liste de paires pointées
;;; (lst2pairs '(1 2 3 4 5 8 9 10 16)) -> ((1 . 5) (8 . 10) (16 . 16))
(defun lst2pairs (l / a b r)
 (setq	a (car l)
b a
l (cdr l)
 )
 (while a
   (if	(= (car l) (1+ b))
     (setq b (car l))
     (setq r (cons (cons a b) r)
    a (car l)
    b a
     )
   )
   (setq l (cdr l))
 )
 (reverse r)
)

(defun union (l1 l2)
 (lst2pairs
   (vl-sort
     (append
(pairs2lst l1)
(pairs2lst l2)
     )
     '    )
 )
)

(defun intersection (l1 l2)
 (lst2pairs
   (vl-remove-if-not
     (function
(lambda	(x)
  (member x (pairs2lst l2))
)
     )
     (pairs2lst l1)
   )
 )
)

(defun subtraction (l1 l2)
 (lst2pairs
   (vl-remove-if
     (function
(lambda	(x)
  (member x (pairs2lst l2))
)
     )
     (pairs2lst l1)
   )
 )
) 

[Patrick_35]

Salut

 

Eut égard à la qualité des routines qu'il a pu donner dans d'autres challenges et aux efforts qu'il fait pour participer à un forum francophone, le pense qu'on devrait faire un effort pour essayer de répondre à ce challenge, d'autant que l'exercice est intéressant et très "ouvert" (beaucoup d'algorithmes et de solutions possible).

Je ne peux qu'être d'accord. C'est le temps qui me manque pour l'instant, mais promis, je donnerai une réponse.

 

@+

[ElpanovEvgeniy]

Je ne demande pas les ripostes.

Cette compétition, j'ai commencé cinq ans en arrière.

Un rivalisait.

À la base de ce code, j'ai créé quelques plus grands projets, de qui je suis fier!

 

[Bruno_T]

bonjour,

voici une solution pour l'union (trés peu testée)

 

(defun union_bto (lsta lstb / lst lstU a b)
 (setq lst (vl-sort (append lsta lstb) '(lambda (a b) (< (car a) (car b)))))               
 (setq  a (car lst))
 (foreach b (cdr lst)
   (if (>= (cdr a) (1- (car b)))
     (setq a (cons (min (car a) (car b))(max (cdr a) (cdr b))))
     (setq lstU (cons a lstU) a b)
   )
 )
 (reverse (cons a lstU))
)

 

example
(setq
 lst1'((1 . 5) (8 . 10) (20 . 20) (35 . 60) (62 . 62))
 lst2 '((2 . 2) (4 . 6) (9 . 30) (32 . 33))
)
(union_bto lst1 lst2)

return : ((1 . 6) (8 . 30) (32 . 33) (35 . 60) (62 . 62)) 

 

L’intérêt du stockage sous la forme '((1 . 6) (8 . 30)....) est d'avoir des listes compactes. Gilles, dans ta dernière solution, tu proposes de les "décompacter" pour les "recompacter", cela se fait en mémoire mais ça me semble antagoniste avec le fait d'avoir des listes compactes qui offrent aussi l'avantage de s'affranchir de devoir balayer tous les nombres. On utilise ces astuces de stockage pour de très grandes listes, comme tu le proposes dans tes premières solutions, je pense qu’on a tout intérêt à éviter de les balayer totalement.

 

Bruno Toniutti

 

[Edité le 20/9/2008 par Bruno_T]

[(gile)]

Salut Bruno,

 

L’intérêt du stockage sous la forme '((1 . 6) (8 . 30)....) est d'avoir des listes compactes. Gilles, dans ta dernière solution, tu proposes de les "décompacter" pour les "recompacter", cela se fait en mémoire mais ça me semble antagoniste avec le fait d'avoir des listes compactes qui offrent aussi l'avantage de s'affranchir de devoir balayer tous les nombres. On utilise ces astuces de stockage pour de très grandes listes, comme tu le propose dans tes premières solutions, je pense qu’on a tout intérêt à éviter de les balayer totalement.

 

Complètement d'accord avec toi, je donnais ces routines à titre d'exemple pour montrer la multiplicité des possibilité de solutions et parce que cette méthode est peut-être plus facile à appréhender. Son exécution est bien sûr plus lente que le traitement direct des listes de paires.

 

La solution que tu donnes ressemble un peu à la seconde que je donnais (append des deux listes). Je crains que cette méthode ne soit applicable que pour la fonction union.

D'autre part, elle ne retourne pas le résultat escompté pour :

(Union '((2 . 4) (6 . 8)) '((2 . 5))) qui devrait retourner '((2 . 8)) -dernier exemple donné par Evgeniy.

 

 

J'ai essayé de corriger/améliorer ma première solution et de l'extrapoler aux autres fonctions (intersection et subtraction).

 

(defun union_gile (l1 l2)
 (cond
   ((null l1) l2)
   ((null l2) l1)
   ((     (cons (car l1) (union_gile (cdr l1) l2))
   )
   ((     (cons (car l2) (union_gile l1 (cdr l2)))
   )
   (T
    (if (       (union_gile
 (cons (cons (min (caar l1) (caar l2)) (cdar l1)) (cdr l1))
 (cdr l2)
      )
      (union_gile
 (cdr l1)
 (cons (cons (min (caar l1) (caar l2)) (cdar l2)) (cdr l2))
      )
    )
   )
 )
)

(defun intersection_gile (l1 l2)
 (cond
   ((or (null l1) (null l2)) nil)
   ((     (intersection_gile (cdr l1) l2)
   )
   ((     (intersection_gile l1 (cdr l2))
   )
   ((     (cons (cons (max (caar l1) (caar l2)) (cdar l1))
   (intersection_gile (cdr l1) l2)
    )
   )
   ((     (cons (cons (max (caar l1) (caar l2)) (cdar l2))
   (intersection_gile l1 (cdr l2))
    )
   )
   (T
    (cons (cons (max (caar l1) (caar l2)) (cdar l1))
   (intersection_gile (cdr l1) (cdr l2))
    )
   )
 )
)

(defun subtraction_gile (l1 l2)
 (cond
   ((null l1) nil)
   ((null l2) l1)
   ((     (subtraction_gile l1 (cdr l2))
   )
   ((     (cons (car l1) (subtraction_gile (cdr l1) l2))
   )
   ((      (if (	(subtraction_gile (cdr l1) l2)
(subtraction_gile (cons (cons (1+ (cdar l2)) (cdar l1)) (cdr l1)) l2)
     )
   )
   ((      (cons (cons (caar l1) (1- (caar l2)))
    (subtraction_gile (cdr l1) l2)
     )
   )
   (T
    (cons (cons (caar l1) (1- (caar l2)))
   (subtraction_gile
     (cons (cons (1+ (cdar l2)) (cdar l1)) (cdr l1))
     l2
   )
    )
   )
 )
) 

[Bruno_T]

oui Gilles, effectivement je n'ai pas suffisamment fait de tests (et seulement 1 de plus depuis...), j'ai corrigé mon code initial, merci pour l'info. Effectivement le principe est similaire à ta seconde solution.

 

Bien que je trouve ces challenges intéressants, je ne sais pas si j'aurai le temps de m'attaquer aux autres :(

 

Bruno Toniutti

 

 

[Edité le 20/9/2008 par Bruno_T]