jugs.scm

;; Adam Coffman
;; Scheme Assignment 2
;; Jugs Problem
;;Program to solve the "Jugs Problem" from die hard 3.
;;invoked with (Jugs CapacityJugA CapacityJugB GoalFillofA)
;;returns a step by step path to the goal.
;;IE (Jugs 5 3 4) would return
;;((0 0 5 3) (5 0 5 3) (2 3 5 3) (2 0 5 3) (0 2 5 3) (5 2 5 3) (4 3 5 3))

;;Suporting Functions
;;Fill Jug A
(define Fill-A
  (lambda (L)
    (cons (caddr L) (cdr L))
    ))

;;Fill Jug B
(define Fill-B
  (lambda (L)
    (cons (car L) (cons (cadddr L) (cddr L)))
    ))

;;Empty Jug A
(define Empty-A
  (lambda (L)
    (cons '0 (cdr L))
    ))

;;Empty Jug B
(define Empty-B
  (lambda (L)
    (cons (car L) (cons '0 (cddr L)))
    ))

;;Pour Contents of A into B
(define A-to-B
  (lambda (L)
    (if (<= (car L) (-(cadddr L)(cadr L))) (cons '0 (cons (+ (cadr L)(car L)) (cddr L))) 
        (cons (- (car L)(-(cadddr L)(cadr L))) (cons (cadddr L)(cddr L))))
    ))

;;Pour contents of B into A
(define B-to-A
  (lambda (L)
    (if (<= (cadr L) (-(caddr L)(car L))) (cons (+ (car L)(cadr L)) (cons '0 (cddr L)))
        (cons (caddr L) (cons (- (cadr L)(- (caddr L)(car L))) (cddr L))))
    ))

;;List of all possible operations that can be done.
(define op-list '(Fill-A Fill-B Empty-A Empty-B A-to-B B-to-A))


;;Run each op in the op-list on the members of lst
(define extend 
   (lambda (lst) ;; lst is the local name for node-list i.e, path-list
     (do ((ops op-list (cdr ops)) (cur-node (caar lst)) (new '())) ;; initialize
       ((null? ops) (cdr lst))         ;; remove cur-node when return
       (set! new ((eval (car ops)) cur-node))
       (if (not (in new lst))
           (set! lst (append lst (list (cons new (car lst)))))) ; 
     )
   )
)
;;Checks to see if element a is in list l
(define in 
  (lambda (a l)
    (cond ((null? l) #f)
          ((equal? a (car l)) #t)
          ((list? (car l)) 
           (or (in a (car l))(in a (cdr l))))
          (else (in a (cdr l))))))


;; Takes Three Arguments, the size of jug a, the size of jug b, and the goal volume for jug a.
(define Jugs
  (lambda (sizeA sizeB goal)
    (do ((node-list (list (list (list 0 0 sizeA sizeB))))) ;; var, init node-list is path-list in doc
        ((or (null? node-list) (equal? goal (caaar node-list)))
         (if (null? node-list) '() (reverse (car node-list))))
        (set! node-list (extend node-list))) ;; loop body
                                             ;; node-list = extend(node-list);
   )
)