Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pt.comp.programacao > #186
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Newsgroups | pt.comp.programacao |
| Subject | Re: Lisp, um mapa de trajeto |
| Date | 2024-01-23 17:29 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87il3kyn4g.fsf@brilhante.top> (permalink) |
| References | (16 earlier) <87v87qike6.fsf@example.com> <874jfajvgc.fsf@brilhante.top> <878r4mfjiw.fsf@example.com> <87v87oi0pw.fsf@brilhante.top> <87wms4f4m3.fsf@example.com> |
Patricia Ferreira <pferreira@example.com> writes:
> Daniel Cerqueira <dan.list@brilhante.top> writes:
>
>> Patricia Ferreira <pferreira@example.com> writes:
>>
>>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>>
>>>> Como resolverias este exercício? :-)
>>>
>>> (defun find-path (src dst graph)
>>> (cond
>>> ((eq src dst) (cons src nil))
>>> (t
>>> (let ((subsolution (find-path/list (neighbors src graph) dst graph)))
>>> (if subsolution
>>> (cons src subsolution)
>>> nil)))))
>>>
>>> (defun find-path/list (ns end graph)
>>> (cond
>>> ((null ns) nil)
>>> (t (let ((subsolution (find-path (car ns) end graph)))
>>> (if subsolution
>>> subsolution
>>> (find-path/list (cdr ns) end graph))))))
>>>
>>> CL-USER> (find-path 'A 'G sample-graph)
>>> (A B E F G)
>>> CL-USER> (find-path 'C 'D sample-graph)
>>> (C D)
>>> CL-USER> (find-path 'C 'A sample-graph)
>>> NIL
>>>
>>> Solucionado.
>>
>> Estou (e passei estes últimos dias) a olhar espantado quanto ao
>> maravilhoso engenho deste algoritmo....
>
> Somos dois. Mas me parece mais adequado observá-lo nesta forma:
>
> (defun find-path/list (ns end graph)
> (cond
> ((null ns) nil)
> (t (or (find-path (car ns) end graph)
> (find-path/list (cdr ns) end graph)))))
>
> (defun find-path (src dst graph)
> (cond
> ((eq src dst) (cons src nil))
> (t (and (find-path/list (neighbors src graph) dst graph)
> (cons src (find-path/list (neighbors src graph) dst graph))))))
>
>>> (*) Novo problema
>>>
>>> Encontremos todos os caminhos. Parece moleza. Experimenta.
>>
>> Vou demorar algum tempo a resolver este último problema. Primeiro quero
>> entender melhor a solução que des-te.
>>
>> E vou resolver sim esse novo problema ;-)
>
> Tem uma solução que julgo mais ou menos óbvia, mas me pergunto se é uma
> solução natural aí no caso. Vou deixar você trabalhar por aí antes de
> apresentar. Torço pra que você encontre a solução que eu acho que
> deveria existir e não consigo encontrar.
Bem, acho que encontrei a solução adquada. Alguns dos meus algoritmos
fazem duas vezes a mesma operação, por isso só falta optimiza-los para
nestas vezes, guardar o valor numa variável.
Aqui vai a minha resposta:
(defun cdrs (lists)
(mapcar #'cdr lists))
(defun cars (lists)
(mapcar #'car lists))
(defun diff (path-a path-b)
(cond
((null (member (car path-a) path-b)) path-a)
(t (diff (cdr path-a) path-b))))
(defun neighbors-exclude (exclude-lists list)
(diff list (cars exclude-lists)))
(defun find-path2 (src dst exclude-lists graph)
(cond
((eq src dst) (cons dst nil))
((null
(find-path/list2
(neighbors-exclude (cdrs exclude-lists) (neighbors src graph))
dst (cdrs exclude-lists) graph))
nil)
(t (cons
src
(find-path/list2
(neighbors-exclude (cdrs exclude-lists) (neighbors src graph))
dst (cdrs exclude-lists) graph)))))
(defun find-path/list2 (ns end exclude-lists graph)
(cond
((null ns) nil)
((null (find-path2 (car ns) end exclude-lists graph))
(find-path/list2 (cdr ns) end exclude-lists graph))
(t (find-path2 (car ns) end exclude-lists graph))))
(defun paths (src dst graph &optional exclude-lists)
(cond
((null (find-path2 src dst exclude-lists graph)) nil)
(t (cons
(find-path2 src dst exclude-lists graph)
(paths src dst graph
(push (find-path2 src dst exclude-lists graph) exclude-lists))))))
A função a ser executada é a função ``paths''. Consegues verificar-me se
funciona corretamente?
Back to pt.comp.programacao | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-08 10:44 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-08 13:05 -0300
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-09 09:53 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-09 09:31 -0300
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-10 13:18 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Ninguém <usenet@rasparta.org> - 2024-01-10 15:18 +0000
fiat lux! (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:57 -0300
Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:42 +0000
Re: fiat lux! Ninguém <usenet@rasparta.org> - 2024-01-11 22:21 +0000
Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 14:23 +0000
Re: fiat lux! "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-16 14:05 +0000
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-16 11:45 -0300
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:24 -0300
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:02 -0300
Lisp (was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-10 16:00 +0000
Re: Lisp Patricia Ferreira <pferreira@example.com> - 2024-01-10 17:00 -0300
Re: Lisp Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:30 +0000
Lisp, um mapa de trajeto (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:37 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 17:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:37 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 18:22 +0000
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-12 18:51 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:29 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:27 -0300
E-mail (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 10:34 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 17:02 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:07 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:39 -0300
Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:51 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:27 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:21 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:24 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:23 +0000
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:33 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 17:01 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:26 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:50 -0300
Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 11:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 09:46 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:32 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 16:59 -0300
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:11 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:01 -0300
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 14:18 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:33 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:02 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:51 -0300
Encriptação (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:44 +0000
Re: Encriptação Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:30 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:25 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:25 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:43 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 14:00 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-16 18:10 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-16 22:06 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 14:10 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 18:03 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:47 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 15:51 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 17:57 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:09 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 19:24 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 17:56 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-19 10:39 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-19 08:38 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-20 13:38 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-20 11:42 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-23 17:29 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 11:19 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 09:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 13:14 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-05 15:43 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-05 18:50 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 10:55 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-06 18:13 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 11:11 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 14:52 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 18:09 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 20:48 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-04 11:42 +0000
csiph-web