After thinking about it some more, I think the following solution fixes my efficiency problem while simplifying the function. I'm not guaranteeing it works, but I think it will.<br><br>(defn lib-test<br> [x y checked]<br>
(if (some #{[x y]} checked)<br> checked<br> (reduce #(lib-test (first %2)<br> (second %2)<br> (clojure.set/union %1 #{[x y]}))<br> (cons checked (friends x y)))))<br>
<br>The main power here is done with 'reduce', which in this case takes a list composed of 'checked' followed by a bunch of x-y pairs. This way, it should run in linear time instead of n^2.<br><br>-Tom<br>
<br><div class="gmail_quote">On Wed, Nov 2, 2011 at 9:54 PM, Thomas Helmuth <span dir="ltr"><<a href="mailto:thGST@hampshire.edu">thGST@hampshire.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I would be tempted to write a more recursive, slightly simpler solution to this problem. I have no idea if the following solution is more or less efficient than Lee's code, and also have not tested it.<div class="im">
<br><br>(defn lib-test<br>
[x y checked]<br></div> (if (some #{[x y]} checked)<br> checked<br> (apply clojure.set/union<br> (map #(lib-test (first %)<br> (second %)<br> (clojure.set/union checked #{[x y]}))<br>
(friends x y)))))<br><br>This code is called on an x-y pair and an empty set, and returns a set of pairs. If the pair is in 'checked', then it just returns 'checked'. Otherwise, it maps a function over the sequence returned by 'friends'. The mapping function takes an x-y pair from 'friends' and recursively calls lib-test on the pair as well as 'checked' with [x y] added. The map results in a sequence of sets, where each set contains pairs that are in the group. Thus, we can just union them together to get the result.<br>
<br>Now that I think about it, this might find every path to every stone in a group. This may be of some concern, since it makes an algorithm that runs in O(n^2) time for a problem that should be solvable in linear time. Maybe to improve the efficiency, you need to do something like what Lee did. But, it's always helpful to see a different solution.<br>
<br>-Tom<br>
</blockquote></div><br>