;;; These functions were created in CS 32, in class, on Monday, Oct. 15, 2007
;;; A few comments have been added since, to help the reader.


;;; First we review how list-ref and random can be combined to construct
;;; a function that returns a random item of fruit. Evaluate
;;; (random-fruit) to see what happens.
(define (random-fruit)
  (list-ref *fruit* (random (length *fruit*))))
  
;;; The above requires *fruit* to be a list. Here it is:
(define *fruit* '(oranges grapes pineapple passion-fruit avocado))

;;; We now define the maze that appears in problem 5 on midterm #1.
;;; Brianna corrected an error in the list of neighbors of node h.
;;; Note that p is the goal node in this maze.
(define *maze* '((a (b)) 
                 (b (a c f m)) 
                 (c (b d e))
                 (d (c)) 
                 (e (c f j)) 
                 (f (b e g h j k l m))
                 (g (f))
                 (h (f))
                 (i (j))
                 (j (i e f p n))
                 (k (f))
                 (l (f))
                 (m (b f n))
                 (n (o j m))
                 (o (n))
                 (p (j))))

;;; The get-neighbors function returns a list of nodes that are the
;;; neighboring vertices of node v in maze m. Evaluate
;;; (get-neighbors 'f *maze*) to see what happens.
(define (get-neighbors v m)
  (cond ((null? m) '())
        ((eq? v (caar m)) (cadar m))
        (else (get-neighbors v (cdr m)))))

;;; To implement the random search algorithm below, we need an auxilliary
;;; function that returns a random neighbor of node v in maze m.
;;; Evaluate (get-random-neighbor 'f *maze*) to see what happens.
(define (get-random-neighbor v m)
  (cond ((null? m) '())
        ((eq? v (caar m)) 
         (list-ref (cadar m) (random (length (cadar m)))))
         (else (get-random-neighbor v (cdr m)))))

;;; The following defines a predicate function that returns #t if v represents
;;; the goal node.
(define (goal? v)
  (eq? v 'p))

;;; The following implements a random walk in a maze. start denotes the start node,
;;; goal, the goal node, and graph, a nested list that defines the topology of the
;;; maze. Evaluate (randomsearch 'a 'p *maze*) and see what happens. Have fun!
(define (randomsearch start goal graph)
  (display start)
  (cond ((eq? start goal) (display " ") "Eureka!!!")
        (else (randomsearch 
               (get-random-neighbor start graph) goal graph))))