RE: Small puzzle

["Wilson, Douglas" <dgwilson@sonomasystems.net>]

This seems to work and is O(N) to build the data structures
and O(N) to find a parent (especially if have only a
single line of parentage (e.g. A => B => C => D, etc).

I just return the string 'undef' for the sake of printing
and keeping it simple...

the find_ancestor function is 11 lines, but hey, this is
perl, so you could condense it to 1 lines if you wanted
too :-)

#!/usr/bin/perl

use strict;
use warnings;

my %tree = (
  A => {
    B => { D => undef, E => { G => undef } },
    C => { F => undef },
  },
  M => { N => undef },
);

my %parents;
my %is_parent;
build_data(undef, \%tree);
print find_ancestor( "D", "G" ),"\n";
print find_ancestor( "D", "E" ),"\n";
print find_ancestor( "D", "B" ),"\n";
print find_ancestor( "D", "A" ),"\n";
print find_ancestor( "D", "F" ),"\n";
print find_ancestor( "G", "E" ),"\n";
print find_ancestor( "D", "M" ),"\n";
print find_ancestor( "N", "M" ),"\n";

sub build_data {
  my ($parent, $tree) = @_;
  while ( my ($key, $value) = each %$tree ) {
    if (defined $parent) {
      $is_parent{$key}{$parent} = undef;
      @{$parents{$key}} = $parent;
      if (exists $parents{$parent}) {
        undef @{$is_parent{$key}}{@{$parents{$parent}}};
        push @{$parents{$key}}, @{$parents{$parent}};
      }
    }
    build_data($key, $value) if ref $value;
  }
}

sub find_ancestor {
  my ($node1, $node2) = @_;
  return $node1 if exists $is_parent{$node2}{$node1};
  return $node2 if exists $is_parent{$node1}{$node2};
  return 'undef'
    unless exists $parents{$node1}
       and exists $parents{$node2};
  for my $parent (@{$parents{$node1}}) {
    return $parent if exists $is_parent{$node2}{$parent};
  }
  return 'undef';
}
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**