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