UF CAP 4621 Artificial Intelligence HW2Solution

HW2 Solution Developed in LISP The following is a solution that I developed to HW 2 using Lisp. This solution is developed in a very general manner so it will solve any jug problem -- all you must do is change the variables in the hw-2 function to specify your starting state, ending state, and maximum depth of search. I hope this serves as a reasonable model of code development for you when you are developing your solutions to the project.

---

;; this program solves the jug problem in a general manner
;; change the value of start-state, which specifies the
;; starting liquid amounts for each container; end-state,
;; which specifies the ending liquid amounts for each
;; container; and max-depth, which specifies the maximum
;; number of moves that you wish to try in generating the
;; solution. The program will print all solutions having
;; max-depth moves or less
(defun hw-2 ()
   (setq start-state '(12 12 0 7 0 5))
   (setq end-state '(6 12 6 7 0 5))
   (setq path ())
   (setq max-depth 11)
   (d-search start-state end-state path max-depth)
   )

;; d-search performs the depth-first search of the search space
;; by (1) checking to see if we have a solution, (2) if we have
;; searched to the maximum depth, then (3) trying, successively,
;; each of the possible moves -- which recursively calls this
;; routine to try the next level down in the search
(defun d-search (s-state e-state path depth)
   (cond ((equal s-state e-state) (print (reverse (cons e-state path))))
         ((<= depth 0) nil)
         (t (try 1 2 s-state e-state path depth)
            (try 1 3 s-state e-state path depth)
            (try 2 1 s-state e-state path depth)
            (try 2 3 s-state e-state path depth)
            (try 3 1 s-state e-state path depth)
            (try 3 2 s-state e-state path depth)) )
   )

;; try tries to make a move by pouring liquid from "from"
;; to "to". It first looks to see if position from is empty then if
;; position full is full -- these are halting situations. It then
;; pours the maximum from "from" to "to" and calls d-search with
;; this new state
(defun try (from to s-state e-state path depth)
   (cond ((empty from s-state) nil)
         ((full to s-state) nil)
         (t (d-search (gen-new-state from to s-state) e-state (cons s-state path) (- depth 1)))
   ) )

;; empty looks at the container in position pos in the state to
;; see if it is empty
(defun empty (pos state)
   (zerop (retrieve-amt pos state))
   )

;; retrieve-amount returns the amount of liquid in the specified
;; container at position, pos, of the state
(defun retrieve-amt (pos state)
   (cond ((equal pos 1) (car state))
         ((equal pos 2) (caddr state))
         ((equal pos 3) (caddr (cddr state)))
         ) )

;; full looks to see if the container at position pos is full
;; by comparing the amount in the position to the max amount
(defun full (pos state)
   (equal (retrieve-amt pos state) (retrieve-max pos state))
   )

;; retrieve-max returns the amount of liquid that the container
;; in position pos can hold as a maximum
(defun retrieve-max (pos state)
   (cond ((equal pos 1) (cadr state))
         ((equal pos 2) (cadddr state))
         ((equal pos 3) (caddr (cdddr state)))
         ) )

;; gen-new-state generates a new state by pouring the maximum amount
;; from container "from" to container "to"
(defun gen-new-state (from to state)
   (setq max-to-pour (retrieve-amt from state)) ; amount in the "from" state
   (setq current-amt (retrieve-amt to state))   ; amount in the "to" state
   (setq max-hold (retrieve-max to state))      ; amount to state can hold
   (setq max-pour-amt (- max-hold current-amt)) ; max that can be added to "to" state
   (cond ((> max-pour-amt max-to-pour)
          (new-state from 0 to (+ current-amt max-to-pour) state) )
         (t (new-state from (- max-to-pour max-pour-amt) to max-hold state)))
   )

;; new-state forms the new state from the values computed in gen-new-state
(defun new-state (state1 amt1 state2 amt2 state)
   (list (cond ((equal state1 1) amt1)
               ((equal state2 1) amt2)
               (t (car state)))
      (cadr state)
      (cond ((equal state1 2) amt1)
            ((equal state2 2) amt2)
            (t (caddr state)))
      (cadddr state)
      (cond ((equal state1 3) amt1)
            ((equal state2 3) amt2)
            (t (caddr (cddr state))))
      (cadddr (cddr state)) ) )

Internal Links

Parent Article: UF CAP 4621 Artificial Intelligence Homework