Re: Small puzzle

[David Steuber <david.steuber@verizon.net>]

On Wed, Oct 15, 2003 at 01:34:15AM -0400, Mark Dominus wrote:
> 
> 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?

Simpler is not always better if you are reducing the number of
instructions executed in terms of O(n) notation.

Does each node have a comparitor function like is_equal()?

sub common_ancestor {
  my ($a, $b) = @_;
  for (my $node = $b; $node; $node = $b->parent()) {
    return $node if $a->is_equal($node);
  }
  return common_ancestor($a->parent(), $b) if $a->parent();
  return undef;
}

#include <std_disclaimer>

This is just off the cuff and I haven't thought it through.  Your
example misses that F & G have A as a common ancestor.

If the above algorithm is correct, it still suffers from O(n^2) runtime
possibility.

-- 
David Steuber           |  telco:610.436.1677
302 E Marshall St       |  http://www.david-steuber.com/
Apt 612                 |  (do ((a 1 b) (b 1 (+ a b)))
West Chester, PA 19380  |      (nil a) (print a))
-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**