We'll use the famous animal tree:
Reptile - Snake - Python - Cobra - Lizard - Salamander - Chameleon - Bird - Pigeon - Canary - Owl Mammal - Equine - Horse - Zebra - Pony - Canine - Dog - Fox - Wolf - Bovine - Cow - Bison
All the leaves are on the same level.
Let's have a module Zoo.pm which implements the following methods:
Parent
Static method. 'Zoo'->Parent($node) returns the parent of the given node in the tree, e.g. 'Zoo'->Parent('Owl') is 'Bird', 'Zoo'->Parent('Bird') is 'Reptile'.
new
The constructor. Use a list of tree leaves as arguments:
my $zoo = 'Zoo'->new(qw( Cobra Pigeon Zebra ));
get_leaves
For a given object, returns the list it was constructed from (order is not guaranteed).
print join ' ', $zoo->get_leaves; # Cobra Pigeon Zebra
The Task
When comparing too different zoos, we aren't interested in the animals only, but in their categories, too. Our task is to implement a static method 'Zoo'->diff($zoo1, $zoo2) which returns two array references, $add and $delete, such that:
- Imagine we build trees above both of the objects, containing all their $_->get_leaves and their ancestors.
- If we start from the tree built above $zoo1, add all the nodes from $add and remove all nodes from $delete, we get $zoo2.
- Both the lists @$add and @$delete are minimal.
For example,
'Zoo'->diff( 'Zoo'->new('Cobra'), 'Zoo'->new('Fox') )
should return
( [qw[ Fox Canine Mammal ]], [qw[ Cobra Snake Reptile ]] )
Similarly,
'Zoo'->diff( 'Zoo'->new(qw( Dog Fox Wolf )), 'Zoo'->new(qw( Fox )));
should return
( [], [ 'Dog', 'Wolf' ] )
Updates: Please, use <readmore> tags for the code.
Use only the documented API in the solution (i.e. Parent and get_leaves). The tree structure is not accessible directly (in reality, it was stored in a database).
($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,