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 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> References: <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 Daniel Cerqueira 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)))