Hi all, I am new to functional programming and thought this might be interesting to others to see my approach to this kind a recursion problem. I found this problem hard to think through, does anyone have any suggestions for simpler solution to this type of problem?
I needed a recursive backtracking algorithm that did not consume the stack so to test out how I might go about writing it I wrote a trampolined version of maze solver that I had to write at uni. The maze solver algorithm is something like what can be seen here http://www.cs.bu.edu/teaching/alg/maze/ it is basically a fairly unintelligent brute force solution but very simple to implement with four self recursive calls (one for each direction) but not easily using tail recursion. The version I have implemented here is not as simple but it is trampolined so that it doesn't consume the stack and it is functional without mutation. It brakes the problem down into two mutually recursive functions recur-forward and backtrack. Note: This test does not use a large enough maze to worry about blowing the stack (you would need a very large maze) but the real algorithm I will need to write will be much more deeply recursive than this. Here is the code, the solve-maze function looks large but it is really two functions wrapped up in a function using letfn so the caller does not have to worry about using trampoline. (def test-maze [[:X :X :X :X :X :X :X :X :X :X] [:X :o :X :o :o :o :o :o :o :X] [:X :o :X :o :o :o :X :o :o :X] [:X :o :X :o :o :X :X :o :o :X] [:X :o :X :X :o :o :X :o :o :X] [:X :o :o :X :X :o :X :X :o :X] [:X :o :o :X :F :o :o :X :o :X] [:X :o :o :o :X :X :X :X :o :X] [:X :o :X :o :o :o :o :o :o :X] [:X :X :X :X :X :X :X :X :X :X]]) (defn tile-in-bounds? [[x y] maze] (let [h (count maze)] (if (and (>= y 0) (>= x 0) (< y h)) (if (< x (count (maze y))) true)))) (defn get-tile [[x y] maze] (if (tile-in-bounds? [x y] maze) ((maze y) x))) (defn update-tile [[x y] maze value] (if (tile-in-bounds? [x y] maze) (assoc maze y (assoc (maze y) x value)) maze)) (defn valid-tile? [[x y] maze] (= (get-tile [x y] maze) :o)) (defn print-maze [maze] (if (coll? maze) (print (map println-str maze)) (println maze))) (defn filter-neighbours [f [x y] maze] (for [dir (list [0 -1] [1 0] [0 1] [-1 0]) :when (f (map + [x y] dir) maze)] (map + [x y] dir))) (defn valid-neighbours [[x y] maze] (filter-neighbours #(valid-tile? %1 %2) [x y] maze)) (defn find-neighbours [match [x y] maze] (filter-neighbours #(= (get-tile %1 %2) match) [x y] maze)) (defn solve-maze [[init-x init-y] init-maze] (letfn [(recur-forward [[x y] track maze] (if-not (empty? (find-neighbours :F [x y] maze)) #(backtrack true (conj track [x y]) maze) (let [neighbours (valid-neighbours [x y] maze) next-maze (update-tile [x y] maze :?) next-track (conj track [x y])] (if-not (empty? neighbours) #(recur-forward (first neighbours) next-track next- maze) #(backtrack false track next-maze))))) (backtrack [found track maze] (let [curr-track (pop track) solved-maze (update-tile (first track) maze :*)] (if found (if (empty? curr-track) maze #(backtrack found curr-track solved-maze)) (let [curr-coord (first curr-track) neighbours (valid-neighbours curr-coord maze) next-maze (update-tile curr-coord maze :*)] (if-not (empty? neighbours) #(recur-forward curr-coord (rest track) maze) #(backtrack found curr-track maze))))))] (let [start [init-x init-y]] (trampoline recur-forward start (list start) init-maze)))) (print-maze (solve-maze [1 1] test-maze)) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
