flengyel-4clojure-solution89.clj

;; flengyel's solution to Graph Tour
;; https://4clojure.com/problem/89

(fn [edgevec]
  (letfn [(neighbors [edgevec]
      (reduce
         (fn [m e]
             (letfn [(addmap [m a b] (assoc m a (if-let [nbdset (get m a)] 
  					     (conj nbdset b) 
						    (set (list b)))))]  
               (let [a (e 0) b (e 1)]
                    (addmap (addmap m a b) b a))))
         {} edgevec))
(connected? [edgevec]
  (let [N (neighbors edgevec)
	vertices (keys N)
	q (atom clojure.lang.PersistentQueue/EMPTY)]
    (letfn [(nq [v] (swap! q #(conj  % v)))
	    (hq [] (peek @ q))
	    (dq [] (swap! q pop ))]
        (nq (first vertices))
	(loop [bag #{}]
	  (if-let [head  (hq)]
	    (do  (dq) (loop [v (vec (N head))]
		 (if (not (empty? v))
		   (do		     (if (not (contains? bag (first v))) (nq (first v)))
		     (recur (rest v)))))
               (recur (conj bag head)))
	   (= (set vertices) bag))))))
        (degmod2 [edgevec]
      (reduce
         (fn [m e]
             (letfn [(addmap [m a b] (assoc m a (if-let [bit (get m a)] (bit-xor bit 1) 1)))]  
               (let [a (e 0) b (e 1)]
                    (addmap (addmap m a b) b a))))
         {} edgevec))]
  (let [oddballs (reduce +  (vals (degmod2 edgevec)))]
    (and (connected? edgevec) (<= oddballs 2)))))