Re: Lisp, um mapa de trajeto

Path	csiph.com!weretis.net!feeder8.news.weretis.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	Sat, 03 Feb 2024 09:29:00 -0300
Organization	A noiseless patient Spider
Lines	122
Message-ID	<8734u9buk3.fsf@example.com> (permalink)
References	<ungjlm$1gn5r$1@dont-email.me> <87edel4avz.fsf@brilhante.top> <874jfhvwb9.fsf@example.com> <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>
MIME-Version	1.0
Content-Type	text/plain; charset=utf-8
Content-Transfer-Encoding	8bit
Injection-Info	dont-email.me; posting-host="aad133e4c5be3d1a82e952397156fd9c"; logging-data="3286419"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+loUyenj4mxt66y8qCOiW3jDGYIdCbrts="
Cancel-Lock	sha1:vWNxg5Uc2NufuEdJID79CA3AC0I= sha1:46pa1LpIFVPbI557uzLOpT6Ce8o=
Xref	csiph.com pt.comp.programacao:214

Show key headers only | View raw

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

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