(load "moves.cl")
(load "solnA1.cl")

;;; My attempt at building an 8-puzzle state-space searcher.
;;; 1/24/96 GWC

;;; Main function: SSS
;;; Takes one required parameter,
;;; the initial state.
;;; Two optional parameters:
;;;    -type: can be BFS (default) or DFS.
;;;    -depth: a depth bound for DFS (default: 7)
;;; SSS checks whether we are at the goal.
;;; If not, it constructs the initial open list
;;; and passes control to an au illiary function that
;;; actually does the searching.
;;; The open list will be a list of lists, of the form:
;;; (<path 1> <path 2> .... <path n>)
;;; where <path i> is of the form:
;;; ((<move_k> <state_k>) (<move_k-1> <state k-1>) ...(<move_1> <state 1>))

(defun SSS (state &key (type 'BFS) (depth 7))
   (if (goal-state state) nil
     (case type
       (BFS (search-BFS (make-open-init state)))
       (DFS (search-DFS (make-open-init state) depth))
       (ID (search-ID (make-open-init state))))))


(defun search-BFS (open)
   ;; check for failure
   (if (endp open) 'FAIL
     ;; Otherwise, continue search
     ;; Get relevant stuff:
     ;; Current path
     ;; current state
     (let* ((current-path (first open))
     (current-state (get-state (first current-path))))

       (if
    ;; If we're at the goal, return the path
    (goal-state current-state) (path current-path)

  ;; Otherwise, recurse on new open list
  (search-BFS (append (rest open) (extend-path current-path)))))))

(defun search-DFS (open depth)
   ;; check for failure
   (if (endp open) 'FAIL
  ;; Otherwise, continue search
  ;; Get relevant stuff:
  ;; Current path
  ;; current state
     (let* ((current-path (first open))
     (current-state (get-state (first current-path)))
     )
       (cond
    ;; If we're at the goal, return the path
    ((goal-state current-state) (path current-path))

    ;; if we have e ceeded depth limit, recurse on rest of open list
    ((> (length current-path) depth)
     (search-DFS (rest open) depth))

    ;; Otherwise, recurse on new open list
    (t (search-DFS
        (append (extend-path current-path) (rest open))
        depth))))))

(defun search-ID (open &optional (curr-depth 0))
       (let ((dfs-try (search-DFS open curr-depth)))
          (if (eq dfs-try 'FAIL)
             (search-ID open (1+ curr-depth))
             dfs-try)))

;;; extend-path takes a path and return a list of paths
;;; each is an e tension by one move of path

(defun extend-path (path)
   ;; can't e tend an empty path
   (if (endp path) nil
     ;; find the successors of the first
     ;; element of the path, and construct
     ;; a list of new possible paths
     (extend-path-au
      (remove-redundant (moves (get-state (first path))) path)
      path)))

(defun extend-path-au  (moves path)
   (if (endp moves) nil
     (cons (append (list (first moves)) path)
    (extend-path-au  (cdr moves) path))))

;;; make-open-init
;;; This function takes one argument, "initial_state",
;;; that should be a legal state of the puzzle.
;;; It returns a legal OPEN list, with one path on it,
;;; consisting of the null move from the initial state.
;;; side effects: none
(defun make-open-init (initial_state)
   (list (list (list nil initial_state))))