A recursive formulation is exactly the right idea. Also, you're right when you say it won't work with recur as you've set it up. In fact, you won't be able to use recur at all in this situation as a you are doing a depth-first search through possible paths--it's impossible to formulate a depth-first search as a tail-recursive function.
You are definitely on the right track with your current idea. Though I would offer a hint: it's even simpler to return a sequence of all the paths (in a way very similar to how you've set it up) without using ANY of the state ref types. On Sep 21, 9:29 am, ax2groin <ax2gr...@gmail.com> wrote: > I've been working through algorithm problems to learn the language a > little better. I'm currently struggling with the question about a > "robot" traversing a grid. If the grid is completely open, then the > answer to "how many possible ways to traverse the grid?" is simply the > math for combinations using factorials (see Project Euler #15). But if > you suppose that some places in the grid are blocked or that you have > to actually traverse the paths? > > I know that the code below doesn't work yet (recur is not at the > tail). Think of it as pseudo-code to show my intent. I've left out the > other methods to get at the heart of what I'm asking about. > Essentially, each path leads to two more recursion points (at least > the way I've formulated it in my "else"), until they finally run out > of bounds or meet the goal. The input "n" represents the width of the > square grid. I'm using a two-element vector to represent a point in > the grid. > > (defn get-paths > [n] > (let [paths (agent '()) goal (vector n n)] > (loop [point [0 0] path '()] > (cond (points-equal? goal point) (send paths conj (conj path > point)) > (out-of-bounds? n point) nil > (blocked? point) nil > :else (recur (inc-x point) (conj path point)) > (recur (inc-y point) (conj path point)))) > (deref paths))) > > Perhaps ultimately, the approach I've tried here is a dead-end? I'm > not sure that this loop formulation would ever exit, or perhaps it > would exit too quickly. -- 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
