Re: [racket-users] Looking for suggestion on accumulating the paths of Graph from HtDP
On Feb 12, 2016, at 1:00 PM, liweijian wrote: > I just added missing parts as follows, it passed all the tests I wrote. Great. Use the force Liweijian -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Looking for suggestion on accumulating the paths of Graph from HtDP
在 2016年2月1日星期一 UTC+8上午1:41:51，Matthias Felleisen写道： > I think you may wish to read How to Design Programs. Here are something that > are missing: > > — data definitions (what’s a graph? what’s a path) > — signatures > — examples > — tests > > Once you supply those missing pieces, you will make much more progress. If > you post those, we can also help you make real progress, not just complete a > problem from HtDP/2e. > > > > On Jan 30, 2016, at 11:29 PM, liweijian wrote: > > > > HtDP taught us how to check if there exists path(s) from one node to > > another. > > > > I tried to implement accumulating all the paths between two nodes as: > > > > ```racket > > (define (find-paths origin dest G path) > > (cond > >[(equal? origin dest) (reverse (cons dest path))] > >[else > > (find-paths/all (neighbors origin G) dest G (cons origin path))])) > > > > (define (find-paths/all lons dest G path) > > (cond > >[(empty? lons) '(#f)] > >[else > > (map (λ (n) (find-paths n dest G path)) lons)])) > > ``` > > > > However, when I tested it by > > > > ```racket > > (define sample-graph > > '((A (B E)) > >(B (E > > > > (define (neighbors origination G) > > (cadr (assoc origination G))) > > > > (find-paths 'A 'E sample-graph '()) > > ``` > > > > The answer is: '(((A B E)) (A E)) > > > > In order to get the right answer, I have to write another `flatten` > > function as: > > > > ```racket > > (define (flatten-path lop) > > (cond > >[(empty? lop) empty] > >[(not (list? (caar lop))) (cons (first lop) (flatten-path (rest lop)))] > >[else > > (append (flatten-path (first lop)) (flatten-path (rest lop)))])) > > > > (filter (λ (path) (not (boolean? (car path (flatten-path (find-paths 'A > > 'E sample-graph '( > > ``` > > > > And now it works. > > > > I was wondering if maybe I could improve it? > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Racket Users" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to > > For more options, visit https://groups.google.com/d/optout. Great thanks to Matthias and your great book:) I found another solution without the nested list problem : http://stackoverflow.com/questions/26836750/finding-all-paths-in-graph-from-one-node-to-another-node/26847591#26847591 I just added missing parts as follows, it passed all the tests I wrote. ``` #lang racket (require rackunit) ; Node Node Graph Path -> [Nested List-of Path] ; Find all the paths from orig to dest in G with prefix path (define (find-paths-aux orig dest G path) (cond [(equal? orig dest) (reverse (cons dest path))] [else (find-paths/all (neighbors orig G) dest G (cons orig path))])) ; [List-of Node] Node Graph Path -> [List-of Path] ; Collects all the paths from lons to dest in G with prefix path (define (find-paths/all lons dest G path) (cond [(empty? lons) '(#f)] [else (map (λ (n) (find-paths-aux n dest G path)) lons)])) ; A Graph is a [Assoc-List-of [List-of Node]] ; Node is a Symbol ; Path is [List-of Node] (define sample-graph '((A (B E)) (B (E ; Node Graph -> [List-of Node] ; Find all the neighbors of origination in G (define (neighbors origination G) (cadr (assoc origination G))) ; Node Node Graph -> [List-of Path] ; Finds all paths from orig to dest in G (define (find-paths orig dest G) (filter (λ (path) (not (boolean? (car path (flatten-path (find-paths-aux orig dest G '( ) ; Nested List-of Node -> [List-of Path] ; This is the function I want to avoid (define (flatten-path lop) (cond [(empty? lop) empty] [(not (list? (caar lop))) (cons (first lop) (flatten-path (rest lop)))] [else (append (flatten-path (first lop)) (flatten-path (rest lop)))])) (define H0 '((A (B (define paths/H0 (find-paths 'A 'B H0)) (check-equal? (length paths/H0) 1) (check-not-false (member '(A B) paths/H0)) (define H1 '((A (B E)) (B (E (define paths/H1 (find-paths 'A 'E H1)) (check-equal? (length paths/H1) 2) (check-not-false (member '(A E) paths/H1)) (check-not-false (member '(A B E) paths/H1)) (define H2 '((A (B C E)) (B (E)) (C (F)) (E ()) (F ( (define paths/H2 (find-paths 'A 'E H2)) (check-equal? (length paths/H2) 2) (check-not-false (member '(A E) paths/H2)) (check-not-false (member '(A B E) paths/H2)) (define H3 '((A (B E)) (B (E F)) (C (D)) (D ()) (E (C F)) (F (D G)) (G ( (define paths/H3 (find-paths 'A 'D H3)) (check-equal? (length paths/H3) 5) (check-not-false (member '(A E C D) paths/H3)) (check-not-false (member '(A B E C D) paths/H3)) (check-not-false (member '(A E F D) paths/H3)) (check-not-false (member '(A B F D) paths/H3)) (check-not-false (member '(A B E F D) paths/H3)) ``` -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from
Re: [racket-users] Looking for suggestion on accumulating the paths of Graph from HtDP
I think you may wish to read How to Design Programs. Here are something that are missing: — data definitions (what’s a graph? what’s a path) — signatures — examples — tests Once you supply those missing pieces, you will make much more progress. If you post those, we can also help you make real progress, not just complete a problem from HtDP/2e. > On Jan 30, 2016, at 11:29 PM, liweijian wrote: > > HtDP taught us how to check if there exists path(s) from one node to another. > > I tried to implement accumulating all the paths between two nodes as: > > ```racket > (define (find-paths origin dest G path) > (cond >[(equal? origin dest) (reverse (cons dest path))] >[else > (find-paths/all (neighbors origin G) dest G (cons origin path))])) > > (define (find-paths/all lons dest G path) > (cond >[(empty? lons) '(#f)] >[else > (map (λ (n) (find-paths n dest G path)) lons)])) > ``` > > However, when I tested it by > > ```racket > (define sample-graph > '((A (B E)) >(B (E > > (define (neighbors origination G) > (cadr (assoc origination G))) > > (find-paths 'A 'E sample-graph '()) > ``` > > The answer is: '(((A B E)) (A E)) > > In order to get the right answer, I have to write another `flatten` function > as: > > ```racket > (define (flatten-path lop) > (cond >[(empty? lop) empty] >[(not (list? (caar lop))) (cons (first lop) (flatten-path (rest lop)))] >[else > (append (flatten-path (first lop)) (flatten-path (rest lop)))])) > > (filter (λ (path) (not (boolean? (car path (flatten-path (find-paths 'A > 'E sample-graph '( > ``` > > And now it works. > > I was wondering if maybe I could improve it? > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Looking for suggestion on accumulating the paths of Graph from HtDP
HtDP taught us how to check if there exists path(s) from one node to another. I tried to implement accumulating all the paths between two nodes as: ```racket (define (find-paths origin dest G path) (cond [(equal? origin dest) (reverse (cons dest path))] [else (find-paths/all (neighbors origin G) dest G (cons origin path))])) (define (find-paths/all lons dest G path) (cond [(empty? lons) '(#f)] [else (map (λ (n) (find-paths n dest G path)) lons)])) ``` However, when I tested it by ```racket (define sample-graph '((A (B E)) (B (E (define (neighbors origination G) (cadr (assoc origination G))) (find-paths 'A 'E sample-graph '()) ``` The answer is: '(((A B E)) (A E)) In order to get the right answer, I have to write another `flatten` function as: ```racket (define (flatten-path lop) (cond [(empty? lop) empty] [(not (list? (caar lop))) (cons (first lop) (flatten-path (rest lop)))] [else (append (flatten-path (first lop)) (flatten-path (rest lop)))])) (filter (λ (path) (not (boolean? (car path (flatten-path (find-paths 'A 'E sample-graph '( ``` And now it works. I was wondering if maybe I could improve it? -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
