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 | 20 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 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-17 15:51 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87h6jcj6uh.fsf@brilhante.top> |
| In reply to | #169 |
Patricia Ferreira <pferreira@example.com> writes:
> Daniel Cerqueira <dan.list@brilhante.top> writes:
>
>> Mesmo assim. Não estou a ver maneira de isso ser possível, dado eu só
>> poder fazer uma função, com o cond, car, cdr, eq, atom, cons, etc..
>
> Você pode (e deve) fazer várias funções.
>
>> Não consigo fazer tal função.
>
> Não é muito fácil. Isso é ensinado no HtDP. O propósito dos exercícios
> é diagnosticar isso. Devemos ler o livro ou não? Parece que devemos.
>
> Você pode olhar a solução deles, capítulo 29, parte V. Mas não creio
> que você aprecie muito a apresentação deles se você não estiver bem
> treinado no método de raciocínio que eles usam.
>
> Uma sugestão é a gente voltar um pouco e trabalhar num exercício mais
> fácil. Por exemplo, capítulo 19, parte IV, exercício 313 --- tendo lido
> o capítulo 19 todo, o que não demora. Está bem relacionado com
> /find-path/, mas é mais fácil. O próprio avisa isso no capítulo 29.
>
> Ou então insistimos em /find-path/, o que não recomendo. Diga-me o que
> pensas.
Demorei à volta de 40 minutos.
Aqui está a minha resposta, assim, sem querer pensar muito mais no
assunto: (Não consultei esse livro online.)
(defun get-start-list (start graph)
(cond
((null graph) nil)
((eq (caar graph) start) (car graph))
(t (get-start-list start (cdr graph)))))
(defun get-path-list (start end graph)
(cond
((null start) (cons nil nil))
((eq start end) (cons end nil))
((eq (car (get-start-list start graph)) start)
(cons
start
(get-path-list (caadr (get-start-list start graph)) end graph)))))
(defun find-path (start end graph)
(cond
((null (car (last (get-path-list start end graph)))) nil)
(t (get-path-list start end graph))))
Dá-me o teu parecer ;-)
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-01-18 08:29 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87wms6khgu.fsf@yaxenu.org> |
| In reply to | #171 |
Desculpe a demora --- o assunto aqui exige tempo e energia. Daniel Cerqueira <dan.list@brilhante.top> writes: > Patricia Ferreira <pferreira@example.com> writes: > >> Daniel Cerqueira <dan.list@brilhante.top> writes: >> >>> Mesmo assim. Não estou a ver maneira de isso ser possível, dado eu só >>> poder fazer uma função, com o cond, car, cdr, eq, atom, cons, etc.. >> >> Você pode (e deve) fazer várias funções. >> >>> Não consigo fazer tal função. >> >> Não é muito fácil. Isso é ensinado no HtDP. O propósito dos exercícios >> é diagnosticar isso. Devemos ler o livro ou não? Parece que devemos. >> >> Você pode olhar a solução deles, capítulo 29, parte V. Mas não creio >> que você aprecie muito a apresentação deles se você não estiver bem >> treinado no método de raciocínio que eles usam. >> >> Uma sugestão é a gente voltar um pouco e trabalhar num exercício mais >> fácil. Por exemplo, capítulo 19, parte IV, exercício 313 --- tendo lido >> o capítulo 19 todo, o que não demora. Está bem relacionado com >> /find-path/, mas é mais fácil. O próprio avisa isso no capítulo 29. >> >> Ou então insistimos em /find-path/, o que não recomendo. Diga-me o que >> pensas. > > Demorei à volta de 40 minutos. O tempo sugere que esse é um problema que você não resolveu ainda. Você está tentando expressar essa estratégia pela primeira vez. > Aqui está a minha resposta, assim, sem querer pensar muito mais no > assunto: (Não consultei esse livro online.) > > (defun get-start-list (start graph) > (cond > ((null graph) nil) > ((eq (caar graph) start) (car graph)) > (t (get-start-list start (cdr graph))))) Uma sugestão é chamar essa de get-vertex or alguma coisa assim. Maravilha que você a implementou por conta própria --- você deve saber que /assoc/ em Common Lisp faria o mesmo por você aí. > (defun get-path-list (start end graph) > (cond > ((null start) (cons nil nil)) > ((eq start end) (cons end nil)) > ((eq (car (get-start-list start graph)) start) > (cons > start > (get-path-list (caadr (get-start-list start graph)) end graph))))) Maravilha de procedimento. Esse aí já é quase uma solução. Ele só não é uma solução porque ele desiste no primeiro caminho que tenta. > (defun find-path (start end graph) > (cond > ((null (car (last (get-path-list start end graph)))) nil) > (t (get-path-list start end graph)))) > > Dá-me o teu parecer ;-) Você deve saber que sua solução não computa a resposta desejada. A impressão que dá é que você olhou só os casos mais simples que colocamos como teste. Por exemplo, você computa a resposta certa em --8<---------------cut here---------------start------------->8--- CL-USER> (find-path 'C 'D sample-graph) ((C D)) --8<---------------cut here---------------end--------------->8--- Computa a resposta certa em --8<---------------cut here---------------start------------->8--- CL-USER> (find-path 'C 'A sample-graph) NIL --8<---------------cut here---------------end--------------->8--- Mas dá uma olhada em --8<---------------cut here---------------start------------->8--- CL-USER> (find-path 'A 'E sample-graph) ((A E)) --8<---------------cut here---------------end--------------->8--- Fica faltando aí (A B E). Seu advogado objeta e diz que a gente permitiu qualquer caminho pro destino e não todos --- mas seu procedimento responde uma lista, o que sugere que ele está em busca de todos, o que fica claro em --8<---------------cut here---------------start------------->8--- CL-USER> (find-path 'A 'F sample-graph) ((A (B F)) (A (E F))) --8<---------------cut here---------------end--------------->8--- sendo que a forma da resposta mudou. O resultado que esperávamos era ((A B F) (A B E F) (A E F)) embora não exatamente nessa ordem --- qualquer ordem serve. Então afirmo que não temos uma solução aí. --8<---------------cut here---------------start------------->8--- De qualquer forma, dou-lhe os parabéns pela tentativa e um diagnóstico final. O diagnóstico é de que o HtDP --- pelo menos em suas partes posteriores do livro --- contém técnicas que não dominamos nem de perto. Agora, um problema que vejo aqui é que possivelmente se você resolver ler só as partes posteriores do livro, talvez você não compreenda o processo de escrita que eles recomendam lá. É o aviso. O livro é um jeito de pensar que exige um hábito de pensar. --8<---------------cut here---------------end--------------->8--- (*) Seu find-path Okay, uma pergunta é --- onde está a falha no find-path? Ou, melhor, por que seu procedimento não funciona? Ou melhor, qual é a essência da sua estratégia? Sua estratégia parece bem clara na sua escrita --- e parabéns pela clareza de escrita (com o devido agradecimento à cultura Lisp, o que você parece ter). Você afirma que se eu descer num certo caminho e terminar com NIL, então é porque aquele caminho é sem saída --- desista dele. De outra forma, você responde o caminho. Isso sugere que get-path-list é de fato o seu descobridor de caminhos e find-path é seu detector de caminhos válidos. Mas essas observações são contraditórias. Se get-path-list é o seu descobridor de caminhos, por que ela tenta coletar mais de um caminho? Quando leio find-path, minha conclusão é de que sua solução reportaria um único caminho válido, o que não é o que acontece em --8<---------------cut here---------------start------------->8--- CL-USER> (find-path 'A 'F sample-graph) ((A (B F)) (A (E F))) --8<---------------cut here---------------end--------------->8---
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-18 17:57 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87cytyjzhb.fsf@brilhante.top> |
| In reply to | #173 |
Patricia Ferreira <pferreira@example.com> writes: > Desculpe a demora --- o assunto aqui exige tempo e energia. Está tranquila. Até que não achei te tivesses demorado muito tempo. > Você deve saber que sua solução não computa a resposta desejada. A > impressão que dá é que você olhou só os casos mais simples que colocamos > como teste. Por exemplo, você computa a resposta certa em > > --8<---------------cut here---------------start------------->8--- > CL-USER> (find-path 'C 'D sample-graph) > ((C D)) > --8<---------------cut here---------------end--------------->8--- A mim, não me dá assim: --8<---------------cut here---------------start------------->8--- (find-path 'c 'd sample-graph) (C D) --8<---------------cut here---------------end--------------->8--- > Computa a resposta certa em > > --8<---------------cut here---------------start------------->8--- > CL-USER> (find-path 'C 'A sample-graph) > NIL > --8<---------------cut here---------------end--------------->8--- --8<---------------cut here---------------start------------->8--- (find-path 'c 'a sample-graph) NIL --8<---------------cut here---------------end--------------->8--- > Mas dá uma olhada em > > --8<---------------cut here---------------start------------->8--- > CL-USER> (find-path 'A 'E sample-graph) > ((A E)) > --8<---------------cut here---------------end--------------->8--- --8<---------------cut here---------------start------------->8--- (find-path 'a 'e sample-graph) (A B E) --8<---------------cut here---------------end--------------->8--- > Fica faltando aí (A B E). Seu advogado objeta e diz que a gente > permitiu qualquer caminho pro destino e não todos --- mas seu > procedimento responde uma lista, o que sugere que ele está em busca de > todos, o que fica claro em > > --8<---------------cut here---------------start------------->8--- > CL-USER> (find-path 'A 'F sample-graph) > ((A (B F)) (A (E F))) > --8<---------------cut here---------------end--------------->8--- --8<---------------cut here---------------start------------->8--- (find-path 'a 'f sample-graph) NIL --8<---------------cut here---------------end--------------->8--- > sendo que a forma da resposta mudou. O resultado que esperávamos era > > ((A B F) (A B E F) (A E F)) > > embora não exatamente nessa ordem --- qualquer ordem serve. Então > afirmo que não temos uma solução aí. > > --8<---------------cut here---------------start------------->8--- > De qualquer forma, dou-lhe os parabéns pela tentativa e um diagnóstico > final. O diagnóstico é de que o HtDP --- pelo menos em suas partes > posteriores do livro --- contém técnicas que não dominamos nem de perto. > Agora, um problema que vejo aqui é que possivelmente se você resolver > ler só as partes posteriores do livro, talvez você não compreenda o > processo de escrita que eles recomendam lá. É o aviso. O livro é um > jeito de pensar que exige um hábito de pensar. > --8<---------------cut here---------------end--------------->8--- > > > (*) Seu find-path > > Okay, uma pergunta é --- onde está a falha no find-path? Ou, melhor, > por que seu procedimento não funciona? Ou melhor, qual é a essência da > sua estratégia? > > Sua estratégia parece bem clara na sua escrita --- e parabéns pela > clareza de escrita (com o devido agradecimento à cultura Lisp, o que > você parece ter). Você afirma que se eu descer num certo caminho e > terminar com NIL, então é porque aquele caminho é sem saída --- desista > dele. De outra forma, você responde o caminho. Isso sugere que > get-path-list é de fato o seu descobridor de caminhos e find-path é seu > detector de caminhos válidos. Mas essas observações são contraditórias. > Se get-path-list é o seu descobridor de caminhos, por que ela tenta > coletar mais de um caminho? Quando leio find-path, minha conclusão é de > que sua solução reportaria um único caminho válido, o que não é o que > acontece em > > --8<---------------cut here---------------start------------->8--- > CL-USER> (find-path 'A 'F sample-graph) > ((A (B F)) (A (E F))) > --8<---------------cut here---------------end--------------->8--- De certeza que estavas a usar o mey código que te enviei? Esses resultados parecer ser de outro código. De qualquer das maneiras, o este meu código não está a funcionar direito, em alguns casos.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-01-18 15:09 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87v87qike6.fsf@example.com> |
| In reply to | #174 |
Daniel Cerqueira <dan.list@brilhante.top> writes: [...] > De certeza que estavas a usar o mey código que te enviei? Esses > resultados parecer ser de outro código. Perdão. Modifiquei seu código e não consegui retorná-lo ao estado original (como pensei). > De qualquer das maneiras, o este meu código não está a funcionar > direito, em alguns casos. Pois é. Sua estratégia é realmente expressa por get-path-list. O procedimento find-path é apenas um procedimento de apresentação --- se get-path-list não encontrar o caminho, diga nil. O que há de errado com sua estratégia? Façamos a pergunta --- por que get-path-list não encontra o caminho de F a G? São vizinhos; deveria ser trivial. Mas G não é o /primeiro/ vizinho de F. O primeiro vizinho de F é D. Como não há caminho entre D e G, seu procedimento pensa que não há caminho. Em outras palavras, seu procedimento só faz uma tentativa de várias possíveis --- se não houver caminho na primeira, seu procedimento acha que não há caminho qualquer.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-18 19:24 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <874jfajvgc.fsf@brilhante.top> |
| In reply to | #176 |
Patricia Ferreira <pferreira@example.com> writes: > Daniel Cerqueira <dan.list@brilhante.top> writes: > >> De qualquer das maneiras, o este meu código não está a funcionar >> direito, em alguns casos. > > Pois é. Sua estratégia é realmente expressa por get-path-list. O > procedimento find-path é apenas um procedimento de apresentação --- se > get-path-list não encontrar o caminho, diga nil. > > O que há de errado com sua estratégia? Façamos a pergunta --- por que > get-path-list não encontra o caminho de F a G? São vizinhos; deveria > ser trivial. Mas G não é o /primeiro/ vizinho de F. O primeiro vizinho > de F é D. Como não há caminho entre D e G, seu procedimento pensa que > não há caminho. Em outras palavras, seu procedimento só faz uma > tentativa de várias possíveis --- se não houver caminho na primeira, seu > procedimento acha que não há caminho qualquer. Pois... eu sei que só está a resolver o primeiro caminho. Quando tento fazer com que resolva todos os caminhos, o meu código fica muito complicado; e ainda não consegui fazê-lo. Estava apenas a tentar usar cons e isso estava-me a dificultar um pouco. Acho que a essência deste exercício está-me a passar ao lado. Como resolverias este exercício? :-)
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-01-18 17:56 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <878r4mfjiw.fsf@example.com> |
| In reply to | #178 |
Daniel Cerqueira <dan.list@brilhante.top> writes:
> Patricia Ferreira <pferreira@example.com> writes:
>
>> Daniel Cerqueira <dan.list@brilhante.top> writes:
>>
>>> De qualquer das maneiras, o este meu código não está a funcionar
>>> direito, em alguns casos.
>>
>> Pois é. Sua estratégia é realmente expressa por get-path-list. O
>> procedimento find-path é apenas um procedimento de apresentação --- se
>> get-path-list não encontrar o caminho, diga nil.
>>
>> O que há de errado com sua estratégia? Façamos a pergunta --- por que
>> get-path-list não encontra o caminho de F a G? São vizinhos; deveria
>> ser trivial. Mas G não é o /primeiro/ vizinho de F. O primeiro vizinho
>> de F é D. Como não há caminho entre D e G, seu procedimento pensa que
>> não há caminho. Em outras palavras, seu procedimento só faz uma
>> tentativa de várias possíveis --- se não houver caminho na primeira, seu
>> procedimento acha que não há caminho qualquer.
>
> Pois... eu sei que só está a resolver o primeiro caminho. Quando tento
> fazer com que resolva todos os caminhos, o meu código fica muito
> complicado; e ainda não consegui fazê-lo. Estava apenas a tentar usar
> cons e isso estava-me a dificultar um pouco.
>
> Acho que a essência deste exercício está-me a passar ao lado.
>
> Como resolverias este exercício? :-)
Eis uma tentativa pela receita HtDP. Um Vértice é um Símbolo. Um
Vizinhos é uma lista de Símbolos. Um Grafo é um de
- NIL
- (cons Vértice Vizinhos)
Por exemplo,
NIL ou (list B E))
são Vizinhos. Já A, B, C, ... são Vértices. E, assim,
((A (B E))
(B (E F)))
é um grafo. Precisamos de um procedimento neighbors que extrai os
Vizinhos de um vértice. Como é trivial, usemos /assoc/:
(defun neighbors (v g) (assoc v g))
Como já temos Grafo e Vértice, já podemos escrever a assinatura de
find-path. Ela consome dois vértices e um grafo e produz uma lista de
Vértice --- que é o caminho em si.
Vértice Vértice Grafo --> List-of Vértices
Usando sample-graph, temos os exemplos:
(find-path 'C 'D sample-graph) --> (C D)
(find-path 'E 'D sample-graph) --> (E C D) ou (E F D)
(find-path 'C 'G sample-graph) --> sem-caminho
O caso E--D já apresenta essa ambiguidade: tem dois caminhos possíveis.
O caso C--G não tem nenhum. É preciso decidir o que fazer em cada caso.
Dizer NIL quando sem-caminho vai ajudar a escrever um código mais curto
em Common Lisp. Quanto à ambiguidade, escolhamos por ora o primeiro
caminho que for encontrado.
O procedimento find-path tem que retornar uma List-of Vértices, então
não estamos incorretos se retornarmos NIL num esboço
(defun find-path (src dst g)
NIL)
A receita pra esse tipo de problema é considerar algumas possibilidades:
o caso base, o repartir do problema em um subproblema e o passo de
combinação da subsolução pra obter o problema original.
Quando dois Vértices são vizinhos, o caminho é trivial: os dois vértices
numa lista. Mas dá pra tornar esse problema ainda mais trivial que é
quando os dois Vértices são o mesmo Vértice, que é o que você fez em
get-path-list. Usemos isso também: a resposta aí é (cond end nil).
Se os argumentos são diferentes, precisamos considerar cada vizinho.
Considerar cada vizinho é um problema novo, mas /cada um/ desses
problemas é da mesma forma que o problema original. Se os vizinhos de
/src/ são v1, v2, então os subproblemas são
(find-path v1 end g)
(find-path v2 end g)
Agora, invocar a resolução desses subproblemas é um problema /novo/
porque envolve uma List-of Vértices. Esse /tipo/ diferente nos leva a
escrever um novo procedimento --- porque as assinaturas não casam. Que
tipo de resposta esse novo procedimento produz? Uma List-of Vértices,
logo NIL é um esboço de resposta.
;; Vizinhos Vértice Grafo --> List-of Vértice
;; interpretação: o primeiro caminho encontrado entre um Vértice de
;; origem (em Vizinhos) até o Vértice de destino no Grafo.
(defun find-path/list (ns dst g)
NIL)
Agora já podemos escrever find-path, assumindo que find-path/list está
pronta. Se houver um caminho de algum vizinho até DST, então a resposta
é uma lista não-vazia. Se não houver, é NIL. Assim, se find-path/list
retorna NIL, então não há caminho algum. Se ela retorna List-of
Vértice, então a resposta do problema original é
(cons SRC <RETORNO DE FIND-PATH/LIST).
(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)))))
Recapitule. Se SRC e DST são idênticos, caso base. Se forem
diferentes, então precisamos ver se existe caminho entre os vizinhos de
SRC até DST. Isso quem descobre é find-path/list. Se find-path/list
retornar uma coisa que não é NIL, então a solução do problema original é
simplesmente SRC na cabeça de SUBSOLUTION. Se não houver, então
respondemos NIL também.
Pra isso funcionar, só precisamos de find-path/list. É hora de recordar
o projeto que fizemos pra find-path/list, o que repetimos aqui pra não
ter que recuperar texto acima já passado.
;; Vizinhos Vértice Grafo --> List-of Vértice
;; interpretação: o primeiro caminho encontrado entre um Vértice de
;; origem (em Vizinhos) até o Vértice de destino no Grafo.
(defun find-path/list (ns dst g)
NIL)
Agora que find-path está escrita, fica muito mais fácil pensar em
find-path/list porque o que find-path/list faz é usar find-path até
encontrar um caminho, ou seja, find-path/list é trivial: basta percorrer
a lista de Vizinhos um a um. O caso base de find-path/list é quando não
há mais Vizinhos a considerar.
(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.
(*) Uma expressão mais típica
Usamos /if/ no código acima pra casar com a nossa redação em português,
mas não é a forma idiomática de escrever. Eis uma reescrita.
(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))))))
É a solução.
(*) Epílogo
Esse é o processo ensinado pelo HtDP. Mas não é fácil usar isso. Não
diria que realmente compreenda esse processo. Os autores anunciam
também --- especialmente nesses casos de recursão ``generativa'', que é
como eles chama esse tipo, o código muitas vezes exige um certo insight.
Em retrospectiva, posso fazer as seguintes observações. Observe que pra
escrever find-path/list, precisamos de find-path. Pra escrever
find-path, precisamos de find-path/list. Em outras palavras, temos uma
recursão mútua aí. Isso é comum de ocorrer em árvores. Por exemplo,
como se faz pra descer um sistema de arquivos? Dessa forma. Esse grafo
não é nada senão uma árvore. Ele não possui ciclos. Então é preciso
trabalhar de forma mais sistemática --- observando essas coisas. Como
diz Frederick P. Brooks, é preciso prestar atenção à estrutura de dados
primeiro. Os algoritmos em si serão óbvios depois. Essa noção está
explicitamente explorada pelo HtDP.
``Representation Is the Essence of Programming. Much more often,
strategic breakthrough will come from redoing the representation of
the data or tables. This is where the heart of a program lies. Show
me your flowcharts and conceal your tables, and I shall continue to be
mystified. Show me your tables, and I won’t usually need your
flowcharts; they’ll be obvious.'' -- ``The Mythical Man-Month'',
expanded anniversary edition (2nd edition), 1995, Addison-Wesley, ISBN
0-201-83595-9. Página 102.
(*) Novo problema
Encontremos todos os caminhos. Parece moleza. Experimenta.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-19 10:39 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87zfx1ip40.fsf@brilhante.top> |
| In reply to | #179 |
Patricia Ferreira <pferreira@example.com> writes: > Eis uma tentativa pela receita HtDP. Um Vértice é um Símbolo. Um > Vizinhos é uma lista de Símbolos. Um Grafo é um de > > - NIL > - (cons Vértice Vizinhos) > > Por exemplo, > > NIL ou (list B E)) > > são Vizinhos. Já A, B, C, ... são Vértices. E, assim, > > ((A (B E)) > (B (E F))) > > é um grafo. Precisamos de um procedimento neighbors que extrai os > Vizinhos de um vértice. Como é trivial, usemos /assoc/: > > (defun neighbors (v g) (assoc v g)) Esta função "neighbors" está a confundir-me, porque, da maneira com que está escrita, ela está a devolver a aresta mais o vértice (sendo v um vértice e g um grafo). Verifica esta função e vê se está correta. Será que deveria ficar assim: (defun neighbors (v g) (cadr (assoc v g))) ?
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-01-19 08:38 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87zfx1eeo6.fsf@example.com> |
| In reply to | #180 |
Daniel Cerqueira <dan.list@brilhante.top> writes: > Patricia Ferreira <pferreira@example.com> writes: > >> Eis uma tentativa pela receita HtDP. Um Vértice é um Símbolo. Um >> Vizinhos é uma lista de Símbolos. Um Grafo é um de >> >> - NIL >> - (cons Vértice Vizinhos) >> >> Por exemplo, >> >> NIL ou (list B E)) >> >> são Vizinhos. Já A, B, C, ... são Vértices. E, assim, >> >> ((A (B E)) >> (B (E F))) >> >> é um grafo. Precisamos de um procedimento neighbors que extrai os >> Vizinhos de um vértice. Como é trivial, usemos /assoc/: >> >> (defun neighbors (v g) (assoc v g)) > > Esta função "neighbors" está a confundir-me, porque, da maneira com que > está escrita, ela está a devolver a aresta mais o vértice (sendo v um > vértice e g um grafo). > > Verifica esta função e vê se está correta. > > Será que deveria ficar assim: > > (defun neighbors (v g) (cadr (assoc v g))) > > ? Perdão! Percebi isso depois de escrever o procedimento; atualizei o código e não postei pra você. Na verdade escrevi (defun vertex (v graph) (assoc v graph)) (defun neighbors (v graph) (cadr (vertex v graph))) Sua leitura está correta.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-20 13:38 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87v87oi0pw.fsf@brilhante.top> |
| In reply to | #179 |
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.... Isto deve ser o que Stallman quer dizer com "playful cleverness" (que é o significado real da palavra "hacker"). Ainda estou a analisar cuidadosamente os algoritmos. Por serem regenerativos (acho que é assim o nome), parecem que tem por base ar puro, isto é, nada em concreto. E funcionam :-) É uma solução maravilhosa........ > (*) Epílogo > > Esse é o processo ensinado pelo HtDP. Mas não é fácil usar isso. Não > diria que realmente compreenda esse processo. Os autores anunciam > também --- especialmente nesses casos de recursão ``generativa'', que é > como eles chama esse tipo, o código muitas vezes exige um certo insight. > > Em retrospectiva, posso fazer as seguintes observações. Observe que pra > escrever find-path/list, precisamos de find-path. Pra escrever > find-path, precisamos de find-path/list. Em outras palavras, temos uma > recursão mútua aí. Isso é comum de ocorrer em árvores. Por exemplo, > como se faz pra descer um sistema de arquivos? Dessa forma. Esse grafo > não é nada senão uma árvore. Ele não possui ciclos. Então é preciso > trabalhar de forma mais sistemática --- observando essas coisas. Como > diz Frederick P. Brooks, é preciso prestar atenção à estrutura de dados > primeiro. Os algoritmos em si serão óbvios depois. Essa noção está > explicitamente explorada pelo HtDP. > > ``Representation Is the Essence of Programming. Much more often, > strategic breakthrough will come from redoing the representation of > the data or tables. This is where the heart of a program lies. Show > me your flowcharts and conceal your tables, and I shall continue to be > mystified. Show me your tables, and I won’t usually need your > flowcharts; they’ll be obvious.'' -- ``The Mythical Man-Month'', > expanded anniversary edition (2nd edition), 1995, Addison-Wesley, ISBN > 0-201-83595-9. Página 102. Ótima citação. Parece que o HtDP tem muito a oferecer. E esse do "The Mythical Man-Month" já ouvi muitas vezes esse nome, mas não sei bem de que assunto esse livro trata. > (*) 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 ;-)
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-01-20 11:42 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87wms4f4m3.fsf@example.com> |
| In reply to | #182 |
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))))))
> Isto deve ser o que Stallman quer dizer com "playful cleverness" (que é
> o significado real da palavra "hacker").
>
> Ainda estou a analisar cuidadosamente os algoritmos. Por serem
> regenerativos (acho que é assim o nome), parecem que tem por base ar
> puro, isto é, nada em concreto. E funcionam :-) É uma solução
> maravilhosa........
Como traduzimos isso? Não apoio ``regenerativo'', não, porque essa
palavra sugere uma coisa que foi destruída e então recuperou-se. Já
``generativa'' sugere a geração de alguma coisa, que é o que ocorre em
qualquer recursão. Entretanto, a recursão que é obviamente menor que a
anterior é chamada de recursão estrutural ou recursão natural. Essa é a
impressão que tenho. Nunca achei muito fácil definir recursão natural,
estrutura e recursão generativa.
>> (*) Epílogo
>>
>> Esse é o processo ensinado pelo HtDP. Mas não é fácil usar isso. Não
>> diria que realmente compreenda esse processo. Os autores anunciam
>> também --- especialmente nesses casos de recursão ``generativa'', que é
>> como eles chama esse tipo, o código muitas vezes exige um certo insight.
>>
>> Em retrospectiva, posso fazer as seguintes observações. Observe que pra
>> escrever find-path/list, precisamos de find-path. Pra escrever
>> find-path, precisamos de find-path/list. Em outras palavras, temos uma
>> recursão mútua aí. Isso é comum de ocorrer em árvores. Por exemplo,
>> como se faz pra descer um sistema de arquivos? Dessa forma. Esse grafo
>> não é nada senão uma árvore. Ele não possui ciclos. Então é preciso
>> trabalhar de forma mais sistemática --- observando essas coisas. Como
>> diz Frederick P. Brooks, é preciso prestar atenção à estrutura de dados
>> primeiro. Os algoritmos em si serão óbvios depois. Essa noção está
>> explicitamente explorada pelo HtDP.
>>
>> ``Representation Is the Essence of Programming. Much more often,
>> strategic breakthrough will come from redoing the representation of
>> the data or tables. This is where the heart of a program lies. Show
>> me your flowcharts and conceal your tables, and I shall continue to be
>> mystified. Show me your tables, and I won’t usually need your
>> flowcharts; they’ll be obvious.'' -- ``The Mythical Man-Month'',
>> expanded anniversary edition (2nd edition), 1995, Addison-Wesley, ISBN
>> 0-201-83595-9. Página 102.
>
> Ótima citação. Parece que o HtDP tem muito a oferecer.
É. Não é um livro que deveríamos ignorar, já que não enxergamos essas
técnicas com naturalidade. Tem outras coisas que não devemos ignorar,
mas fica pra outro momento.
>> (*) 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.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-01-23 17:29 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87il3kyn4g.fsf@brilhante.top> |
| In reply to | #183 |
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?
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-03 11:19 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <8734u97q1z.fsf@brilhante.top> |
| In reply to | #186 |
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)))))) > > > A função a ser executada é a função ``paths''. Consegues verificar-me se > funciona corretamente? Patrícia, qual é a tua solução a este problema? Ainda falta-te dizer.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-02-03 09:29 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <8734u9buk3.fsf@example.com> |
| In reply to | #213 |
Daniel Cerqueira <dan.list@brilhante.top> writes:
[...]
>>>>> (*) 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?
>
> Patrícia, qual é a tua solução a este problema? Ainda falta-te dizer.
Opa! Parece que deixei passar seu artigo de 23 de janeiro---perdão. Só
com essa nova mensagem percebi. Ainda bem que postou. Deixe-me estudar
sua solução acima.
Sabe qual é a minha solução? A minha é---use find-path pra encontrar um
primeiro caminho de SRC a DST. Se houver caminho, é porque SRC tem
algum vizinho que de fato nos leva a DST. Remova esse vizinho gráfico e
tente de novo---repita até que não haja mais caminho. Estou vendo seu
exclude-lists acima---talvez você tenha feito o mesmo.
Pra remover um vizinho de SRC, eu uso neighbor-, que consome um grafo e
um vértice e produz um grafo sem o primeiro /vizinho/ de SRC. (Torço
pra que o código abaixo esteja completo).
A propósito, estávamos escrevendo Lisp ou Scheme? Parece que mudei pra
Scheme? Já nem lembro o que estávamos fazendo. :-)
(define (find-path src dst graph)
(cond
([symbol=? src dst] (list src))
[else (let ((candidate (find-path/list (neighbors src graph) dst graph)))
(and candidate
(cons src candidate)))]))
(define (find-path/list ns end graph)
(cond
[(null? ns) #f]
[else (or (find-path (car ns) end graph)
(find-path/list (cdr ns) end graph))]))
(define (find-all-paths src dst graph [acc '()])
(let ((path (find-path src dst graph)))
(if path
(find-all-paths src dst (neighbor- src graph) (cons path acc))
acc)))
(define (neighbor- s graph)
;; Symbol Graph --> Graph
;; interp. Removes a neighbor from Node represented by Symbol s
(let* ((ns (neighbors s graph)) ;; [n]eighbor[s]
(nn (list s (cdr ns)))) ;; [n]ew [n]ode
(cons nn (graph- s graph))))
(define (graph- s graph)
(filter (λ (n) (symbol=? (node-name n) s)) graph))
(define (node v graph) (assoc v graph))
(define (node-name v) (car v))
(define (neighbors v graph) (cdr (node v graph)))
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-03 13:14 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87y1c1665p.fsf@brilhante.top> |
| In reply to | #214 |
Patricia Ferreira <pferreira@example.com> writes: > Daniel Cerqueira <dan.list@brilhante.top> writes: > > [...] > >>>>>> (*) 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? >> >> Patrícia, qual é a tua solução a este problema? Ainda falta-te dizer. > > Opa! Parece que deixei passar seu artigo de 23 de janeiro---perdão. Só > com essa nova mensagem percebi. Ainda bem que postou. Deixe-me estudar > sua solução acima. > > Sabe qual é a minha solução? A minha é---use find-path pra encontrar um > primeiro caminho de SRC a DST. Se houver caminho, é porque SRC tem > algum vizinho que de fato nos leva a DST. Remova esse vizinho gráfico e > tente de novo---repita até que não haja mais caminho. Estou vendo seu > exclude-lists acima---talvez você tenha feito o mesmo. > > Pra remover um vizinho de SRC, eu uso neighbor-, que consome um grafo e > um vértice e produz um grafo sem o primeiro /vizinho/ de SRC. (Torço > pra que o código abaixo esteja completo). > > A propósito, estávamos escrevendo Lisp ou Scheme? Parece que mudei pra > Scheme? Já nem lembro o que estávamos fazendo. :-) > > (define (find-path src dst graph) > (cond > ([symbol=? src dst] (list src)) > [else (let ((candidate (find-path/list (neighbors src graph) dst graph))) > (and candidate > (cons src candidate)))])) > > (define (find-path/list ns end graph) > (cond > [(null? ns) #f] > [else (or (find-path (car ns) end graph) > (find-path/list (cdr ns) end graph))])) > > (define (find-all-paths src dst graph [acc '()]) > (let ((path (find-path src dst graph))) > (if path > (find-all-paths src dst (neighbor- src graph) (cons path acc)) > acc))) > > (define (neighbor- s graph) > ;; Symbol Graph --> Graph > ;; interp. Removes a neighbor from Node represented by Symbol s > (let* ((ns (neighbors s graph)) ;; [n]eighbor[s] > (nn (list s (cdr ns)))) ;; [n]ew [n]ode > (cons nn (graph- s graph)))) > > (define (graph- s graph) > (filter (λ (n) (symbol=? (node-name n) s)) graph)) > > (define (node v graph) (assoc v graph)) > (define (node-name v) (car v)) > (define (neighbors v graph) (cdr (node v graph))) Estamos a escrever em Common Lisp! :-) Mudaste para Scheme, acho eu.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-05 15:43 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <875xz26hny.fsf@brilhante.top> |
| In reply to | #214 |
Patricia Ferreira <pferreira@example.com> writes:
>
> [...]
>
>>>>>> (*) Novo problema
>>>>>>
>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta.
Descobri a solução. Em Common Lisp (não em Scheme) :-P
Vai aqui o código completo. As funções "no", "vizinhos", "caminho" e
"caminho/lista", são as que tinhamos descoberto anteriormente.
Esta solução (tal como a tua), vai removendo elementos de GRAPH para
encontrar caminhos alternativos. O truque desta solução é que ao
remover, remove de GRAPH um elemento igual ao penúltimo elemento de um
dado caminho LIST. Assim mantem-se o DST de um caminho em GRAPH.
Se, após a remoção, o caminho alternativo der NIL, não existe mais
caminhos possíveis no GRAPH, desde SRC até DST.
Este código está completo. Podes copiar, colar, avaliar/compilar, e
correr. A função que descobre todos os caminho é "caminhos".
(defparameter graph
'((A (B E))
(B (E F))
(C (D))
(D ())
(E (C F))
(F (D G))
(G ())))
(defun no (node graph)
"Retorna um nó NODE de um grafo GRAPH."
(assoc node graph))
(defun vizinhos (node graph)
"Retorna os vizinhos de NODE de um grafo GRAPH."
(cadr (no node graph)))
(defun caminho (src dst graph)
"Retorna um caminho desde SRC até DST de um GRAPH."
(cond
((eq src dst) (cons dst nil))
(t
(let ((caminho-de-lista-de-vizinhos (caminho/lista (vizinhos src graph) dst graph)))
(cond
((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil
(t (cons src caminho-de-lista-de-vizinhos)))))))
(defun caminho/lista (list dst graph)
"Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho."
(cond
((null list) nil) ; fim da list
(t
(let ((caminho-de-atomo (caminho (car list) dst graph)))
(cond
((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior)
(t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list
(defun remover-penultimo (list graph)
"Remove de GRAPH um nó igual ao penultimo átomo de LIST."
(remove-if #'(lambda (el) (eq (nth (- (length list) 2) list) (car el))) graph))
(defun cortar-grafo (graph previous-paths)
"Corta no grafo GRAPH o(s) nó(s) igual(ais) ao penultimo átomo de cada caminho de PREVIOUS-PATHS."
(cond
((null previous-paths) graph)
(t (cortar-grafo
(remover-penultimo (car previous-paths) graph)
(cdr previous-paths)))))
(defun caminhos-alternativos (src dst graph previous-paths)
"Retorna um caminho desde SRC até DST de um GRAPH, que seja diferente dos caminhos de PREVIOUS-PATHS."
(let ((novo-caminho (caminho src dst (cortar-grafo graph previous-paths))))
(cond
((null novo-caminho) previous-paths)
(t (caminhos-alternativos src dst graph (push novo-caminho previous-paths))))))
(defun caminhos (src dst graph)
"Retorna todos os caminhos desde SRC até DST de um GRAPH. Retorna NIL caso não haja caminho."
(let ((um-caminho (caminho src dst graph)))
(cond
((null um-caminho) nil)
((eq src dst) (list (list src)))
(t (caminhos-alternativos src dst graph (list um-caminho))))))
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-02-05 18:50 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87zfwelgwi.fsf@example.com> |
| In reply to | #220 |
Daniel Cerqueira <dan.list@brilhante.top> writes: > Patricia Ferreira <pferreira@example.com> writes: > >> >> [...] >> >>>>>>> (*) Novo problema >>>>>>> >>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta. > > Descobri a solução. Em Common Lisp (não em Scheme) :-P > > Vai aqui o código completo. As funções "no", "vizinhos", "caminho" e > "caminho/lista", são as que tinhamos descoberto anteriormente. > > Esta solução (tal como a tua), vai removendo elementos de GRAPH para > encontrar caminhos alternativos. O truque desta solução é que ao > remover, remove de GRAPH um elemento igual ao penúltimo elemento de um > dado caminho LIST. Assim mantem-se o DST de um caminho em GRAPH. > > Se, após a remoção, o caminho alternativo der NIL, não existe mais > caminhos possíveis no GRAPH, desde SRC até DST. > > Este código está completo. Podes copiar, colar, avaliar/compilar, e > correr. A função que descobre todos os caminho é "caminhos". > > > (defparameter graph > '((A (B E)) > (B (E F)) > (C (D)) > (D ()) > (E (C F)) > (F (D G)) > (G ()))) > > (defun no (node graph) > "Retorna um nó NODE de um grafo GRAPH." > (assoc node graph)) > > (defun vizinhos (node graph) > "Retorna os vizinhos de NODE de um grafo GRAPH." > (cadr (no node graph))) > > (defun caminho (src dst graph) > "Retorna um caminho desde SRC até DST de um GRAPH." > (cond > ((eq src dst) (cons dst nil)) > (t > (let ((caminho-de-lista-de-vizinhos (caminho/lista (vizinhos src graph) dst graph))) > (cond > ((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil > (t (cons src caminho-de-lista-de-vizinhos))))))) > > (defun caminho/lista (list dst graph) > "Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho." > (cond > ((null list) nil) ; fim da list > (t > (let ((caminho-de-atomo (caminho (car list) dst graph))) > (cond > ((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior) > (t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list > > (defun remover-penultimo (list graph) > "Remove de GRAPH um nó igual ao penultimo átomo de LIST." > (remove-if #'(lambda (el) (eq (nth (- (length list) 2) list) (car el))) graph)) > > (defun cortar-grafo (graph previous-paths) > "Corta no grafo GRAPH o(s) nó(s) igual(ais) ao penultimo átomo de cada caminho de PREVIOUS-PATHS." > (cond > ((null previous-paths) graph) > (t (cortar-grafo > (remover-penultimo (car previous-paths) graph) > (cdr previous-paths))))) > > (defun caminhos-alternativos (src dst graph previous-paths) > "Retorna um caminho desde SRC até DST de um GRAPH, que seja diferente dos caminhos de PREVIOUS-PATHS." > (let ((novo-caminho (caminho src dst (cortar-grafo graph previous-paths)))) > (cond > ((null novo-caminho) previous-paths) > (t (caminhos-alternativos src dst graph (push novo-caminho previous-paths)))))) Não compreendo a necessidade de /push/ aqui. > (defun caminhos (src dst graph) > "Retorna todos os caminhos desde SRC até DST de um GRAPH. Retorna NIL caso não haja caminho." > (let ((um-caminho (caminho src dst graph))) > (cond > ((null um-caminho) nil) > ((eq src dst) (list (list src))) > (t (caminhos-alternativos src dst graph (list um-caminho)))))) A expressão está bem melhor. É engraçado como código tem uma certa forma. Um especialista em xadrez olha pra um tabuleiro e rapidamente nota se alguma coisa não faz sentido.
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-06 10:55 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <871q9p6evs.fsf@brilhante.top> |
| In reply to | #221 |
Patricia Ferreira <pferreira@example.com> writes: > Daniel Cerqueira <dan.list@brilhante.top> writes: > >> Patricia Ferreira <pferreira@example.com> writes: >> >>> >>> [...] >>> >>>>>>>> (*) Novo problema >>>>>>>> >>>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta. >> >> Descobri a solução. Em Common Lisp (não em Scheme) :-P >> >> Vai aqui o código completo. As funções "no", "vizinhos", "caminho" e >> "caminho/lista", são as que tinhamos descoberto anteriormente. >> >> Esta solução (tal como a tua), vai removendo elementos de GRAPH para >> encontrar caminhos alternativos. O truque desta solução é que ao >> remover, remove de GRAPH um elemento igual ao penúltimo elemento de um >> dado caminho LIST. Assim mantem-se o DST de um caminho em GRAPH. >> >> Se, após a remoção, o caminho alternativo der NIL, não existe mais >> caminhos possíveis no GRAPH, desde SRC até DST. >> >> Este código está completo. Podes copiar, colar, avaliar/compilar, e >> correr. A função que descobre todos os caminho é "caminhos". >> >> >> (defparameter graph >> '((A (B E)) >> (B (E F)) >> (C (D)) >> (D ()) >> (E (C F)) >> (F (D G)) >> (G ()))) >> >> (defun no (node graph) >> "Retorna um nó NODE de um grafo GRAPH." >> (assoc node graph)) >> >> (defun vizinhos (node graph) >> "Retorna os vizinhos de NODE de um grafo GRAPH." >> (cadr (no node graph))) >> >> (defun caminho (src dst graph) >> "Retorna um caminho desde SRC até DST de um GRAPH." >> (cond >> ((eq src dst) (cons dst nil)) >> (t >> (let ((caminho-de-lista-de-vizinhos (caminho/lista (vizinhos src graph) dst graph))) >> (cond >> ((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil >> (t (cons src caminho-de-lista-de-vizinhos))))))) >> >> (defun caminho/lista (list dst graph) >> "Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho." >> (cond >> ((null list) nil) ; fim da list >> (t >> (let ((caminho-de-atomo (caminho (car list) dst graph))) >> (cond >> ((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior) >> (t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list >> >> (defun remover-penultimo (list graph) >> "Remove de GRAPH um nó igual ao penultimo átomo de LIST." >> (remove-if #'(lambda (el) (eq (nth (- (length list) 2) list) (car el))) graph)) >> >> (defun cortar-grafo (graph previous-paths) >> "Corta no grafo GRAPH o(s) nó(s) igual(ais) ao penultimo átomo de cada caminho de PREVIOUS-PATHS." >> (cond >> ((null previous-paths) graph) >> (t (cortar-grafo >> (remover-penultimo (car previous-paths) graph) >> (cdr previous-paths))))) >> >> (defun caminhos-alternativos (src dst graph previous-paths) >> "Retorna um caminho desde SRC até DST de um GRAPH, que seja diferente dos caminhos de PREVIOUS-PATHS." >> (let ((novo-caminho (caminho src dst (cortar-grafo graph previous-paths)))) >> (cond >> ((null novo-caminho) previous-paths) >> (t (caminhos-alternativos src dst graph (push novo-caminho previous-paths)))))) > > Não compreendo a necessidade de /push/ aqui. > Por o argumento de caminhos-alternativos ser uma lista de lista, o push é uma maneira de adicionar uma lista a esta lista de listas. >> (defun caminhos (src dst graph) >> "Retorna todos os caminhos desde SRC até DST de um GRAPH. Retorna NIL caso não haja caminho." >> (let ((um-caminho (caminho src dst graph))) >> (cond >> ((null um-caminho) nil) >> ((eq src dst) (list (list src))) >> (t (caminhos-alternativos src dst graph (list um-caminho)))))) > > A expressão está bem melhor. É engraçado como código tem uma certa > forma. Um especialista em xadrez olha pra um tabuleiro e rapidamente > nota se alguma coisa não faz sentido. Tenho más notícias.... esta solução continua a não retornar todos os caminhos. Por exemplo: (caminhos 'b 'd graph) retorna apenas 2 caminhos, quando deveria retornar 3 caminhos. Após ter enviado este artigo, comecei a trabalhar numa solução que solucionasse isto de maneira definitiva. Já tenho a solução, que vou postar num artigo próprio.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-02-06 18:13 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <8734u5l2j9.fsf@example.com> |
| In reply to | #223 |
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: >>> >>>> >>>> [...] >>>> >>>>>>>>> (*) Novo problema >>>>>>>>> >>>>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta. >>> >>> Descobri a solução. Em Common Lisp (não em Scheme) :-P >>> >>> Vai aqui o código completo. As funções "no", "vizinhos", "caminho" e >>> "caminho/lista", são as que tinhamos descoberto anteriormente. >>> >>> Esta solução (tal como a tua), vai removendo elementos de GRAPH para >>> encontrar caminhos alternativos. O truque desta solução é que ao >>> remover, remove de GRAPH um elemento igual ao penúltimo elemento de um >>> dado caminho LIST. Assim mantem-se o DST de um caminho em GRAPH. >>> >>> Se, após a remoção, o caminho alternativo der NIL, não existe mais >>> caminhos possíveis no GRAPH, desde SRC até DST. >>> >>> Este código está completo. Podes copiar, colar, avaliar/compilar, e >>> correr. A função que descobre todos os caminho é "caminhos". >>> >>> >>> (defparameter graph >>> '((A (B E)) >>> (B (E F)) >>> (C (D)) >>> (D ()) >>> (E (C F)) >>> (F (D G)) >>> (G ()))) >>> >>> (defun no (node graph) >>> "Retorna um nó NODE de um grafo GRAPH." >>> (assoc node graph)) >>> >>> (defun vizinhos (node graph) >>> "Retorna os vizinhos de NODE de um grafo GRAPH." >>> (cadr (no node graph))) >>> >>> (defun caminho (src dst graph) >>> "Retorna um caminho desde SRC até DST de um GRAPH." >>> (cond >>> ((eq src dst) (cons dst nil)) >>> (t >>> (let ((caminho-de-lista-de-vizinhos (caminho/lista (vizinhos src graph) dst graph))) >>> (cond >>> ((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil >>> (t (cons src caminho-de-lista-de-vizinhos))))))) >>> >>> (defun caminho/lista (list dst graph) >>> "Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho." >>> (cond >>> ((null list) nil) ; fim da list >>> (t >>> (let ((caminho-de-atomo (caminho (car list) dst graph))) >>> (cond >>> ((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior) >>> (t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list >>> >>> (defun remover-penultimo (list graph) >>> "Remove de GRAPH um nó igual ao penultimo átomo de LIST." >>> (remove-if #'(lambda (el) (eq (nth (- (length list) 2) list) (car el))) graph)) >>> >>> (defun cortar-grafo (graph previous-paths) >>> "Corta no grafo GRAPH o(s) nó(s) igual(ais) ao penultimo átomo de cada caminho de PREVIOUS-PATHS." >>> (cond >>> ((null previous-paths) graph) >>> (t (cortar-grafo >>> (remover-penultimo (car previous-paths) graph) >>> (cdr previous-paths))))) >>> >>> (defun caminhos-alternativos (src dst graph previous-paths) >>> "Retorna um caminho desde SRC até DST de um GRAPH, que seja diferente dos caminhos de PREVIOUS-PATHS." >>> (let ((novo-caminho (caminho src dst (cortar-grafo graph previous-paths)))) >>> (cond >>> ((null novo-caminho) previous-paths) >>> (t (caminhos-alternativos src dst graph (push novo-caminho previous-paths)))))) >> >> Não compreendo a necessidade de /push/ aqui. > > Por o argumento de caminhos-alternativos ser uma lista de lista, o push > é uma maneira de adicionar uma lista a esta lista de listas. Você não pode usar cons pra isso? >>> (defun caminhos (src dst graph) >>> "Retorna todos os caminhos desde SRC até DST de um GRAPH. Retorna NIL caso não haja caminho." >>> (let ((um-caminho (caminho src dst graph))) >>> (cond >>> ((null um-caminho) nil) >>> ((eq src dst) (list (list src))) >>> (t (caminhos-alternativos src dst graph (list um-caminho)))))) >> >> A expressão está bem melhor. É engraçado como código tem uma certa >> forma. Um especialista em xadrez olha pra um tabuleiro e rapidamente >> nota se alguma coisa não faz sentido. > > Tenho más notícias.... esta solução continua a não retornar todos os > caminhos. Por exemplo: (caminhos 'b 'd graph) retorna apenas 2 caminhos, > quando deveria retornar 3 caminhos. > > Após ter enviado este artigo, comecei a trabalhar numa solução que > solucionasse isto de maneira definitiva. Já tenho a solução, que vou > postar num artigo próprio. Okay!
[toc] | [prev] | [next] | [standalone]
| From | Daniel Cerqueira <dan.list@brilhante.top> |
|---|---|
| Date | 2024-02-06 11:11 +0000 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87wmrh4zlf.fsf@brilhante.top> |
| In reply to | #214 |
Patricia Ferreira <pferreira@example.com> writes:
[...]
>>>>>> (*) Novo problema
>>>>>>
>>>>>> Encontremos todos os caminhos. Parece moleza. Experimenta.
Aqui está a minha solução a este problema. Com uma nova abordagem.
Esta solução é mais intensa na memória, mas estou a falhar em encontrar
uma solução mais suave para a memória do computador.
Aqui as funções "no", "vizinhos", "caminho" e "caminho/lista" são as
funções que já descobrimos nos exercícios anteriores.
A técnica aqui reside em criar uma lista de grafos, em que tem todos os
grafos na qual falta apenas um nó dos nós iniciais. Esta é a parte
intensiva para a memória.
Depois calculo todos os caminhos usando este /multiverso de grafos/ e
vou armazenando os caminhos únicos numa váriavel (local). Para depois
retornar esta variável.
Aqui a função que retorna todos os caminhos é "caminhos".
Patrícia, se descobrires outra abordagem que retorne todos os caminhos,
quero ouvir sobre ela. Uma maneira simples de testar, se retorna todos
os caminhos, é calcular os caminhos desde B até D, tendo de retornar 3
caminhos ;-)
(defparameter graph
'((A (B E))
(B (E F))
(C (D))
(D ())
(E (C F))
(F (D G))
(G ())))
(defun no (node graph)
"Retorna um nó NODE de um grafo GRAPH."
(assoc node graph))
(defun vizinhos (node graph)
"Retorna os vizinhos de NODE de um grafo GRAPH."
(cadr (no node graph)))
(defun caminho (src dst graph)
"Retorna um caminho desde SRC até DST de um GRAPH."
(cond
((eq src dst) (cons dst nil))
(t
(let* ((lista-de-vizinhos (vizinhos src graph))
(caminho-de-lista-de-vizinhos (caminho/lista lista-de-vizinhos dst graph)))
(cond
((null caminho-de-lista-de-vizinhos) nil) ; se chegou a um beco sem saída, isto é, um vizinho nil, retorna nil
(t (cons src caminho-de-lista-de-vizinhos)))))))
(defun caminho/lista (list dst graph)
"Retorna um caminho desde uma lista LIST até DST de um GRAPH. Retorna NIL caso não haja qualquer caminho."
(cond
((null list) nil) ; fim da list
(t
(let ((caminho-de-atomo (caminho (car list) dst graph)))
(cond
((consp caminho-de-atomo) caminho-de-atomo) ; caminho de o primeiro vizinho (depende de função anterior)
(t (caminho/lista (cdr list) dst graph))))))) ; ver restante da list
(defun remover-no (number graph)
"Remove um nó de GRAPH por posição NUMBER (primeira posição é o zero)"
(remove-if #'(lambda (el) (eq el (nth number graph))) graph))
(defun grafo-multiverso (graph &optional number)
"Retorna uma lista com todas as variações de GRAPH em que falta, em cada grafo, um nó."
(cond
((null number) (cons graph (grafo-multiverso graph 0)))
((eq number (length graph)) nil)
(t (cons (remover-no number graph) (grafo-multiverso graph (1+ number))))))
(defun caminho-map (src dst graph-multiverse result)
"Retorna todos os caminhos (RESULT) únicos desde SRC até DST, da lista de grafos GRAPH-MULTIVERSE. Retorna RESULT caso não haja qualquer caminho."
(let ((caminho (caminho src dst (car graph-multiverse))))
(cond
((null graph-multiverse) result)
((or
(null caminho)
(consp (member caminho result :test #'equal)))
(caminho-map src dst (cdr graph-multiverse) result))
(t (caminho-map src dst (cdr graph-multiverse) (push caminho result))))))
(defun caminhos (src dst graph)
"Retorna todos os caminhos de GRAPH, desde SRC até DST. Retorna NIL se não há qualquer caminho."
(caminho-map src dst (grafo-multiverso graph) nil))
[toc] | [prev] | [next] | [standalone]
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Date | 2024-02-03 14:52 -0300 |
| Subject | Re: Lisp, um mapa de trajeto |
| Message-ID | <87y1c1qvu3.fsf@example.com> |
| In reply to | #186 |
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.
[toc] | [prev] | [next] | [standalone]
Page 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
Back to top | Article view | pt.comp.programacao
csiph-web