[Cs254f11] Recursion without loop

[Thomas Helmuth]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.hampshire.edu/pipermail/cs254f11/attachments/20111102/bfa588d7/attachment.htm>