Skip to content

Instantly share code, notes, and snippets.

@ray1729
Created September 10, 2012 21:46
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ray1729/3694135 to your computer and use it in GitHub Desktop.
Solution to 4clojure problem 117
(fn solve-maze
[maze]
(let [num-rows (count maze)
num-cols (count (first maze))
char-at-pos (fn [[row col]] (get (get maze row) col))
free? (fn [p] (when-let [c (char-at-pos p)] (not= c \#)))
neighbours (fn [[row col]] (filter free? (map (fn [[delta-row delta-col]]
[(+ row delta-row)
(+ col delta-col)])
[[0 0] [0 1] [0 -1] [1 0] [-1 0]])))
intersects? (fn [ns s] (some #(contains? s %) ns))
contains-mouse? (fn [xs] (some #{\M} (map char-at-pos xs)))
contains-cheese? (fn [xs] (some #{\C} (map char-at-pos xs)))]
(loop [nodes (for [row (range num-rows) col (range num-cols)] [row col])
connected-subsets #{}]
(if nodes
(let [p (first nodes)]
(if (= (char-at-pos p) \#)
(recur (next nodes) connected-subsets)
(let [neighbouring-nodes (neighbours p)
neighbouring-subsets (filter
(partial intersects? neighbouring-nodes)
connected-subsets)
this-connected-subset (into (set neighbouring-nodes)
(reduce concat neighbouring-subsets))]
(recur (next nodes)
(conj (apply disj connected-subsets neighbouring-subsets)
this-connected-subset)))))
(boolean (some #(and (contains-mouse? %) (contains-cheese? %)) connected-subsets))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment