;Solution to Water Jug Problem using Breadth First Search 
;By: Rohit Kumar
;Dt: 12/10/02

(setq global-list ())
(setq flag nil)

(defun CheckRepeat (x)
	(setq CheckRepeat nil)
	(let (temp)
		(setq flag nil)
		(dolist (temp global-list)
			(if (equal x temp)
				(setq flag t)
			)
			(if flag (return-from CheckRepeat))
		)
	)
)

(defun BFS (x y)
	(setq global-list (cons (cons x (cons y ())) global-list))
	(if (eq 2 x) (return-from BFS))
	(let (local-list)
		(setq local-list ())
		(if (< x 4) 
			(setq local-list (cons (cons 4 (cons y ())) local-list))
		)
		(if (< y 4) 
			(setq local-list (cons (cons x (cons 3 ())) local-list))
		)
		(if (> x 0) 
			(setq local-list (cons (cons 0 (cons y ())) local-list))
		)
		(if (> y 0) 
			(setq local-list (cons (cons x (cons 0 ())) local-list))
		)
		(if (and (<= (+ x y) 4) (> y 0))
			(setq local-list (cons (cons (+ x y) (cons 0 ())) local-list))
		)
		(if (and (<= (+ x y) 3) (> x 0))
			(setq local-list (cons (cons 0 (cons (+ x y) ())) local-list))
		)
		(if (and (>= (+ x y) 4) (> y 0))
			(setq local-list (cons (cons 4 (cons (- y (- 4 x)) ())) local-list))
		)
		(if (and (>= (+ x y) 3) (> x 0))
			(setq local-list (cons (cons (- x (- 3 y)) (cons 3 ())) local-list))
		)
		(if (and (eq 0 x) (eq 2 y))
			(setq local-list (cons (cons 2 (cons 0 ())) local-list))
		)
		(if (eq 2 x)
			(setq local-list (cons (cons 0 (cons y ())) local-list))
		)
		(dolist (nexttry local-list)
			(CheckRepeat nexttry)
			(if (not flag)
				(BFS (car nexttry) (car (cdr nexttry)))
			)
			(if (eq 2 (car (car global-list)))
				(return-from BFS)
			)
		)
	)
	(setq global-list (cdr global-list))
)

(defun SolveWaterJug ()
	(setq global-list ())
	(BFS 0 0)
	(dolist (onestep (reverse global-list))
		(print onestep)
	)
)
