1
\$\begingroup\$

The "Causes" puzzle is to recursively find, starting with the word "causes", the number of words that can be formed by substituting one letter.

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);

}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.