; water jugs puzzle
(define (water-jugs-verbose fcap tcap target)
(let loop ((fjug 0) (tjug 0) (steps 0))
(display "step: ") (display steps)
(display "; fjug: ") (display fjug)
(display "; tjug: ") (display tjug)
(cond ((= fjug target)
(display "; done; target in fjug") (newline)
steps)
((= tjug target)
(display "; done; target in tjug") (newline)
steps)
((= tjug tcap) ; "to" jug full; empty it
(display "; tjug full; empty it") (newline)
(loop fjug 0 (+ steps 1)))
((zero? fjug)
(display "; fjug empty; fill it") (newline)
(loop fcap tjug (+ steps 1)))
(else
(display "; pour fjug into tjug") (newline)
(let ((x (min (- tcap tjug) fjug)))
(loop (- fjug x) (+ tjug x) (+ steps 1)))))))
(define (water-jugs fcap tcap target)
(let loop ((fjug 0) (tjug 0) (steps 0))
(cond ((or (= fjug target) (= tjug target)) steps)
((= tjug tcap) (loop fjug 0 (+ steps 1)))
((zero? fjug) (loop fcap tjug (+ steps 1)))
(else (let ((x (min (- tcap tjug) fjug)))
(loop (- fjug x) (+ tjug x) (+ steps 1)))))))
(define (jugs x y target)
(if (positive? (modulo target (gcd x y))) #f
(min (water-jugs x y target) (water-jugs y x target))))
(water-jugs-verbose 3 5 4) (newline)
(water-jugs-verbose 5 3 4) (newline)
(display (jugs 3 5 4)) (newline)