Re: Small puzzle

["Eric J. Roode" <sdn@comcast.net>]

On Wed, Oct 15, 2003 at 01:34:15AM -0400, Mark Dominus wrote:
> 
> I have a bunch of nodes, which are abstract objects.  Nodes have a
> 'parent' method, which returns the parent node, if there is one, or
> 'undef' if not.  I can also compare two nodes to see if they are
> equal.  No node has more than one parent.
> 
> I want to write a function which, given a list of nodes, returns the
> youngest common ancestor of all the nodes in the list, or undef if
> there is no common ancestor.  For example, given nodes organized like
> this:
> 
> 
>                 A               M
>                / \              |
>               B   C             N
>              / \  |
>             D   E F
>                 |
>                 G
> 
> 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?

Untested, but straightforward.
Not counting braces, my(), blank lines, the sub declaration, the
return line, and comments, it's three lines.

Assumes equal(undef, undef) returns true, which may or may not
be a good assumption.

sub ancestor
{
    my @a = shift;
    my @b = shift;
    my $ancestor;

    # Get lists of both objects' ancestors
    $ap[@ap] = $ap[-1]->parent while defined $ap[-1];
    $bp[@bp] = $bp[-1]->parent while defined $bp[-1];

    # Find the earliest one in common, working backwards from root(s).
    pop @bp and $ancestor = pop @ap
        while @ap && @bp && !equal($ap[-1], $bp[-1]);

    return $ancestor;
}   

-- 
Eric J. Roode                                            sdn@comcast.net
$_ = reverse sort $/.r , qw p ekca ts lre reh
uJ p, map $_ . $" , qw e p h tona e and print

Attachment: pgpp1X7IhedrA.pgp
Description: PGP signature