Re: Small puzzle

[Jason Proctor <jproctor@persons.marlboro.edu>]

> The common ancestor of D and G is B;
> the common ancestor of D and E is B;
> the common ancestor of D and B is B;
> the common ancestor of D and A is A;
> the common ancestor of D and F is A;
> the common ancestor of G and E is E;
> the common ancestor of D and M is undefined
> the common ancestor of N and M is M.
>
> My function to do this is 18 lines long.  This is way too much code.
> I am sure there must be a simpler solution.  Can anyone think of a
> simpler solution?

Maybe.  But it's probably not going to be me before I've had some coffee
this morning.  It was very clever not actually telling us how you did it,
so we wouldn't be influenced by your algorithm.

It's not obvious how you generated your list of nodes to compare.  Is that
supposed to be part of the function, or is it just an example that it'll
be called multiple times?

Assuming the latter, is this youngest common ancestor function the sort of
thing you want to optimize for (thus 18 lines being "too long") or is it
just an incidental feature?  Or somewhere in between?

My first thought was if, in addition to the parent() method, there were an
ancestors() method that returns a complete list.  To optimize speed (at
the expense of memory, of course), carry the list around with the node.
If that's not an option, generate it each time.  Step through $list1 until
you find an element in $list2, or return undef.

If finding parents is expensive (another tree search?), make it a
recursion problem.  I'd call yca() with anonymous listrefs: [ $node1 ] and
[ $node2 ].  The yca() function compares those lists.  If there's no
match, push onto each list the parent of the last node in the list and
call yca() on the new lists.  You could do one list at a time, but it's
impossible to judge which list to focus on without having the lists
already.  If parent-finding is *really* expensive, comparatively, you
could pick one at random instead of doing both, but even in the optimal
case (one node is an ancestor of another, and you always pick the
"correct" node to regress), you only cut your effort in half.  Naturally,
if neither list has a new parent to push, there's no common ancestor.

Either way, I don't think you're looking at much less than 15-20 "lines".
You could apply some obfuscation to make it take less vertical space, but
you're not likely to make it much less computationally complex.


j
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**