;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-advanced-reader.ss" "lang")((modname |29.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
(define G1
  '((A (B E))
    (B (E F))
    (C (D))
    (D ())
    (E (C F))
    (F (D G))
    (G ())))

(define G2 (vector '(1 4)
                   '(4 5)
                   '(3)
                   empty
                   '(2 5)
                   '(3 6)
                   empty))

(define (find-route1 ori dest G)
  (local ((define (find-route ori dest G)
            (cond
              [(symbol=? ori dest) (list ori)]
              [else (local ((define possible-route (find-route/list (neighbors ori G) dest G)))
                      (cond
                        [(boolean? possible-route) false]
                        [else (cons ori possible-route)]))]))
          (define (find-route/list lo-ori dest G)
            (cond
              [(empty? lo-ori) false]
              [else (local ((define possible-route (find-route (first lo-ori) dest G)))
                      (cond [(boolean? possible-route) (find-route/list (rest lo-ori) dest G)]
                            [else possible-route]))]))
          (define (assf op aloxy)
            (cond
              [(empty? aloxy) false]
              [(op (first (first aloxy))) (first aloxy)]
              [else (assf op (rest aloxy))]))
          (define (neighbors anode G)
            (first (rest (assf (lambda (x) (equal? anode x)) G)))))
    (find-route ori dest G)))

(define (find-route2 ori dest G)
  (local ((define (find-route ori dest G)
            (cond
              [(= ori dest) (list ori)]
              [else (local ((define possible-route (find-route/list (neighbors ori G) dest G)))
                      (cond [(boolean? possible-route) false]
                            [else (cons ori possible-route)]))]))
          (define (find-route/list lo-ori dest G)
            (cond
              [(empty? lo-ori) false]
              [else (local ((define possible-route (find-route (first lo-ori) dest G)))
                      (cond
                        [(boolean? possible-route) (find-route/list (rest lo-ori) dest G)]
                        [else possible-route]))]))
          (define (neighbors anode agraph)
            (vector-ref agraph anode)))
    (find-route ori dest G)))

(define n 100000)
(time (andmap (lambda (x) (equal? (find-route1 'A 'G G1)
                                  (list 'A 'B 'E 'F 'G))) (build-list n identity)))
(time (andmap (lambda (x) (equal? (find-route2 0 6 G2)
                                  (list 0 1 4 5 6))) (build-list n identity)))