[Cs254f11] Recursion without loop

[Lee Spector]

That is indeed elegant in a way, and I *think* it will work -- hard to say for sure without running it! -- but also think it will be quite a bit slower because it calls itself recursively on friends even if they've already been checked... But that could be fixed by changing the thing you're mapping over from (friends x y) to a sequence made from the set difference of (friends x y) and checked... But I think you'll still be doing more work than you need to, when, as you say, there are multiple paths to a stone. The set union will clean things up afterwords, but it can't undo the extra work you've done.

That said, my loop-based solution does a lot of the same work in a different way. The comment I made above about not looking again at friends that have already been checked could also be applied to my solution, changing the call to "concat" to something that only adds in things that aren't in checked. And I'm not really sure what all of the tradeoffs will be.

Max, since you have all of the support code you could try various options and let us know what you find!

But optimization probably isn't as important as clarity here. I'd do whatever is most clear to you and most clearly works, and worry about optimization only if/when you have performance problems and a good reason to believe that this particular algorithm is contributing to them in a significant way (which I doubt will happen).

 -Lee


On Nov 2, 2011, at 9:54 PM, Thomas Helmuth wrote:

> 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.
> 
> (defn lib-test
>   [x y checked]
>   (if (some #{[x y]} checked)
>     checked
>     (apply clojure.set/union
>            (map #(lib-test (first %)
>                            (second %)
>                            (clojure.set/union checked #{[x y]}))
>                 (friends x y)))))
> 
> 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.
> 
> 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.
> 
> -Tom

--
Lee Spector, Professor of Computer Science
Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438