Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Patricia Ferreira <pferreira@example.com>
Newsgroups: pt.comp.programacao
Subject: Re: Lisp, um mapa de trajeto
Date: Mon, 05 Feb 2024 18:50:37 -0300
Organization: A noiseless patient Spider
Lines: 97
Message-ID: <87zfwelgwi.fsf@example.com>
References: <ungjlm$1gn5r$1@dont-email.me> <87a5p83yxq.fsf@brilhante.top> <87mst8rpjj.fsf@example.com> <87o7dn3636.fsf@brilhante.top> <874jff1dbm.fsf@yaxenu.org> <87a5p638mt.fsf@brilhante.top> <87bk9mzg3b.fsf@example.com> <87bk9l9mki.fsf@brilhante.top> <87r0ign4zd.fsf@yaxenu.org> <87h6jcj6uh.fsf@brilhante.top> <87wms6khgu.fsf@yaxenu.org> <87cytyjzhb.fsf@brilhante.top> <87v87qike6.fsf@example.com> <874jfajvgc.fsf@brilhante.top> <878r4mfjiw.fsf@example.com> <87v87oi0pw.fsf@brilhante.top> <87wms4f4m3.fsf@example.com> <87il3kyn4g.fsf@brilhante.top> <8734u97q1z.fsf@brilhante.top> <8734u9buk3.fsf@example.com> <875xz26hny.fsf@brilhante.top>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: dont-email.me; posting-host="60f3787e6dabe4a9c31eadec529b81ee"; logging-data="510968"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+qfq+w6kQiV4pH1Tspx88ZKZbS9uO3mQ8="
Cancel-Lock: sha1:XZHreZomsgCuMwWGerJKGYaVDRk= sha1:qZp6vOFb6LLivlK5UW/3SUc1MeM=
Xref: csiph.com pt.comp.programacao:221

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.