Re: Small puzzle

[Abigail <abigail@abigail.nl>]

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?


I've 12 lines of code. It's the function 'lca' in the code below.
Beside the 'parent' method, the objects also have a 'name' method,
returning their label. I also created an extra node, with the empty
string as a label, itself as a parent, and with A and M as its children.
It's also assumed that no node has label '0'.

Here's the code:
#!/usr/bin/perl

use strict;
use warnings;

{
    package Node;
                         
    my %parent;
    my %name;

    sub DESTROY {
        my $self = shift;
        delete $parent {$self};
        delete $name   {$self}
    }
    
    sub new {
        my $class = shift;
        my $self  = bless \my $x => $class;
    }
        
    sub parent {
        my $self = shift;
        if (@_) {
            $parent {$self} = shift;
            return $self;
        }
        $parent {$self}  
    }

    sub name   {
        my $self = shift;
        if (@_) {
            $name   {$self} = shift;
            return $self;
        }
        $name   {$self}
    }
}                        
    
package main;

my %parents = (A => "", M => "", qw /
    B A
    C A
    D B
    E B
    F C
    G E
    N M
/);
     
my %node;
    
# "Super" node with label "", which is its own parent.
$node {""} = Node -> new
                  -> name ("");
$node {""} -> parent ($node {""});
         
# Abuse the fact keys are sorted in the tree.
foreach my $name (sort keys %parents) {
    my $parent = $parents {$name};
    $node {$name} = Node -> new
                         -> parent ($node {$parent})
                         -> name   ($name);
}
            
         
# This is the function that finds the lowest common ancestor.
# For each node, create a list, starting with itself, followed by
# all the ancestors, in order, ending with "".
# Given two lists, pop off ancestors until we've found a difference.
sub lca {
    my ($node1, $node2) = @_;
    my @parents1 = $node1;
    my @parents2 = $node2;
    while ($node1 -> name) {$node1 = $node1 -> parent; push @parents1 => $node1}
    while ($node2 -> name) {$node2 = $node2 -> parent; push @parents2 => $node2}
    while (@parents1 > 1 && @parents2 > 1 && $parents1 [-2] == $parents2 [-2]) {
        pop @parents1;
        pop @parents2;
    }  
    $parents1 [-1];
}
       
my @pairs = ([qw /D G/], [qw /D E/], [qw /D B/], [qw /D A/], [qw /D F/],
             [qw /G E/], [qw /D M/], [qw /N M/], [qw /E E/], [qw /A A/],
             [qw /A M/]);
    
foreach my $pair (@pairs) {
    my ($node1, $node2) = map {$node {$_}} @$pair;
    printf "The common ancestor of %s and %s is %s\n",
                      $node1 -> name,
                      $node2 -> name,
                       lca ($node1, $node2) -> name || "undefined";
}
__END__
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
The common ancestor of E and E is E
The common ancestor of A and A is A
The common ancestor of A and M is undefined

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