;; =/=/=/=/= program to read connections 
;; =/=/=/=/= and find the number of hops between cities

;; == connection list (association list) functions ======================
;; store a pair of connected cities in the connection list 
;;   (AKA association list)
(defun store (c1 c2 l)
  (cond ((null l) (list (list c1 c2)))
        ((eq (caar l) c1) 
         (cond ((member c2 (cdar l)) l )
               (t (cons (cons c1 (cons c2 (cdar l)))
                        (cdr l)))))
        (t (cons (car l) (store c1 c2 (cdr l))))))
;; test (store 'a 'b '((a c)(b a)))

;; find all cities connected to city
(defun findconnections (city connections)
  (cond ((null connections) nil)
        ((eq (caar connections) city)
         (cdar connections))
        (t (findconnections city (cdr connections)))))
;; test (findconnections 'a '((b c d)(a b d)))

;; == return the set of connections for a list of cities
(defun allconnections (cities connections)
  (cond ((null cities) nil)
        (t (union (findconnections (car cities) connections)
                  (allconnections (cdr cities) connections)))))
;; test  (allconnections '(a b) '((a c d)(b e f)(c d e)))

;; store the UNDIRECTED path in the connection lists
(defun insert(c1 c2 l)
  (store c1 c2 (store c2 c1 l)))
;; test (insert 'a 'b '((a b)(b d)))

;; ================= set operations =================================
;; return the set union of two lists (l2 must be a set)
(defun union (l1 l2)
  (cond ((null l1) l2)
        ((member (car l1) l2) (union (cdr l1) l2))
        (t (union (cdr l1) (cons (car l1) l2)))))
;; test (union '(a b) '(b c))

;; return true if l1 is a subset of l2
(defun subset (l1 l2)
  (cond ((null l1) t)
        ((member (car l1) l2) (subset (cdr l1) l2))
        (t nil)))
;; test  (subset '(a b) '(a b c)) (subset '(a b) '(a c d))

;; == return the set diff s1 s2 (things in s1 not in s2)
(defun setdiff (s1 s2)
  (cond ((null s1) nil)
        ((member (car s1) s2) (setdiff (cdr s1) s2))
        ( t (cons (car s1) (setdiff (cdr s1) s2)))))
;; test (setdiff '(a b c) '(b d))

;; ===================== program functions ===============================
;; === return the association list built as we read path pairs from input
(defun path (a b l)
  (cond ((or (= a 0)(= b 0))
         nil)
        (getem (store a b (store b a l)))))

;; == return the number of hops from cities sofar to dest (nil if no connect)
;;    return nil if there is no path
(defun findhops (dest sofar connect new len)
  (cond ((member dest new) len)
        ((null new) nil)
        (t (findhops dest 
                     (union sofar new) 
                     connect 
                     (setdiff (allconnections new connect) sofar)
                     (+ 1 len)))))
;; test (findhops 'd nil '((a b)(b a c)(c d)) '(a) 0)
;; test (findhops 'a nil '((a b)(b a c)(c b)) '(c) 0)

;; == return the connection list built from inputs
(defun getem (c1 c2 l)
  (cond ((or (eq c1 0)(eq c2 0)) (terpri)(print 'FromTo) l)
        (t (print 'Connect)
           (getem (read)(read)(store c1 c2 (store c2 c1 l))))))

;; == search for a path from start to dest using connections
;;    return 'done if start or dest is zero
(defun search (connect start dest )
  (cond ((or (eq start 0)(eq dest 0)) 'done)
        (t  (print 'Hops)(print start)(print 'To)(print dest)(print 'Is)
            (print (findhops dest nil connect (list start) 0))
            (terpri)
            (print 'FromTo)
            (search connect (read)(read))))))

(defun main ()
  (print 'Connect)
  (search (getem (read) (read) nil) (read)(read)))