Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pt.comp.programacao > #173

Re: Lisp, um mapa de trajeto

From Patricia Ferreira <pferreira@example.com>
Newsgroups pt.comp.programacao
Subject Re: Lisp, um mapa de trajeto
Date 2024-01-18 08:29 -0300
Organization A noiseless patient Spider
Message-ID <87wms6khgu.fsf@yaxenu.org> (permalink)
References (16 earlier) <87a5p638mt.fsf@brilhante.top> <87bk9mzg3b.fsf@example.com> <87bk9l9mki.fsf@brilhante.top> <87r0ign4zd.fsf@yaxenu.org> <87h6jcj6uh.fsf@brilhante.top>

Show all headers | View raw

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---

Back to pt.comp.programacao | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-08 10:44 +0000
  Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-08 13:05 -0300
    Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-09 09:53 +0000
      Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-09 09:31 -0300
        Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-10 13:18 +0000
          Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Ninguém <usenet@rasparta.org> - 2024-01-10 15:18 +0000
            fiat lux! (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:57 -0300
              Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:42 +0000
                Re: fiat lux! Ninguém <usenet@rasparta.org> - 2024-01-11 22:21 +0000
                Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 14:23 +0000
                Re: fiat lux! "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-16 14:05 +0000
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-16 11:45 -0300
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:24 -0300
                Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:02 -0300
          Lisp (was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-10 16:00 +0000
            Re: Lisp Patricia Ferreira <pferreira@example.com> - 2024-01-10 17:00 -0300
              Re: Lisp Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:30 +0000
          Lisp, um mapa de trajeto (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:37 -0300
            Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 17:04 +0000
              Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:37 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 18:22 +0000
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-12 18:51 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:29 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:27 -0300
                E-mail (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 10:34 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:04 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 17:02 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:07 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:39 -0300
                Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:51 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:27 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:21 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:24 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:23 +0000
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:33 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 17:01 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:26 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:50 -0300
                Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 11:04 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 09:46 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:32 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 16:59 -0300
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:11 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:01 -0300
                Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 14:18 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:33 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:02 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:51 -0300
                Encriptação (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:44 +0000
                Re: Encriptação Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:30 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:25 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:25 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:43 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 14:00 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-16 18:10 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-16 22:06 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 14:10 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 18:03 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:47 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 15:51 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 17:57 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:09 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 19:24 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 17:56 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-19 10:39 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-19 08:38 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-20 13:38 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-20 11:42 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-23 17:29 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 11:19 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 09:29 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 13:14 +0000
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-05 15:43 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-05 18:50 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 10:55 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-06 18:13 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 11:11 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 14:52 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 18:09 +0000
                Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 20:48 -0300
                Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-04 11:42 +0000

csiph-web