Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pt.comp.programacao > #114 > unrolled thread
| Started by | dirk@orka.cs.kuleuven.be. (Dirk Craeynest) |
|---|---|
| First post | 2024-01-08 10:44 +0000 |
| Last post | 2024-02-04 11:42 +0000 |
| Articles | 3 on this page of 83 — 5 participants |
Back to article view | Back to pt.comp.programacao
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
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-03 18:09 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87ttmp5sit.fsf@brilhante.top> |
| In reply to | #216 |
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: >>> >>>> 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)))))) > > Por que push aqui quando você já está usando cons quando quer construir > uma lista? Será que você tá usando exclude-lists de forma global? Não > faz sentido, já que você passando ela como argumento pra /paths/. > >> A função a ser executada é a função ``paths''. Consegues verificar-me se >> funciona corretamente? > > Aparentemente sim, mas você parece entrar num laço infinito com > > (paths 'a 'a sample-graph). > > Como funciona? Não é óbvia a estratégia. > > Parece que find-path2 seria a solução pra um qualquer caminho---seria a > solução anterior. Mas, não---você teve que alterá-la substancialmente > pra poder obter a nova. Tenho dificuldade de entendê-la. Não só > estamos preocupados com exclude-lists, mas também em excluir vizinhos. > > Essa exclude-lists talvez fosse melhor chamada de exclude-paths. > > A solução que julguei ``mais ou menos óbvia'' foi a que sugeri em > mensagem anterior hoje---computa-se um caminho a partir do primeiro > vizinho; remove-se o vizinho do grafo e computa-se de novo. Repita até > não haver mais caminho---sinal de que não há mais vizinhos que nos leve > ao destino. exclude-paths parece-me um bom nome. O push é porque a variável exclude-lists é do tipo lista de listas, e faço um push de um path, para assim saber que esse path já foi obtido (e tentar outro). Ainda preciso de arranjar a minha solução, mas é uma maneira mais eficiente que calcular todos os paths com remoção de vizinhos. Não é óbvio de entender a minha solução; por isso também irei tentar fazer com que seja mais fácil a sua leitura.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-02-03 20:48 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <871q9thzxp.fsf@example.com> |
| In reply to | #217 |
Daniel Cerqueira <dan.list@brilhante.top> writes: > 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: >>>> >>>>> 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)))))) >> >> Por que push aqui quando você já está usando cons quando quer construir >> uma lista? Será que você tá usando exclude-lists de forma global? Não >> faz sentido, já que você passando ela como argumento pra /paths/. >> >>> A função a ser executada é a função ``paths''. Consegues verificar-me se >>> funciona corretamente? >> >> Aparentemente sim, mas você parece entrar num laço infinito com >> >> (paths 'a 'a sample-graph). >> >> Como funciona? Não é óbvia a estratégia. >> >> Parece que find-path2 seria a solução pra um qualquer caminho---seria a >> solução anterior. Mas, não---você teve que alterá-la substancialmente >> pra poder obter a nova. Tenho dificuldade de entendê-la. Não só >> estamos preocupados com exclude-lists, mas também em excluir vizinhos. >> >> Essa exclude-lists talvez fosse melhor chamada de exclude-paths. >> >> A solução que julguei ``mais ou menos óbvia'' foi a que sugeri em >> mensagem anterior hoje---computa-se um caminho a partir do primeiro >> vizinho; remove-se o vizinho do grafo e computa-se de novo. Repita até >> não haver mais caminho---sinal de que não há mais vizinhos que nos leve >> ao destino. > > exclude-paths parece-me um bom nome. > > O push é porque a variável exclude-lists é do tipo lista de listas, e > faço um push de um path, para assim saber que esse path já foi obtido (e > tentar outro). > > Ainda preciso de arranjar a minha solução, mas é uma maneira mais > eficiente que calcular todos os paths com remoção de vizinhos. > > Não é óbvio de entender a minha solução; por isso também irei tentar > fazer com que seja mais fácil a sua leitura. Combinado. Então vou esperar. E a minha ``mais ou menos óbvia''? Deu pra entender? Eu teria pensado que haveria uma solução mais fácil de fazer, dado que conseguimos escrever find-path. Mas você viu o trabalho que nós dois tivemos em ambos os casos? Por isso eu disse---parece moleza. Só faltou dizer---mas não é (pra mim, pelo menos). Mas não queria te influenciar. O fato é---o problema não é trivial (pra mim). O que está me faltando?
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-04 11:42 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87il345ubu.fsf@brilhante.top> |
| In reply to | #218 |
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: >>> >>>> 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)))))) >>> >>> Por que push aqui quando você já está usando cons quando quer construir >>> uma lista? Será que você tá usando exclude-lists de forma global? Não >>> faz sentido, já que você passando ela como argumento pra /paths/. >>> >>>> A função a ser executada é a função ``paths''. Consegues verificar-me se >>>> funciona corretamente? >>> >>> Aparentemente sim, mas você parece entrar num laço infinito com >>> >>> (paths 'a 'a sample-graph). >>> >>> Como funciona? Não é óbvia a estratégia. >>> >>> Parece que find-path2 seria a solução pra um qualquer caminho---seria a >>> solução anterior. Mas, não---você teve que alterá-la substancialmente >>> pra poder obter a nova. Tenho dificuldade de entendê-la. Não só >>> estamos preocupados com exclude-lists, mas também em excluir vizinhos. >>> >>> Essa exclude-lists talvez fosse melhor chamada de exclude-paths. >>> >>> A solução que julguei ``mais ou menos óbvia'' foi a que sugeri em >>> mensagem anterior hoje---computa-se um caminho a partir do primeiro >>> vizinho; remove-se o vizinho do grafo e computa-se de novo. Repita até >>> não haver mais caminho---sinal de que não há mais vizinhos que nos leve >>> ao destino. >> >> exclude-paths parece-me um bom nome. >> >> O push é porque a variável exclude-lists é do tipo lista de listas, e >> faço um push de um path, para assim saber que esse path já foi obtido (e >> tentar outro). >> >> Ainda preciso de arranjar a minha solução, mas é uma maneira mais >> eficiente que calcular todos os paths com remoção de vizinhos. >> >> Não é óbvio de entender a minha solução; por isso também irei tentar >> fazer com que seja mais fácil a sua leitura. > > Combinado. Então vou esperar. E a minha ``mais ou menos óbvia''? Deu > pra entender? Eu teria pensado que haveria uma solução mais fácil de > fazer, dado que conseguimos escrever find-path. Mas você viu o trabalho > que nós dois tivemos em ambos os casos? Por isso eu disse---parece > moleza. Só faltou dizer---mas não é (pra mim, pelo menos). Mas não > queria te influenciar. O fato é---o problema não é trivial (pra mim). > O que está me faltando? Sim, não é moleza. Ainda não vi a fundo a tua solução, porque ainda estou a tentar fazer a minha solução. O que está faltando? Não sei. Mas só há duas soluções: ou se vai removendo elementos do sample-graph (a tua solução), ou se cria e usa uma lista de paths a serem evitados quando se está a calcular um caminho, para se poder encontrar outros paths diferentes (a minha solução). Eu não queria fazer isto, mas vou ter de fazê-lo. Tenho de alterar o código para que não consuma o sample-graph, evitando usar o cdr e passando a usar o nth+um-integer-de-posição. Assim dá para percorrer o grafo, mantendo este sempre no estado inicial, para assim poder comparar o caminho que se está a obter, com os caminhos já obtidos da lista de exclusão. É necessário o nth porque tenho de comparar o caminho desde o ínicio, não um cdr (ou cddr, cdddr, etc.) desse caminho. Isto é necessário na minha solução.
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | pt.comp.programacao
csiph-web