Causes Puzzle Solution: Improvements needed

Question

sub addMember {  
my ( $self, $newMember ) = @_;  
my $len = length($newMember->{'_data'});  
my $newMemberIndex = push(@{$self->{'_MemberList'}}, $newMember) - 1;  
$self->{'_MemberHash'}->{$newMember->{'_data'}} = \$newMember;

#Fetch bucket of same length and check for distance
my $memberList = $self->{'_Bucket'}->getBucket($len);

foreach my $index (@$memberList){  
  if($index eq $newMemberIndex) {  
    next;
  }
  my $memberObj = $self->{'_MemberList'}[$index];  
  if($self->isFriend($newMember->{'_data'}, $memberObj->{'_data'}) eq true) {  
    $newMember->addNeighbour($index);
    $memberObj->addNeighbour($newMemberIndex);
  }
}

#Fetch bucket of length - 1 and check for distance
$memberList = $self->{'_Bucket'}->getBucket($len-1);
foreach my $index (@$memberList){
  if($index eq $newMemberIndex) {
    next;
  }
  my $memberObj = $self->{'_MemberList'}[$index];
  if($self->isFriend($newMember->{'_data'}, $memberObj->{'_data'}) eq true) {
    $newMember->addNeighbour($index);
    $memberObj->addNeighbour($newMemberIndex);
  }
}
#Fetch Bucket of length + 1 and check for distance
$memberList = $self->{'_Bucket'}->getBucket($len+1);
foreach my $index (@$memberList){
  if($index eq $newMemberIndex) {
    next;
  }
  my $memberObj = $self->{'_MemberList'}->[$index];
  if($self->isFriend($newMember->{'_data'}, $memberObj->{'_data'}) eq true) {
    $newMember->addNeighbour($index);
    $memberObj->addNeighbour($newMemberIndex);
  }
}

#Add to the member list
$self->{_Bucket}->addToBucket($len, $newMemberIndex);

}

More Causes Puzzle Code...

Answer 1

Here is one idea: You could first put the words into a hashmap, the length of them being the key. O(n)

Then, since you are only interested in "causes", grab that word and make a node and remove it from the hashmap.

Then, a recursive function

• adds all friends to the node that are in the hashmap (only looking at the relevant lengths)
• removes those from the hashmap
• calls itself on those new nodes

The end result is the social graph of "causes".

It really depends what you are interested in in improving though: For instance, one could assume the whole thing is only called once for a fixed string, or it could be called many many times for different inputs. Depending on that, one might precompute more.