This is part 2.5 of a 3 part series (part 1 & part 2 have been previously posted) -- I realized that there was one more supplimental step that in this case is somewhat separate from the other parts but is necessary to finish the sequence.

The same definitions from part 2 will still apply as we are dealing with cipher and normal text.

Update: as pointed out by Zaxo below, unless a sufficient 'chuck' of the alphabet is used by the cipher, even with a 26 character alphabet the memory will be quickly used up. I'm going to alter the problem statement significantly to avoid problems with both this and the upcoming part 3, with the original noted below the line; those that want to try the latter are free to do so, but I encourage the golfers to try their hand at the top solution instead.

Given: an alphabet string, and a 'translation' string (same length as alphabet), as well as a word in the cipher-text and it's translation. The translation string is set up such that for every character in alphabet, the corresponding character in the translation string is either the normal text character that should replace the ciphertext character from the alphabet, or the character ' ', implying that that ciphertext character has yet to be defined to any normal text character. As an example:

Alphabet:    abcdef
Translation: d a  c
[download]

means that ciphertext 'a' is normaltext 'd', and the same with 'c' and 'f' representing 'a' and 'c', respectively. What 'b', 'd', and 'e' represent is not yet known. You may assume that ' ' will never be part of the given alphabet.

A translation string with no ' ' characters (eg, the full translation is known) must be a permutation of the given alphabet. Note that these can be used to convert cipher text to normal text via eval "tr/$alphabet/$translation/"

Find the perl golf subroutine that returns either a new translation string which keeps all assignments already in the given translation string plus any additional assignments that can be made in converting the ciphertext word to normaltext, or 0/undef if the translation string as it stands cannot convert the cipher text to the normal text word withour changing an existing assignment.

Examples what what would be expected:

my $alpha = "abcdef";
my $cipher = "abcadbbe";
my $word   = "deadbeef";

extend_translation( $alpha, "      ", $cipher, $word );
# should return "deabf "
# note that when the entire translation is given as 
# only ' 's, this sub should always return a new 
# translation string

extend_translation( $alpha, "     c", $cipher, $word );
# should return "deabfc"

extend_translation( $alpha, "c     ", $cipher, $word );
# should return 0 or undef, since cipher 'a' is already
# representing normal 'c', and the two words would 
# require that 'a' means 'd', instead, so the 
# translation cannot work in this case.

my $tr = extend_translation( $alpha, "     ", "ebba", "feed" );
# after this step, $tr = "de  f "
if ( $tr ) { 
    $tr = extend_translation( $alpha, $tr, $cipher, $word );
    # after this step, $tr = "deabf "
}
[download]

---

Original problem statement follows:

Given: a 'word' in cipher text, and a 'word' of the same length in normal text. Both cipher and normal text use the same given alphabet, as given by a string of characters (from the 7-bit ASCII set).

Find in a perl golf solution a subroutine that returns an array of all possible permutations of the alphabet such that applying a tr/// function will convert the cipher word into the normal text word, or returns an empty array if no such translation is possible.

For example, the code should be able to do the following:

my $alpha = "elprxyz";
my $cipher = "zyxe";
my $normal = "perl";

my @array = translation_set( $alpha, $cipher, $normal );

foreach my $trans ( @array ) {
   $_ = $cipher;
   eval "tr/$alpha/$trans/";  #need to eval in order to 
                              #expand variables
   print $trans, ": ", $_,"\n";
}

# Would expect (but not necessarily in this order:)
# lxyzrep: perl
# lxzyrep: perl
# lyxzrep: perl
# lyzxrep: perl
# lzxyrep: perl
# lzyzrep: perl
[download]

Hint: you may need to revisit some of the previous Golf puzzles that I've got on my home node.

Extra credit: Same task, but given an array of cipher words, and an associated array of normal words, such that $cipher[$i] correspondes to $normal[$i]. Arguments should be passed by reference in this case.

(those that have been following this series of puzzles can see where the last one will be going with this one, so you can get a nice head start on #3 which I'll post next week ;-); I'm hoping to see the overall solution come in in under 256 characters, which might be wishful thinking...)

---

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain