my $hint = '1234';
my @wild = ('a'..'z','0'..'9');
my $wild = '{'. join(',',@wild).'}';
my @pw = (<$hint$wild$wild>,
          <$wild$hint$wild>,
          <$wild$wild$hint>);
[download]

Everytime I post here I'm absolutely astounded by the depth of the feedback - many thanks again to everyone who replied - ya'll got some good karma headed your way.

I was looking to build a recursive subroutine that given a $gss and $hint of arbitrary length, and given a @set of valid characters, could generate a @list of all possibilities (without overflowing the call stack) but I think now that I'm probably overthinking the problem (or at least being overly ambitious given my time limitations) - since I know the max length of the password (6 chars) I should probably just hack it using one of the methods described in the replies above...

Thank you much Monks!

This might be a possible solution

#!/usr/bin/perl -w
use strict;

my $hint = '1234';
my @chars = ('0'..'9', 'a'..'z');
my $len = 6 - length $hint;

&append ("");

sub append {
        my $s = shift;


        if (length $s >= $len) {
                &hint($s);
                return;
        }
        foreach (@chars) {
                my $new = $s.$_;
                &append ($new);
        }
}

sub hint {
        my $s = shift;
        my $new;
        for (my $i=0; $i<=length($s); ++$i) {
                $s =~ m/^(.{$i})(.*)$/;
                $new = $1.$hint.$2;
                print $new."\n";
        }
}
[download]

But for larger password sizes, this could fill the call stack, so, as long as you know the exact length of the password, you could get rid of the recursion by hardcoding nested foreach()-loops instead. My first idea, how to do it with flexible password sizes and without recursion, would be to write a code generator that nests the necessary number of foreach()-loops for you, using the password size as a parameter. Maybe this is too complicated but the only thing that comes to my mind at the moment.

Occasionally, most of us would like to have an operation which generates a matching string from a regex. There is no such thing in perl (or elsewhere, afaik).

You want a list of all qualified strings which contain a given substring. One way is to generate all the "free" strings that qualify and insert the known substring into each possible location.

my $len = 6;
my $hint = q(1234);
my $free = $len - length $hint;
my @brute_list;

for my $seed ( '0'x$free .. '9'x$free ) {
    for ( 0 .. $free ) {
        my $string = $seed;
        substr( $string, $_, 0) = $hint;
        push @brute_list, $string;
    }
}

print "@{brute_list}$/";
[download]

Occasionally, most of us would like to have an operation which generates a matching string from a regex. There is no such thing in perl (or elsewhere, afaik).

Not a Perl regex exactly, but (naively) in the same category -- see my reply further down.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Regexps are more for going the other way around: given this password, separate it into the hint and other characters. Sure, you could use substitution to produce a password from a hint pattern:

  $other = "x!4Y";
  $password = $PATTERN; # $PATTERN is aHINTbcd
  $password =~ s/a/x/; # or $password =~ s/a/substr($other,0,1)/e;
  $password =~ s/b/!/;
  $password =~ s/c/4/;
  $password =~ s/d/Y/;
[download]

  $other = "x!4Y";
  $password = $PATTERN; # $PATTERN is aHINTbcd
  $password =~ tr/abcd/$other/;
[download]

  $password = substr($other, 0, 1).$HINT.substr($other, 1, 3);
[download]

  $password = join('', substr($other, 0, 1), $HINT, substr($other, 1, 
+3));
[download]

Yes, regexps implicitly do looping, so it is possible to do the entire thing with a "single" (ir)regexp, but it would be a mess, and much harder to write than straightforward code. (I put "single" in quotes because the body of the regexp would contain at least one code block with multiple statements.)

More likely, you could generate every possible full-length password and use a regexp to filter out the ones containing the hint -- but that rather defeats the purpose of having a hint.

So, to restate your problem, you are looking to match between zero and length - hint_length arbitrary characters, the hint and between zero and length - hint_length arbitrary characters. The perlre sign for "between zero and infinity" is *, though you can be more specific (hint: look for the bit about curly braces in the doc link). Good luck -- old-hand at semester end cramming recommends starting earlier next time ;-).

Given that you know the set of characters allowed as part of the password, then I suspect that some nested-loop approach (having those characters in an array) would probably constitute the expected solution.

That said, I'm sure it would be easier in perl than in java. For example, if the password length is N and the length of the "hint" substring is M, you could loop over all possible character sequences of length N-M, and for each of those, insert the hint string at each juncture within the sequence (offset 0, offset 1, ... offset N-M).

(Update: in other words, what Zaxo said :)

You mentioned you wanted to recursion. Recursion (or more specifically, a stack) is the tool of choice to use if you want to do a depth-first search. However, a depth-first search is not optimal here, since people usually choose passwords much smaller then the maximum length. For example,

# Depth-first search
# Max length = 20
1234
1234a
1234aa
1234aaa
1234aaaa
...
1234aaaaaaaaaaaaaaaa
1234b
1234bb
...
[download]

A breadth-first search would be more appropriate. For example,

# Breadth-first search
1234
1234a
1234b
1234c
...
12348
12349
1234aa
1234ab
1234ac
...
[download]

Breadth-first search uses a queue, not a stack, so recursion is not appropriate. Regexps are also inappropriate because they strength is in backtracking, which is done using stacks. So let's look at a breadth-first solution:

use strict;
use warnings;

sub crack {
   my $hint       = shift;
   my $target     = shift;
   my $salt       = substr($target, 0, 2);
   my @chars      = @_;
   my @to_process = ( '' );
   my $passwd;

   while (@to_process) {
      my $pad = shift(@to_process);

      push(@to_process, $pad . $_)
         foreach @chars;
   
      for my $pos (0..length($pad)) {
         $passwd = $pad;
         substr($passwd, $pos, 0, $hint);

         return $passwd
            if crypt($passwd, $salt) eq $target;
      }
   }
}

my @chars = ('a'..'z', 'A'..'Z', '0'..'9');

print crack('12',   crypt('d12e',    'AA'), @chars), "\n";
print crack('1234', crypt('aa12345', 'AA'), @chars), "\n";
[download]

Unfortunately, the above takes way too much memory. We need to find an interator which generates the next item to process on the fly. Since the to-process list is a simple incrementing sequence, it's not only possible to generate the next item on the fly, it's rather simple. The following code performs a breadth-first search using virtually no stack or heap memory:

Working solution withheld for a week, since you said this was for class.

Oops, it's been more than a week. Here's the promised code

use strict;
use warnings;

sub crack {
   my $hint   = shift;
   my $target = shift;
   my $salt   = substr($target, 0, 2);
   my @chars  = @_;
   my $base   = @chars;
   my $passwd;

   use integer;

   for (my $num_chars=0; ; $num_chars++) {
      for (my $enc=0; ; $enc++) {
         my $i = $enc;
         my $pad = '';
         for (1..$num_chars) {
            my $idx = $i % $base;
            $i = $i / $base;
            $pad .= $chars[$idx];
         }

         # Go add a character.
         last if $i;

        #$pad = reverse $pad;

         for my $pos (0..$num_chars) {
            $passwd = $pad;
            substr($passwd, $pos, 0, $hint);

            return $passwd
               if crypt($passwd, $salt) eq $target;
         }
      }
   }
}

my @chars = ('a'..'z', 'A'..'Z', '0'..'9');

print crack('12',   crypt('d12e',    'AA'), @chars), "\n";
print crack('1234', crypt('aa12345', 'AA'), @chars), "\n";
[download]