#!/usr/local/bin/sbcl --script
(DEFUN GET_ADJACENT_CITIES (CITY) (
	COND
	((STRING-EQUAL CITY "ZERIND")
	 `("ORADEA" "ARAD")
	)
	((STRING-EQUAL CITY "ORADEA")
	 `("ZERIND" "SIBIU")
	)
	((STRING-EQUAL CITY "ARAD")
	 `("ZERIND" "SIBIU" "TIMISOARA")
	)
	((STRING-EQUAL CITY "SIBIU")
	 `("ORADEA" "ARAD" "FAGARAS" "RIMNICU VILCEA")
	)
	((STRING-EQUAL CITY "FAGARAS")
	 `("SIBIU" "BUCHAREST")
	)
	((STRING-EQUAL CITY "RIMNICU VILCEA")
	 `("SIBIU" "CRAIOVA" "PITESTI")
	)
	((STRING-EQUAL CITY "TIMISOARA")
	 `("ARAD" "LUGOJ")
	)
	((STRING-EQUAL CITY "LUGOJ")
	 `("TIMISOARA" "MEHADIA")
	)
	((STRING-EQUAL CITY "MEHADIA")
	 `("DROBETA" "LUGOJ")
	)
	((STRING-EQUAL CITY "DROBETA")
	 `("CRAIOVA" "MEHADIA")
	)
	((STRING-EQUAL CITY "CRAIOVA")
	 `("DROBETA" "PITESTI" "RIMNICU VILCEA")
	)
	((STRING-EQUAL CITY "PITESTI")
	 `("CRAIOVA" "RIMNICU VILCEA" "BUCHAREST")
	)
	((STRING-EQUAL CITY "BUCHAREST")
	 `("FAGARAS" "PITESTI" "URZICENI" "GIURGIU")
	)
	((STRING-EQUAL CITY "GIURGIU")
	 `("BUCHAREST")
	)
	((STRING-EQUAL CITY "URZICENI")
	 `("BUCHAREST" "HIRSOVA" "VASLUI")
	)
	((STRING-EQUAL CITY "HIRSOVA")
	 `("URZICENI" "EFORIE")
	)
	((STRING-EQUAL CITY "EFORIE")
	 `("HIRSOVA")
	)
	((STRING-EQUAL CITY "VASLUI")
	 `("IASI" "URZICENI")
	)
	((STRING-EQUAL CITY "NEAMT")
	 `("IASI")
	)
	((STRING-EQUAL CITY "IASI")
	 `("VASLUI" "NEAMT")
	)
))

(defun ORDER (LIST ORDER) (COND
	((STRING-EQUAL ORDER "ASCENDING")
	 (SORT LIST #'STRING-LESSP))
	((STRING-EQUAL ORDER "DESCENDING")
	 (SORT LIST #'STRING-GREATERP))
))


(defun extract-path-from-goal (goal start)
  (setf path-goal nil)
  (setf path-goal (cons goal path-goal))
  (loop
    (setf goal (intern goal))
    (setf goal (get goal 'previous-goal))
    (setf path-goal (cons goal path-goal))
    (if (string-equal goal start) (return))
  )
)


(defun extract-path-from-start (goal start)
  (setf path-start nil)
  (setf path-start (cons goal path-start))
  (loop 
    (setf goal (intern goal))
    (setf goal (get goal 'previous-start))
    (setf path-start (cons goal path-start))
    (if (string-equal goal start) (return))
  )
)

(setf forbidden-city (list "FAGARAS" "GIURGIU"))

(defun bds-dfs (start goal order forbidden-city)
  (setf path-found 'false)
  (setf no-solution-start 'false)
  (setf no-solution-goal 'false)
  (setf n 0)
  
  (setf open-start (list start))
  (setf closed-start nil)
  
  (setf open-goal (list goal))
  (setf closed-goal nil)
  
  (setf start-search-tree nil)
  (setf goal-search-tree nil)
  
  (format t "~%Closed List for Start after Iteration ~d: ~a" n closed-start)
  (format t "~%Open List for Start after Iteration ~d: ~a" n open-start)
  (format t "~%Closed List for Goal after Iteration ~d: ~a" n closed-goal)
  (format t "~%Open List for Goal after Iteration ~d: ~a" n open-goal)    
  (format t "~%Start Search Tree at Iteration ~d: ~a" n start-search-tree)
  (format t "~%Goal Search Tree at Iteration ~d: ~a" n goal-search-tree) 

  (loop
    (if (null open-start) (progn (setf no-solution-start 'true)(return "NO SOLUTION FOUND")))        ; IF OPEN LIST IS NULL

    (setf to-explore-from-start (car open-start))                                        ; NEXT CITY TO EXPLORE  
    (setf open-start (cdr open-start))                                              ; CITIES THAT ARE WAITING TO BE EXPLORED
    
    (dolist (x forbidden-city)
     (if (string-equal to-explore-from-start x) 
      (multiple-value-setq (to-explore-from-start open-start) (values (car open-start) (cdr open-start)))
     )
    )

    (setf closed-start (cons to-explore-from-start closed-start))                              ; STORE EXPLORED CITIES INTO CLOSED LIST
    ;(format t to-explore-from-start)
    (setf descendants-start (ORDER (GET_ADJACENT_CITIES to-explore-from-start) order)); GET THE SUCCESSOR CITIES OF CURRENT EXPLORED CITY
    (setf descendants-start (set-difference descendants-start closed-start :test #'string=))              ; CHECK AND FILTER CITIES WHICH ARE EXPLORED
    (setf descendants-start (reverse descendants-start))

    (setf open-start (append descendants-start (reverse (set-difference open-start descendants-start :test #'string=))))  ; APPEND ALL THE SUCCESSOR CITIES OF CURRENT EXPLORED CITY IN OPEN LIST AND DEDUPLICATE

    (dolist (x descendants-start)
      (setf (get (intern x) 'previous-start) to-explore-from-start)  
    )



    ;;; DEPTH FIRST SEARCH FROM GOAL
    (if (null open-goal) (progn (setf no-solution-goal 'true)(return nil)))        ; IF OPEN LIST IS NULL

    (setf to-explore-from-goal (car open-goal))                                        ; NEXT CITY TO EXPLORE  
    (setf open-goal (cdr open-goal))                                              ; CITIES THAT ARE WAITING TO BE EXPLORED

    (dolist (x forbidden-city)
     (if (string-equal to-explore-from-goal x) 
      (multiple-value-setq (to-explore-from-goal open-goal) (values (car open-goal) (cdr open-goal)))
     )
    )
    
    (setf closed-goal (cons to-explore-from-goal closed-goal))                              ; STORE EXPLORED CITIES INTO CLOSED LIST
    ;(format t to-explore-from-goal)
    (setf descendants-goal (ORDER (GET_ADJACENT_CITIES to-explore-from-goal) order)) ; GET THE SUCCESSOR CITIES OF CURRENT EXPLORED CITY
    (setf descendants-goal (set-difference descendants-goal closed-goal :test #'string=))              ; CHECK AND FILTER CITIES WHICH ARE EXPLORED
    (setf descendants-goal (reverse descendants-goal))

    (setf open-goal (append descendants-goal (reverse (set-difference open-goal descendants-goal :test #'string=))))  ; APPEND ALL THE SUCCESSOR CITIES OF CURRENT EXPLORED CITY IN OPEN LIST AND DEDUPLICATE

    (dolist (x descendants-goal)
      (setf (get (intern x) 'previous-goal) to-explore-from-goal)  
    )

    (dolist (city closed-goal)
      (if (string-equal city (find city closed-start :test #'string=))
        (progn (setf to-explore-from-goal city) (setf to-explore-from-start city) (setf path-found 'true))
      )
    )
    
    (format t "~%")
    (if (equal path-found 'true) 
      (progn (extract-path-from-goal to-explore-from-goal goal)
        (extract-path-from-start to-explore-from-start start)
        (return "path found")
      )
    )
    
    (incf n)
    (format t "~%Closed List for Start after Iteration ~d: ~a" n closed-start)
    (format t "~%Open List for Start after Iteration ~d: ~a" n open-start)
    (format t "~%Closed List for Goal after Iteration ~d: ~a" n closed-goal)
    (format t "~%Open List for Goal after Iteration ~d: ~a" n open-goal)    
    
    (setf start-search-tree (append closed-start start-search-tree))
    (setf start-search-tree (append (reverse open-start) start-search-tree))
    (setf output-start-search-tree (reverse (REMOVE-DUPLICATES start-search-tree :test #'string=)))
    (format t "~%Start Search Tree at Iteration ~d: ~a" n output-start-search-tree)
    
    (setf goal-search-tree (append closed-goal goal-search-tree))
    (setf goal-search-tree (append (reverse open-goal) goal-search-tree))
    (setf output-goal-search-tree (reverse (REMOVE-DUPLICATES goal-search-tree :test #'string=)))
    (format t "~%Goal Search Tree at Iteration ~d: ~a" n output-goal-search-tree) 
  )
)  



(bds-dfs "ARAD" "IASI" "ASCENDING" forbidden-city)
                  
;(print path-start)
;(print path-goal)
;(print (append path-start (reverse path-goal)))

(setf start-nodes-generated (+ (list-length open-start) (list-length closed-start)))
(setf goal-nodes-generated (+ (list-length open-goal) (list-length closed-goal)))
(setf total-nodes-generated (+ start-nodes-generated goal-nodes-generated))
(format t "~%Total Number of Nodes Generated: ~d" total-nodes-generated)

;ADD IF NO SOLUTION FOUND
(if (or (equal no-solution-start 'true) (equal no-solution-goal 'true)) (format t "~%Cannot Find Solution")
  (progn
    (setf solution-path (remove-duplicates (append path-start (reverse path-goal)) :test #'string=))
    (format t "~%Solution Path: ~a" solution-path)
  )
)


(setf path-cost (- (list-length solution-path) 1))
(format t "~%Path Cost: ~d" path-cost)