; the gas station problem

(define (solve1 stations gasoline)
  (let ((len (vector-length stations)))
    (define (excess n)
      (let ((m (modulo n len)))
        (- (vector-ref stations m) (vector-ref gasoline m))))
    (let loop ((s 0) (i 0) (exs 0))
      (cond ((= s len) #f) ; no solution
            ((and (= i len) (not (negative? exs))) s) ; solution
            ((negative? exs) (loop (+ s 1) 0 0))
            (else (loop s (+ i 1) (+ exs (excess (+ s i)))))))))

(display (solve1 '#(15 8 2 6 18 9 21 30) '#(8 6 30 9 15 21 2 18))) (newline)
(display (solve1 '#(15 8 2 6 18 9 21 29) '#(8 6 30 9 15 21 2 18))) (newline)

(define (solve2 stations gasoline)
  (let ((len (length stations)))
    (let loop ((tank 0) ; gallons in tank
               (min-tank 1000000000) ; minimum gallons so far
               (start 0) ; current starting position
               (pos 1) ; current position
               (stations stations) (gasoline gasoline))
      (if (null? stations)
          (if (negative? tank) #f start)
          (let ((tank (+ tank (car stations) (- (car gasoline)))))
            (if (< tank min-tank)
                (loop tank tank (modulo pos len) (+ pos 1)
                      (cdr stations) (cdr gasoline))
                (loop tank min-tank start (+ pos 1)
                      (cdr stations) (cdr gasoline))))))))

(display (solve2 '(15 8 2 6 18 9 21 30) '(8 6 30 9 15 21 2 18))) (newline)
(display (solve2 '(15 8 2 6 18 9 21 29) '(8 6 30 9 15 21 2 18))) (newline)