AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
if($memo_cache{$memo_key}){
return @{$memo_cache{$memo_key}};
}
else{
my @letters = split('', $word);
my @difference = ();
my %letters_hash = ();
my %letters_seen_hash = ();
my $intersect_num = 0;
my @intersection;
foreach my $element (@$sorted_letters_seen) { $letters_seen_hash{$element}++ }
foreach my $element (@letters) { $letters_hash{$element}++ }
foreach my $element (keys %letters_hash) {
if($letters_seen_hash{$element}){
push(@intersection, $element);
$intersect_num++;
}
else{
push(@difference, $element);
}
}
my @answer = ($intersect_num, @difference);
$memo_cache{$memo_key} = \@answer;
return ($intersect_num, @difference);
}
}
}
sub word_collision{
my ($word,
$letters_seen) = @_;
my @letters = split('', $word);
my @difference = ();
my %letters_hash = ();
my %letters_seen_hash = ();
my $intersect_num = 0;
my @intersection;
foreach my $element (@$letters_seen) { $letters_seen_hash{$element}++ }
foreach my $element (@letters) { $letters_hash{$element}++ }
foreach my $element (keys %letters_hash) {
if($letters_seen_hash{$element}){
push(@intersection, $element);
$intersect_num++;
}
else{
push(@difference, $element);
}
}
return ($intersect_num, @difference);
}
sub get_cands_from_left
{
my ($word,
$dictionary,
$dictionary_rev) = @_;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
if (@_) { $self->{_match_remainder_left} = shift }
return $self->{_match_remainder_left};
}
sub match_remainder_right {
my $self = shift;
if (@_) { $self->{_match_remainder_right} = shift }
return $self->{_match_remainder_right};
}
sub intersect_threshold {
my $self = shift;
if (@_) { $self->{_intersect_threshold} = shift }
return $self->{_intersect_threshold};
}
sub max_collisions{
my $self = shift;
if (@_) { $self->{_max_collisions} = shift }
return $self->{_max_collisions};
}
sub letters_seen{
my $self = shift;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
elsif($direction == 1){
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
#----------------Letters Seen-----------------------------------------------
my @sorted_letters_seen = sort(@$letters_seen);
# how much does this word collide with the letters seen so far, and what are the new letters?
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision($word, \@sorted_letters_seen);
# store the difference in new letters_seen value.
push(@sorted_letters_seen, @differences);
my $new_num_chars_so_far = @sorted_letters_seen;
#-----------------------------------------------------------
my @words_to_make_phrases;
my $stored_c;
return sub{
LABEL1:
# this is a continuation of the second case below, where there were no
# match-remainders for the phrase-so-far, i.e. the palindrome has a space
# in the middle with mirrored phrases on each side. 'cat tac' for example.
my $next_word = shift(@words_to_make_phrases);
if($next_word){
my $w = $next_word;
my $repeated_word_p = 0;
my $antecedent = $phrase_obj->{_predecessor};
my $antecedent_dir = $antecedent->{_dir};
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
if($repeated_word_p || $w eq $word){
goto LABEL1;
#next; #skip this word, we are already looking at it
}
#----------------Compute the Cost-------------------------------------------
my $len_w = length($w);
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($w, $phrase_obj->{_phrase});
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($w);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($w);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision($w,
\@sorted_letters_seen);
my $num_new_chars = $num_chars - $word_intersect;
#my $newcost = $collisions_per_length + $sparsity;
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
#_words_w_cands_list => \@words_to_make_phrases,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
$num_new_chars = 0;
$newcost = 0; # new candidate is a (reversed) substring of word
$new_cost_so_far = $cost + $cost_so_far;
}
elsif($len_c > $len_word){
#if($len_c != $len_word){
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($match_remainder, $phrase_obj->{_phrase});
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($match_remainder);
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($match_remainder);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision_memo($match_remainder,
\@sorted_letters_seen);
$num_new_chars = $num_chars - $word_intersect;
#$newcost = $sparsity + $collisions_per_length;
$newcost = $collisions_per_length + $len_match_remainder;
$new_cost_so_far = $cost + $cost_so_far;
}
#---------------------------------------------------------------------------
if($match_remainder){ # there is a length difference between the candidate and this word.
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
_predecessor => $phrase_obj,
_dir => $new_direction,
_repeated_pal_hash_ref => $repeated_pal_hash_ref,
_letters_seen => \@sorted_letters_seen,
_cost => $newcost,
_cost_so_far => $new_cost_so_far,
_num_chars_so_far => $new_num_chars_so_far,
_num_new_chars => $num_new_chars,
_depth => $depth+1,
);
#print "returning new phrase from second cond.\n";
$new_phrase->{_phrase} = $new_phrase->roll_up_phrase();
return $new_phrase;
}
else{
#
# There is no match_remainder, so this candidate is the reverse
# of $word, or the phrase built so far is an "even" palindrome,
# i.e. it has a word boundary (space) in the middle.
#
#
# This is a special case since there is no match remainder.
# Because there is no remainder to create new phrase obj from, this
# section goes through the whole word list and creates phrase objects
# for each new word. The number of new characters offered by each
# word is recorded to help with guided search.
#
# Update: this case now only goes through the word list for which there
# are cands.
@words_to_make_phrases = @$words_w_cands;
#@words_to_make_phrases = @$words;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
if($repeated_word_p || $w eq $word){
goto LABEL1;
#next; #skip this word, we are already looking at it
}
#----------------Compute the Cost-------------------------------------------
my $len_w = length($w);
my $collisions_per_length = AI::Pathfinding::SMAstar::Examples::PalUtils::collisions_per_length($w, $phrase_obj->{_phrase});
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity_memo($w);
my $num_chars = AI::Pathfinding::SMAstar::Examples::PalUtils::num_chars_in_word_memo($w);
my ($word_intersect, @differences) = AI::Pathfinding::SMAstar::Examples::PalUtils::word_collision_memo($w,
\@sorted_letters_seen);
my $num_new_chars = $num_chars - $word_intersect;
#my $newcost = $collisions_per_length + $sparsity;
my $newcost = $collisions_per_length + $len_w;
my $new_cost_so_far = $cost + $cost_so_far;
#---------------------------------------------------------------------------
my $new_phrase = AI::Pathfinding::SMAstar::Examples::Phrase->new(
_word_list => $words,
_words_w_cands_list => $words_w_cands,
_dictionary => $dictionary,
_dictionary_rev => $dictionary_rev,
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
my @words_to_make_phrases;
my $stored_c;
my $num_successors = 0;
while(1){
# this is a continuation of the second case below, where there were no
# match-remainders for the phrase-so-far, i.e. the palindrome has a space
# in the middle with mirrored phrases on each side. 'cat tac' for example.
my $next_word = shift(@words_to_make_phrases);
if($next_word){
my $w = $next_word;
my $repeated_word_p = 0;
my $antecedent = $phrase_obj->{_predecessor};
my $antecedent_dir = $antecedent->{_dir};
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
else{
#
# There is no match_remainder, so this candidate is the reverse
# of $word, or the phrase built so far is an "even" palindrome,
# i.e. it has a word boundary (space) in the middle.
#
#
# This is a special case since there is no match remainder.
# Because there is no remainder to create new phrase obj from, this
# section goes through the whole word list and creates phrase objects
# for each new word. The number of new characters offered by each
# word is recorded to help with guided search.
#
# Update: this case now only goes through the word list for which there
# are cands.
@words_to_make_phrases = @$words_w_cands;
#@words_to_make_phrases = @$words;
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
@cands = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_right($word, $dictionary, $dictionary_rev);
}
my @words_to_make_phrases;
my $stored_c;
return sub{
LABEL:
# this is a continuation of the second case below, where there were no
# match-remainders for the phrase-so-far, i.e. the palindrome has a space
# in the middle with mirrored phrases on each side. 'cat tac' for example.
my $next_word = shift(@words_to_make_phrases);
if($next_word){
my $w = $next_word;
my $repeated_word_p = 0;
my $antecedent = $phrase_obj->{_predecessor};
my $antecedent_dir = $antecedent->{_dir};
lib/AI/Pathfinding/SMAstar/Examples/Phrase.pm view on Meta::CPAN
}
else{
#
# There is no match_remainder, so this candidate is the reverse
# of $word, or the phrase built so far is an "even" palindrome,
# i.e. it has a word boundary (space) in the middle.
#
#
# This is a special case since there is no match remainder.
# Because there is no remainder to create new phrase obj from, this
# section goes through the whole word list and creates phrase objects
# for each new word. The number of new characters offered by each
# word is recorded to help with guided search.
#
# Update: this case now only goes through the word list for which there
# are cands.
@words_to_make_phrases = @$words_w_cands;
#@words_to_make_phrases = @$words;
( run in 0.819 second using v1.01-cache-2.11-cpan-39bf76dae61 )