AI-Pathfinding-SMAstar
view release on metacpan or search on metacpan
--- #YAML:1.0
name: AI-Pathfinding-SMAstar
version: 0.07
abstract: Simplified Memory-bounded A* Search
license: ~
author:
- Matthias Beebe <mbeebe@cpan.org>
generated_by: ExtUtils::MakeMaker version 6.42
distribution_type: module
requires:
Test::More: 0
Tree::AVL: 0
meta-spec:
url: http://module-build.sourceforge.net/META-spec-v1.3.html
version: 1.3
# when called on a node, returns 1 if it is a goal
_state_goal_p_func => \&FrontierObj::goal_test,
# must return the number of successors of a node
_state_num_successors_func => \&FrontierObj::get_num_successors,
# must return *one* successor at a time
_state_successors_iterator => \&FrontierObj::get_successors_iterator,
# can be any suitable string representation
_state_get_data_func => \&FrontierObj::string_representation,
# gets called once per iteration, useful for showing algorithm progress
_show_prog_func => \&FrontierObj::progress_callback,
);
# you can start the search from multiple start-states
# Add the initial states to the smastar object before starting the search.
foreach my $frontierObj (@start_states){
$smastar->add_start_state($frontierObj);
}
# Start the search. If successful, frontierGoalObj will contain the
# goal node. The optimal path to the goal node will be encoded in the
# ancestry of the goal node. $frontierGoalObj->antecedent() contains
# the goal object's parent, and so forth back to the start state.
my $frontierGoalObj = $smastar->start_search(
\&log_function, # returns a string used for logging progress
\&str_function, # returns a string used to *uniquely* identify a node
$max_states_in_queue, # indicate the maximum states allowed in memory
$MAX_COST, # indicate the maximum cost allowed in search
);
Explanation
In the example above, a hypothetical object, FrontierObj, is used to
represent a node in your search space. To use SMA* search to find a shortest
path from a starting node to a goal in your search space, you must define what
a node is, in your search space (or point, or state).
A common example used for informed search methods, and one that is
used in Russell's original paper, is a N-puzzle, such as an 8-puzzle or
15-puzzle. If trying to solve such a puzzle, a node in the search space
could be defined as a particular configuration of that puzzle. In the
/t directory of this module's distribution, SMA* is applied to the problem
of finding the shortest palindrome that contains a minimum number of letters
specified, over a given lexicon of words.
Once you have a definition and representation of a node in your search space, SMA*
search requires the following functions to work:
** State evaluation function (_state_eval_func above)
This function must return the cost of this node in the search space. In all
forms of A* search, this means the cost paid to arrive at this node along a path,
plus the estimated cost of going from this node to a goal state. This function
must be positive and monotonic, meaning that successor nodes mustn't be less
expensive than their antecedent nodes. Monotonicity is ensured in this implementation
of SMA*, so even if your function is not monotonic, SMA* will assign the antecedent
node's cost to a successor if that successor costs less than the antecedent.
* State successors iterator (_state_iterator above)
This function must return a *handle to a function* that returns next
successor of this node, i.e. it must return an iterator that produces
the successors of this node *one* at a time. This is
necessary to maintain the memory-bounded constraint of SMA* search.
* State get-data function (_state_get_data_func above)
This function returns a string representation of this node.
* State show-progress function (_show_prog_func above)
This is a callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.
* log string function (log_function above)
This is an arbitrary string used for logging. It also gets passed to
the show-progress function above.
* str_function (str_function above)
This function returns a *unique* string representation of this node.
Uniqueness is required for SMA* to work properly.
* max states allowed in memory (max_states_in_queue above)
An integer indicating the maximum number of expanded nodes to
hold in memory at any given time.
* maximum cost (MAX_COST above)
An integer indicating the maximum cost, beyond which nodes will not be
expanded.
DESCRIPTION
Overview
Memory-bounded A* search (or SMA* search) addresses some of the limitations of
conventional A* search, by bounding the amount of space required to perform a
shortest-path search. This module is an implementation of SMA*, which was first
introduced by Stuart Russell in 1992. SMA* is a more efficient variation of the
original MA* search introduced by Chakrabarti et al. in 1989. See references below.
Motivation and Comparison to A* Search
A* search
A* Search is an optimal and complete algorithm for computing a sequence of
fewer nodes in the search space than any other algorithm.
The space complexity of A* search is bounded by an exponential of the
branching factor of the search-space and the length of the longest path
examined during the search. This is can be a problem particularly if the
branching factor is large, as the algorithm may run out of memory.
SMA* Search
SMA* search addresses the possibility of running out of memory during search by
pruning the portion of the search-space that is being examined. It relies on the
pathmax, or monotonicity constraint on f(n) to remove the shallowest of the
highest-cost nodes from the search queue when there is no memory left to
expand new nodes. It records the best costs of the pruned nodes within their
antecedent nodes to ensure that crucial information about the search space is not
lost. To facilitate this mechanism, the search queue is best maintained as a
search-tree of search-trees ordered by cost and depth, respectively.
The pruning of the search queue allows SMA* search to utilize all available
memory for search without any danger of overflow. It can, however, make SMA*
search significantly slower than a theoretical unbounded-memory search, due to
the extra bookkeeping it must do, and because nodes may need to be re-expanded
(the overall number of node expansions may increase).
It can be shown that of the memory-bounded variations of A* search, such MA*,
IDA*, Iterative Expansion, etc., SMA* search expands the least number of nodes
on average. However, for certain classes of problems, guaranteeing optimality
METHODS
new()
Creates a new SMA* search object.
start_search()
Initiates a memory-bounded search. You must pass a log_function for recording
current status, a function that returns a *unique* string representing a node in
the search-space, a maximum number of expanded states to store in the queue, and a
maximum cost value, beyond which the search will cease.
state_eval_func()
Sets/gets the function that returns the cost of this node in the
search space.
state_goal_p_func()
Sets/gets the function that returns the number of successors of
this node.
state_successors_iterator()
Sets/gets the function that returns the next successor of
this node.
state_get_data_func()
Sets/gets the function that returns a string representation
of this node.
show_prog_func()
sets/gets the callback function for displaying the progress of the
search. It can be an empty callback if you do not need this output.
EXPORT
None by default.
SEE ALSO
Russell, Stuart. (1992) "Efficient Memory-bounded Search Methods" Proceedings
of the 10th European conference on Artificial intelligence, pp. 1-5
Chakrabarti, P. P., Ghose, S., Acharya, A., and de Sarkar, S. C. (1989) "Heuristic
search in restricted memory" Artificial Intelligence Journal, 41, pp. 197-221.
AUTHOR
Matthias Beebe, <mbeebe@cpan.org>
INSTALLATION
To install this module type the following:
perl Makefile.PL
make
make test
make install
DEPENDENCIES
This module requires these other modules and libraries:
Tree::AVL
Test::More
COPYRIGHT AND LICENCE
Copyright (C) 2010 by Matthias Beebe
This library is free software; you can redistribute it and/or modify it
under the same terms as Perl itself, either Perl version 5.10.0 or, at
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
croak "SMAstar start_search: str_function is not defined.\n";
}
sma_star_tree_search(\($self->{_priority_queue}),
\&AI::Pathfinding::SMAstar::Path::is_goal,
\&AI::Pathfinding::SMAstar::Path::get_descendants_iterator_smastar,
\&AI::Pathfinding::SMAstar::Path::fcost,
\&AI::Pathfinding::SMAstar::Path::backup_fvals,
$log_function,
$str_function,
\&AI::Pathfinding::SMAstar::Path::progress,
$self->{_show_prog_func},
$max_states_in_queue,
$max_cost,
);
}
#################################################################
#
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
#
#################################################################
sub sma_star_tree_search
{
my ($priority_queue,
$goal_p,
$successors_func,
$eval_func,
$backup_func,
$log_function, # debug string func; represent state object as a string.
$str_function,
$prog_function,
$show_prog_func,
$max_states_in_queue,
$max_cost,
) = @_;
my $iteration = 0;
my $num_states_in_queue = $$priority_queue->size();
my $max_extra_states_in_queue = $max_states_in_queue;
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
# when called on a node, returns 1 if it is a goal
_state_goal_p_func => \&FrontierObj::goal_test,
# must return the number of successors of a node
_state_num_successors_func => \&FrontierObj::get_num_successors,
# must return *one* successor at a time
_state_successors_iterator => \&FrontierObj::get_successors_iterator,
# can be any suitable string representation
_state_get_data_func => \&FrontierObj::string_representation,
# gets called once per iteration, useful for showing algorithm progress
_show_prog_func => \&FrontierObj::progress_callback,
);
# You can start the search from multiple start-states.
# Add the initial states to the smastar object before starting the search.
foreach my $frontierObj (@start_states){
$smastar->add_start_state($frontierObj);
}
#
# Start the search. If successful, $frontierGoalPath will contain the
# goal path. The optimal path to the goal node will be encoded in the
# ancestry of the goal path. $frontierGoalPath->antecedent() contains
# the goal path's parent path, and so forth back to the start path, which
# contains only the start state.
#
# $frontierGoalPath->state() contains the goal FrontierObj itself.
#
my $frontierGoalPath = $smastar->start_search(
\&log_function, # returns a string used for logging progress
\&str_function, # returns a string used to *uniquely* identify a node
$max_states_in_queue, # indicate the maximum states allowed in memory
$MAX_COST, # indicate the maximum cost allowed in search
);
In the example above, a hypothetical object, C<FrontierObj>, is used to
represent a state, or I<node> in your search space. To use SMA* search to
find a shortest path from a starting node to a goal in your search space, you must
define what a I<node> is, in your search space (or I<point>, or I<state>).
A common example used for informed search methods, and one that is used in Russell's
original paper, is optimal puzzle solving, such as solving an 8 or 15-tile puzzle
in the least number of moves. If trying to solve such a puzzle, a I<node> in the
search space could be defined as a configuration of that puzzle (a paricular
ordering of the tiles).
There is an example provided in the /t directory of this module's distribution,
where SMA* is applied to the problem of finding the shortest palindrome that
contains a minimum number of letters specified, over a given list of words.
Once you have a definition and representation of a node in your search space, SMA*
search requires the following functions to work:
=over
=item *
B<State evaluation function> (C<_state_eval_func above>)
This function must return the cost of this node in the search space. In all
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
This function must return a I<handle to a function> that produces the next
successor of the argument object, i.e. it must return an iterator function that
produces the successors of this node *one* at a time. This is necessary
to maintain the memory-bounded constraint of SMA* search.
=item *
B<State get-data function> (C<_state_get_data_func> above)
This function returns a string representation of this node.
=item *
B<State show-progress function> (C<_show_prog_func> above)
This is a callback function for displaying the progress of the search.
It can be an empty callback if you do not need this output.
=item *
B<log string function> (C<log_function> above)
This is an arbitrary string used for logging. It also gets passed to
the show-progress function above.
=item *
B<str_function> (C<str_function> above)
This function returns a *unique* string representation of this node.
Uniqueness is required for SMA* to work properly.
=item *
B<max states allowed in memory> (C<max_states_in_queue> above)
An integer indicating the maximum number of expanded nodes to hold in
memory at any given time.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=back
=head1 DESCRIPTION
=head2 Overview
Simplified Memory-bounded A* search (or SMA* search) addresses some of the
limitations of conventional A* search, by bounding the amount of space required
to perform a shortest-path search. This module is an implementation of
SMA*, which was first introduced by Stuart Russell in 1992. SMA* is a simpler,
more efficient variation of the original MA* search introduced by P. Chakrabarti
et al. in 1989 (see references below).
=head2 Motivation and Comparison to A* Search
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
examined during the search. This is can be a problem particularly if the
branching factor is large, because the algorithm may run out of memory.
=head3 SMA* Search
Like A* search, SMA* search is an optimal and complete algorithm for finding
a least-cost path. Unlike A*, SMA* will not run out of memory, I<unless the size
of the shortest path exceeds the amount of space in available memory>.
SMA* addresses the possibility of running out of memory
by pruning the portion of the search-space that is being examined. It relies on
the I<pathmax>, or I<monotonicity> constraint on I<f(n)> to remove the shallowest
of the highest-cost nodes from the search queue when there is no memory left to
expand new nodes. It records the best costs of the pruned nodes within their
antecedent nodes to ensure that crucial information about the search space is
not lost. To facilitate this mechanism, the search queue is best maintained
as a search-tree of search-trees ordered by cost and depth, respectively.
=head4 Nothing is for free
The pruning of the search queue allows SMA* search to utilize all available
memory for search without any danger of overflow. It can, however, make
SMA* search significantly slower than a theoretical unbounded-memory search,
due to the extra bookkeeping it must do, and because nodes may need to be
re-expanded (the overall number of node expansions may increase).
In this way there is a trade-off between time and space.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head2 new()
my $smastar = AI::Pathfinding::SMAstar->new();
Creates a new SMA* search object.
=head2 start_search()
my $frontierGoalObj = $smastar->start_search(
\&log_function, # returns a string used for logging progress
\&str_function, # returns a string used to *uniquely* identify a node
$max_states_in_queue, # indicate the maximum states allowed in memory
$MAX_COST, # indicate the maximum cost allowed in search
);
Initiates a memory-bounded search. When calling this function, pass a handle to
a function for recording current status( C<log_function> above- this can be
an empty subroutine if you don't care), a function that returns a *unique* string
representing a node in the search-space (this *cannot* be an empty subroutine), a
maximum number of expanded states to store in the queue, and a maximum cost
value (beyond which the search will cease).
=head2 state_eval_func()
$smastar->state_eval_func(\&FrontierObj::evaluate);
Set or get the handle to the function that returns the cost of the object
argument (node) in the search space.
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
=head2 state_successors_iterator()
$smastar->state_successors_iterator(\&FrontierObj::get_successors_iterator);
Set/get the handle to the function that returns iterator that produces the
next successor of this node.
=head2 state_get_data_func()
$smastar->state_get_data_func(\&FrontierObj::string_representation);
Set/get the handle to the function that returns a string
representation of this node.
=head2 show_prog_func()
$smatar->show_prog_func(\&FrontierObj::progress_callback);
Sets/gets the callback function for displaying the progress of the search.
It can be an empty callback (sub{}) if you do not need this output.
=head2 DEPENDENCIES
Tree::AVL
Test::More
lib/AI/Pathfinding/SMAstar.pm view on Meta::CPAN
None by default.
=head1 SEE ALSO
[1] Russell, Stuart. (1992) I<"Efficient Memory-bounded Search Methods.">
Proceedings of the 10th European conference on Artificial intelligence, pp. 1-5
[2] Chakrabarti, P. P., Ghose, S., Acharya, A., and de Sarkar, S. C. (1989)
I<"Heuristic search in restricted memory."> Artificial Intelligence Journal,
41, pp. 197-221.
=head1 AUTHOR
Matthias Beebe, E<lt>matthiasbeebe@gmail.comE<gt>
=head1 COPYRIGHT AND LICENSE
Copyright (C) 2010 by Matthias Beebe
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
sub flush {
my $h = select($_[0]); my $a=$|; $|=1; $|=$a; select($h);
}
{my $spinny_thing = "-";
my $call_num = 0;
my $state;
sub show_progress {
$call_num++;
$state = $call_num % 4;
if($state == 0){
$spinny_thing = "-";
}
elsif($state == 1){
$spinny_thing = "\\";
}
elsif($state == 2){
$spinny_thing = "|";
}
elsif($state == 3){
$spinny_thing = "/";
}
my ($progress) = @_;
my $stars = '*' x int($progress*10);
my $percent = sprintf("%.2f", $progress*100);
$percent = $percent >= 100 ? '100.00%' : $percent.'%';
print("\r$stars $spinny_thing $percent.");
flush(STDOUT);
}
}
sub show_search_depth_and_percentage {
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
flush(STDOUT);
}
{my $LINES=`tput lines`; # number of rows in current terminal window
my $COLUMNS=`tput cols`; # number of columns in current terminal window
sub show_progress_so_far {
my ($iteration, $num_states, $str, $opt_datum, $opt_datum2) = @_;
my $stars = '*' x int($iteration);
# print "\e[H"; # Put the cursor on the first line
# print "\e[J"; # Clear from cursor to end of screen
# print "\e[H\e[J"; # Clear entire screen (just a combination of the above)
# print "\e[K"; # Clear to end of current line (as stated previously)
# print "\e[m"; # Turn off character attributes (eg. colors)
# printf "\e[%dm", $N; # Set color to $N (for values of 30-37, or 100-107)
lib/AI/Pathfinding/SMAstar/Examples/PalUtils.pm view on Meta::CPAN
sub show_search_depth_and_num_states_debug {
}
{my $LINES=`tput lines`; # number of rows in current terminal window
my $COLUMNS=`tput cols`; # number of columns in current terminal window
sub show_progress_so_far_debug {
my ($depth, $prog, $num_states, $str, $num_successors) = @_;
my $stars = '*' x int($depth);
print "depth: $depth, string: $str, num_successors: $num_successors\n";
flush(STDOUT);
}
}
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
sub compare_by_depth
{
my ($self, $arg_obj) = @_;
my $self_depth = $self->{_depth};
my $argobj_depth = $arg_obj->{_depth};
my $result = $self_depth - $argobj_depth;
return $result;
}
# compare_phrase_word_strings
#
# usage: $phrase_obj->compare_phrase_word_strings($other_word_obj)
#
# Accepts another Phrase object as an argument.
# Returns 1 if greater than argument, 0 if equal, and -1 if
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
#
# Representation of a path, used in the SMAstar pathfinding algorithm.
#
# Author: matthias beebe
# Date : June 2008
#
#
package AI::Pathfinding::SMAstar::Path;
use strict;
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
sub fcost
{
my ($self) = @_;
my $fcost = $self->{_f_cost};
if(defined($fcost)){
return $fcost;
}
my $eval_func = $self->{_eval_func};
my $result = $eval_func->($self->{_state});
$self->{_f_cost} = $result;
return $result;
}
sub is_goal
{
my ($self) = @_;
my $goal_p_func = $self->{_goal_p_func};
my $result = $goal_p_func->($self->{_state});
return $result;
}
sub get_num_successors
{
my ($self) = @_;
my $num_successors_func = $self->{_num_successors_func};
my $result = $num_successors_func->($self->{_state});
return $result;
}
sub get_successors_iterator
{
my ($self) = @_;
my $successors_iterator = $self->{_successors_iterator};
my $iterator = $successors_iterator->($self->{_state});
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
my $already_produced_p = $self->{_descendants_produced}->[$i] || ($self->{_descendant_fcosts}->[$i] != -1);
if($already_produced_p){
# have already produced this descendant
$descendants_found++;
# found descendant in tree\n";
if($i == $num_successors - 1 && $descendants_deleted){
# !!! resetting iterator index. descendants have been deleted. clearing forgotten_fcosts on next expansion.
$iterator = $self->get_successors_iterator();
$self->{_iterator_index} = 0;
$i = 0;
# setting completed to 1 (true)
$self->is_completed(1);
next;
}
else{
$i++;
lib/AI/Pathfinding/SMAstar/Path.pm view on Meta::CPAN
$self->is_completed(1);
}
# break out of while() loop
last;
}
}
if($i >= $num_successors - 1 && $descendants_deleted && $self->depth() == 0){
# root node. going to reset iterator index. descendants have been deleted. Also, will be
# clearing out forgotten_descendants fcost list, since those descendants will be re-generated anyway.
$iterator = $self->get_successors_iterator();
$self->{_iterator_index} = 0;
$i = 0;
# setting completed to 1
$self->is_completed(1);
}
if($next_descendant){
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
@rev_word_objs = AI::Pathfinding::SMAstar::Examples::PalUtils::process_rev_words_by_density(\@words, $sparsity);
if(!@word_objs){
print STDERR "no words achieve density specified by max sparsity $sparsity\n";
exit;
}
$num_word_objs = @word_objs;
diag("loading avl trees.");
for (my $i = 0; $i < @word_objs; $i++) {
show_progress($i/$num_words);
my $word = $word_objs[$i]->{_word};
my $rev_word = $rev_word_objs[$i]->{_word};
$avltree->insert($word_objs[$i]);
$avltree_rev->insert($rev_word_objs[$i]);
}
show_progress(1);
print STDERR "\n";
#
# Build the words-with-candidates list. This will be used for phrases that are
# palindromes with a space in the middle position. The descendants of these
# types of palindromes are found by sort-of starting all over again... any word becomes
# a candidate for the extension of the palindrome- any word that has candidates,
# that is. By building a list of only the words that have candidates,
# the search time is greatly reduced.
#
my $i = 0;
diag("building words_w_cands_list.");
foreach my $w (@words){
show_progress($i/$num_words);
my @candidates = AI::Pathfinding::SMAstar::Examples::PalUtils::get_cands_from_left($w, $avltree, $avltree_rev);
if(@candidates){
push(@words_w_cands, $w);
}
$i++;
}
show_progress(1);
print STDERR "\n";
my $num_words_w_cands = @words_w_cands;
diag("number of word/candidate pairs is: $num_words_w_cands.");
$avltree_height = $avltree->get_height();
$avltree_rev_height = $avltree_rev->get_height();
diag("AVL trees loaded. Heights are $avltree_height, $avltree_rev_height\n\n");
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
my $smastar;
ok(
$smastar = AI::Pathfinding::SMAstar->new(
_state_eval_func => AI::Pathfinding::SMAstar::Examples::Phrase::evaluate($min_letters),
_state_goal_p_func => AI::Pathfinding::SMAstar::Examples::Phrase::phrase_is_palindrome_min_num_chars($min_letters),
_state_num_successors_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_num_successors,
_state_successors_iterator => \&AI::Pathfinding::SMAstar::Examples::Phrase::get_descendants_iterator,
_state_get_data_func => \&AI::Pathfinding::SMAstar::Examples::Phrase::roll_up_phrase,
_show_prog_func => sub{ },
#_show_prog_func => \&AI::Pathfinding::SMAstar::Examples::PalUtils::show_progress_so_far,
),
'created smastar');
diag("smastar object created");
foreach my $word (@words_w_cands){
my $sparsity = AI::Pathfinding::SMAstar::Examples::PalUtils::get_word_sparsity($word);
my $len_word = length($word);
t/AI-Pathfinding-SMAstar.t view on Meta::CPAN
sub flush {
my $h = select($_[0]); my $a=$|; $|=1; $|=$a; select($h);
}
{my $spinny_thing = "-";
my $call_num = 0;
my $state;
sub show_progress {
$call_num++;
$state = $call_num % 4;
if($state == 0){
$spinny_thing = "-";
}
elsif($state == 1){
$spinny_thing = "\\";
}
elsif($state == 2){
$spinny_thing = "|";
}
elsif($state == 3){
$spinny_thing = "/";
}
my ($progress) = @_;
my $stars = '*' x int($progress*10);
my $percent = sprintf("%.2f", $progress*100);
$percent = $percent >= 100 ? '100.00%' : $percent.'%';
print STDERR "\r$stars $spinny_thing $percent.";
flush(STDERR);
}
}
( run in 0.519 second using v1.01-cache-2.11-cpan-49f99fa48dc )