Racket solution to the gas station problem:
- #lang racket
- ;; http://programmingpraxis.com/2015/07/17/the-gas-station-problem/
- (define (rotate li)
- (append (cdr li) (list (car li))))
- (define gallons #(15 8 2 6 18 9 21 30))
- (define miles #(8 6 30 9 15 21 2 18))
- (define deltas (vector-map - gallons miles))
- ;;trivial case with no solution
- (define deltas-error #(-1 -1 -1 -1 -1 -1 -1))
- (define (find-start deltas)
- (define len (vector-length deltas))
- (define (loop start i sum)
- (cond
- ;;our return condition
- ;;if we've looped around to start,
- ;;return start
- [(= start (modulo i len))
- start]
- ;;error condition, there is no solution.
- ;;return #f
- [(> i (* 2 len))
- #f]
- ;;reset condition
- ;;if sum < 0
- ;;start = i. i will loop around to 0.
- [(< sum 0)
- (loop (modulo i len) (+ 1 i) (vector-ref deltas (modulo i len)))]
- [else
- (loop start (+ 1 i) (+ sum (vector-ref deltas (modulo i len))))]))
- ;;start our loop with some
- ;;data to avoid early
- ;;termination.
- (loop 0 1 (vector-ref deltas 0)))
- (find-start deltas)
No comments:
Post a Comment