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