20170402 - stagecoach-problem.rkt used to solve stagecoach problem.

stagecoach-problem.rkt

#lang racket
;; 20170402 - stagecoach-problem.rkt used to solve stagecoach problem.
;; license: MIT license
;; by Yoxem




;; cost table from O to D with cost in 2D hash-tables
(define cost-table
  #hash((1 . #hash(
                   (2 . 3)
                   (3 . 4)
                   (4 . 5))
          )
        (2 . #hash(
                   (5 . 2)
                   (6 . 1)
                   (7 . 6))
          )
        (3 . #hash(
                   (5 . 5)
                   (6 . 7)
                   (7 . 1))
          )
        (4 . #hash(
                   (5 . 2)
                   (6 . 3)
                   (7 . 4))
          )
       (5 . #hash(
                   (8 . 6)
                   (9 . 7))
          )
       (6 . #hash(
                   (8 . 1)
                   (9 . 3))
          )
       (7 . #hash(
                   (8 . 4)
                   (9 . 6))
          )
       (8 . #hash((10 . 5)))
       (9 . #hash((10 . 2))
          
        )
))

;; cost function
(define (cost orig dest)
  ; return inf when find no cost (that means no path from O-D).
  (with-handlers ((exn:fail? (lambda (exn)
                               +inf.0)))
    ; return the cost
    (hash-ref (hash-ref cost-table orig) dest)))


;; like list(range()) in python.
;;; (range 10) -> '(0 1 2 3 4 5 6 7 8 9)
(define (range n)
  (cond ((= n 0) '())
       (else (append (range (- n 1)) (list (- n 1))))
))

;; min of the list and its number.
(define (min-of-list L i index)
  (define m (car L))
    (cond
      ((eq? (cdr L) '()) (append (list m) (list index)))
      ((> m (car(cdr L))) (min-of-list(cdr L) (+ i 1) (+ i 1)))
      (else (min-of-list(append (list m) (cdr(cdr L))) (+ i 1) index)))

  )


(define range10 (range 10))
(define (f s)
(define raw-result (f-iter s))
  (define (location-result-iter res l)
    (cond  ((eq? l '()) res) 
    ((eq? (cdr l) '()) (append res (list (car l))))
    (else (location-result-iter (append res (list(car l))) (cdr l)))
    ))
  (define location-result (location-result-iter (list s) (car(cdr raw-result))))
  (define min-cost (car raw-result))
  

  (define (display-loc-iter loc-res)
    (display (car loc-res))
    (if (eq? (cdr loc-res) '())
         (newline)
         
         (begin (display "→")
           (display-loc-iter (cdr loc-res)))
    ))
  
  (define (display-result cost loc-res)
    (display "最短路徑為：")
    (display-loc-iter loc-res)
    (display "最短里程：")
    (display cost)
    (newline))
  
  (display-result min-cost location-result)
  (list min-cost location-result)
)

(define (f-iter s)
  (define list_ (map (lambda (number)
         (if (= (cost s (+ 1 number)) +inf.0)
            +inf.0
            (+ (cost s (+ 1 number)) (car(f-iter (+ 1 number)))))) 
       range10)
       )
    (define point-list (map (lambda (number)
         (if (= (cost s (+ 1 number)) +inf.0)
            +nan.0
           (cdr(f-iter (+ 1 number))))) 
       range10))
       
  (define min-point (min-of-list list_ 1 1))
(if (= 10 s) (list 0 '())
     (list (car min-point) (append (cdr min-point) (car(list-ref point-list (- (car(cdr min-point)) 1))))))
  )

;; count the shortest path from point 1 to 10
(f 1)