Backtracking infinite loop
Posted
by
Greenhorn
on Stack Overflow
See other posts from Stack Overflow
or by Greenhorn
Published on 2011-01-13T04:47:36Z
Indexed on
2011/01/13
4:54 UTC
Read the original article
Hit count: 251
This is Exercise 28.1.2 from HtDP. I've successfully implemented the neighbors
function and all test cases pass.
(define Graph (list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
(define (first-line n alist)
(cond
[(symbol=? (first alist) n) alist]
[else empty]))
;; returns empty if node is not in graph
(define (neighbors n g)
(cond
[(empty? g) empty]
[(cons? (first g))
(cond
[(symbol=? (first (first g)) n) (first-line n (first g))]
[else (neighbors n (rest g))])]))
; test cases
(equal? (neighbors 'A Graph) (list 'A (list 'B 'E)))
(equal? (neighbors 'B Graph) (list 'B (list 'E 'F)))
(equal? (neighbors 'C Graph) (list 'C (list 'D)))
(equal? (neighbors 'D Graph) (list 'D empty))
(equal? (neighbors 'E Graph) (list 'E (list 'C 'F)))
(equal? (neighbors 'F Graph) (list 'F (list 'D 'G)))
(equal? (neighbors 'G Graph) (list 'G empty))
(equal? (neighbors 'H Graph) empty)
The problem comes when I copy-paste the code from Figure 77
of the text. It is supposed to determine whether a destination node is reachable from an origin node. However it appears that the code goes into an infinite loop except for the most trivial case where the origin and destination nodes are the same.
;; find-route : node node graph -> (listof node) or false
;; to create a path from origination to destination in G
;; if there is no path, the function produces false
(define (find-route origination destination G)
(cond
[(symbol=? origination destination) (list destination)]
[else (local ((define possible-route
(find-route/list (neighbors origination G) destination G)))
(cond
[(boolean? possible-route) false]
[else (cons origination possible-route)]))]))
;; find-route/list : (listof node) node graph -> (listof node) or false
;; to create a path from some node on lo-Os to D
;; if there is no path, the function produces false
(define (find-route/list lo-Os D G)
(cond
[(empty? lo-Os) false]
[else (local ((define possible-route (find-route (first lo-Os) D G)))
(cond
[(boolean? possible-route) (find-route/list (rest lo-Os) D G)]
[else possible-route]))]))
Does the problem lie in my code? Thank you.
© Stack Overflow or respective owner