fork(2) download
copy 
  1. ; the gas station problem
  2.  
  3. (define (solve1 stations gasoline)
  4.   (let ((len (vector-length stations)))
  5.     (define (excess n)
  6.       (let ((m (modulo n len)))
  7.         (- (vector-ref stations m) (vector-ref gasoline m))))
  8.     (let loop ((s 0) (i 0) (exs 0))
  9.       (cond ((= s len) #f) ; no solution
  10.             ((and (= i len) (not (negative? exs))) s) ; solution
  11.             ((negative? exs) (loop (+ s 1) 0 0))
  12.             (else (loop s (+ i 1) (+ exs (excess (+ s i)))))))))
  13.  
  14. (display (solve1 '#(15 8 2 6 18 9 21 30) '#(8 6 30 9 15 21 2 18))) (newline)
  15. (display (solve1 '#(15 8 2 6 18 9 21 29) '#(8 6 30 9 15 21 2 18))) (newline)
  16.  
  17. (define (solve2 stations gasoline)
  18.   (let ((len (length stations)))
  19.     (let loop ((tank 0) ; gallons in tank
  20.                (min-tank 1000000000) ; minimum gallons so far
  21.                (start 0) ; current starting position
  22.                (pos 1) ; current position
  23.                (stations stations) (gasoline gasoline))
  24.       (if (null? stations)
  25.           (if (negative? tank) #f start)
  26.           (let ((tank (+ tank (car stations) (- (car gasoline)))))
  27.             (if (< tank min-tank)
  28.                 (loop tank tank (modulo pos len) (+ pos 1)
  29.                       (cdr stations) (cdr gasoline))
  30.                 (loop tank min-tank start (+ pos 1)
  31.                       (cdr stations) (cdr gasoline))))))))
  32.  
  33. (display (solve2 '(15 8 2 6 18 9 21 30) '(8 6 30 9 15 21 2 18))) (newline)
  34. (display (solve2 '(15 8 2 6 18 9 21 29) '(8 6 30 9 15 21 2 18))) (newline)
Success #stdin #stdout 0s 7276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
#f
6
#f
https://ideone.com/UIFtOW
language:
()
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!