use warnings;
use strict;

use Algorithm::Loops qw( NestedLoops );
use Math::BigInt lib => 'GMP';

my $start_base = shift;
my $depth = shift;

my @func = qw/i s f/;  # alphabet used
# my @func = qw/s if/;
my @seq;   # Stores shortest sequences associated with each positive integer [1,200]
$seq[3] = "";

my @todo;  # Stores base elements yet to be searched.
push @todo, $start_base; # Start things off

while (@todo) {
   my $base = shift @todo;
   print "expanding $base\n";
   expand( $base, $depth);
}

for my $val (1..200) {
   print "$val: $seq[$val]\n" if defined $seq[$val];
}


### Subroutines

# Create all possible strings up to $depth long and evaluate each string
sub expand
{
   my ($base, $depth) = @_;

   NestedLoops(
               [ ( [@func] ) x $depth ],
               { OnlyWhen => 1 },
               sub{ evaluate_bigint( $base, @_); },
              );
}

# Evaluate the result of computing the expression given by a string
# Adds useful strings to @seq and pushes newly found values onto @todo
# queue.
sub evaluate_bigint
{
   my $base = shift;
   my $val = Math::BigInt->new( $base);  # create a BigInt object

   my $seq_str = join "", @_;
   my @sequence = split //, $seq_str;
   my $prefix = defined $seq[$base] ? $seq[$base] : "";

   foreach my $f (@sequence) {
      if ($f eq 'i') {    # int
         # int is a no-op for a BigInt
      }
      elsif ($f eq 's') { # sqrt
         $val->bsqrt();
      }
      else {              # factorial
         return if $val->length() > 5;  # limit max size
         $val->bfac();
      }
   }
   return if $val->length() > 3;  # only want small integers
   my $num = $val->numify();      # convert to ordinary scalar

   $seq_str = $prefix . $seq_str;
   $seq_str =~ s/^i+//;
   $seq_str =~ s/i+/i/g;
   $seq_str =~ s/fif/ff/g;

   if (! defined($seq[$num])) { # new entry
      push @todo, $num;
      $seq[$num] = $seq_str;
      print "$num: $seq_str\n";
   }
   elsif (length $seq_str < length $seq[$num]) {
      $seq[$num] = $seq_str;
   }
}

##</code><code>##

use warnings;
use strict;

use Algorithm::Loops qw( NestedLoops );
use Math::BigInt lib => 'GMP';

my $start_base = shift;
my $depth = shift;

my @seq;   # Stores shortest sequences associated with each positive integer [1,200]
$seq[3] = "";

my @todo;  # Stores base elements yet to be searched.
push @todo, $start_base; # Start things off

while (@todo) {
   my $base = shift @todo;
   print "expanding $base\n";
   expand( $base, $depth);
}

for my $val (1..200) {
   print "$val: $seq[$val]\n" if defined $seq[$val];
}


### Subroutines

# Create all possible strings up to $depth long and evaluate each string
sub expand
{
   my ($base, $depth) = @_;

   for my $len (1..$depth) {
      my $max_f = $len < 3 ? $len : 3;
      for my $f (0..$max_f) {
         my $str = 'f'x$f . 's'x($len-$f);
         evaluate_bigint( $base, $str);
      }
   }
}

# Evaluate the result of computing the expression given by a string
# Adds useful strings to @seq and pushes newly found values onto @todo
# queue.
sub evaluate_bigint
{
   my $base = shift;
   my $val = Math::BigInt->new( $base);  # create a BigInt object

   my $seq_str = shift;
   my $prefix = defined $seq[$base] ? $seq[$base] : "";
#    my $str = $prefix . $seq_str;
#    print "base: $base,  seq_str: $seq_str,  str: $str\n";

   my @sequence = split //, $seq_str;

   foreach my $f (@sequence) {
      if ($f eq 'i') {    # int
         # int is a no-op for a BigInt
      }
      elsif ($f eq 's') { # sqrt
         $val->bsqrt();
      }
      else {              # factorial
         return if $val->length() > 3;  # limit max size
         #  print "length before fac:", $val->length(), "\n";
         $val->bfac();
      }
   }
   return if $val->length() > 3;  # only want small integers
   my $num = $val->numify();       # convert to ordinary scalar

   $seq_str = $prefix . $seq_str;

   if (! defined($seq[$num])) { # new entry
      push @todo, $num;
      $seq[$num] = $seq_str;
      print "$num: $seq_str\n";
   }
   elsif (length $seq_str < length $seq[$num]) {
      $seq[$num] = $seq_str;
   }
}