document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #lang racket
  2.  
  3. ;; http://programmingpraxis.com/2015/07/17/the-gas-station-problem/
  4.  
  5. (define (rotate li)
  6.   (append (cdr li) (list (car li))))
  7.  
  8.  
  9. (define gallons #(15 8 2 6 18 9 21 30))
  10.  
  11. (define miles #(8 6 30 9 15 21 2 18))
  12.  
  13. (define deltas (vector-map - gallons miles))
  14.  
  15. ;;trivial case with no solution
  16. (define deltas-error #(-1 -1 -1 -1 -1 -1 -1))
  17.  
  18. (define (find-start deltas)
  19.   (define len (vector-length deltas))
  20.   (define (loop start i sum)
  21.     (cond
  22.       ;;our return condition
  23.       ;;if we\'ve looped around to start,
  24.       ;;return start
  25.       [(= start (modulo i len))
  26.        start]
  27.       ;;error condition, there is no solution.
  28.       ;;return #f
  29.       [(> i (* 2 len))
  30.        #f]
  31.       ;;reset condition
  32.       ;;if sum < 0
  33.       ;;start = i. i will loop around to 0.
  34.       [(< sum 0)
  35.        (loop (modulo i len) (+ 1 i) (vector-ref deltas (modulo i len)))]
  36.       [else
  37.        (loop start (+ 1 i) (+ sum (vector-ref deltas (modulo i len))))]))
  38.   ;;start our loop with some
  39.   ;;data to avoid early
  40.   ;;termination.
  41.   (loop 0 1 (vector-ref deltas 0)))
  42.  
  43. (find-start deltas)
');