; 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)