From now on, I'm archiving explanations of my Perl Golf solutions here. The latest golf by Ton Hospel required generating all distinct permutations of the letters given as command-line parameters. Here's my 52 character entry (which placed second):

/;s/(.) /${$_="$1$`$'"}||=do$0/ge||print

The code uses a simple recursive algorithm for the problem:

  • If there are no input elements, print the accumulated elements
  • Otherwise, select each of the input elements in turn, and recurse with the same parameters, except that the element is moved from the input list to the accumulator list

This being Perl Golf we'll be using strings instead of lists for the input/accumulator. And since manipulating any non-$_ variables tends to be bothersome, we'll keep both the input and the accumulator in the same string.

The input/accumulator parts of the string need to be distinguished somehow. The format I've chosen is that the accumulated elements come first (unseparated), followed by the input elements (all input elements have a trailing space), followed by a newline. So for example the string 'cba d \n' has the elements 'c' and 'b' accumulated, and the elements 'a' and 'd' are still unprocessed.

The advantage of this format is that it's easy to initialize, thanks to the original input being in @ARGV. The first statement of the program (s/^$/@ARGV \n/) sets $_ to a string containing the input elements trailed by a single spaces. The substitution will only happen when $_ is empty, thanks to the left-hand side of the s///.

After initializing $_, we get to the real meat. The first expression of the second statement (s/(.) /${$_="$1$`$'"}||=do$0/ge) will match all of the still unprocessed characters in the input. The right-hand side of the s///ge is evaluated (we don't care about the return value, since the substitution is only used as a looping construct here). We first assign a new value for $_; basically just move the selected element to the start of the string (into the accumulator), and remove the trailing space. After that, we do the recursion using do$0, which basically executes the same program with the same enviroment again (this is why the original initialization of $_ had to only happen when $_ is empty).

The reason s///g is so useful as a looping construct is that it continues to work on the original value of the variable that we're substituting, no matter what's actually done inside the right-hand side. So even though we clobbered the value of $_, Perl has saved for us the only piece of context that we needed.

Once the second substitution fails, $_ obviously doesn't contain any more input. $_ therefore contains the accumulator (in the correct output format), followed by a newline. A simple print that's triggered when the substitution fails takes care of the output.

Unfortunately, we still need to filter out duplicate solutions since the rules called for printing only the distinct permutations. The natural method is marking each printed permutation into a hashtable, and only print a permutation if it's not already there.

We use a couple of small optimizations to this scheme. Instead of using a hashtable, we use Perls symbol table (well, technically it's a hashtable too). And second, we'll do the checking and incrementing at the same time, using the short-circiting ||=-operator. The linenoise-like bits of code in the solution (${...}||=...) are responsible for this. The left-hand side makes a symbolic reference to the value inside the brackets (in this case the value that was assigned to $_), and the ||= assigns a (true) value to that reference, assuming it's old value was false.

So there you have it. I probably won't post such a long explanation for most future golfs.