Permutation
-----------
Given two equal length strings of upper case letters,
find a permutation that maps the first string to the
second string.
Input
-----
For each of several test cases, first a line that gives
the test case name, and then two lines each containing
one of the two strings. All lines are at most 80 char-
acters long. Input ends with an end of file.
Output
------
For each test case, first an exact copy of the test case
name line. Then N lines where N is the common length of
the input strings. Each of the N lines has the form:
L: I -> J
where L is a letter that is in position I in the first
string and position J in the second string. Positions
are numbered 1, 2, ..., N. Each position must appear
EXACTLY ONCE as I on the N lines, and also exactly once
as J in the N lines, so that the N lines define a
permutation (i.e., a 1-1 map).
If this is not possible, output a single line contain-
ing just the word `impossible' in lower case letters,
in place of the N lines.
For example, if the input is: ABC
ABA
the output: A: 1 -> 1
B: 2 -> 2
A: 1 -> 3
is incorrect because 3 does not appear as I in any of
the 3 lines, and also because 1 appears as I more than
once. In fact, as the second string has more A's than
the first string, there are no permutations that map
the first string to the second string, and the correct
answer is `impossible'.
There may be more than one correct solution. If so,
give only one solution.
Sample Input
------ -----
-- SAMPLE 1 --
ABC
CBA
-- SAMPLE 2 --
ABC
ABA
-- SAMPLE 3 --
ABCDEFG
GFEDCBA
-- SAMPLE 4 --
ABABAB
BBBAAA
-- SAMPLE 5 --
ABABAB
BBBAAC
[see sample.in for more sample input]
Sample Output
------ ------
-- SAMPLE 1 --
A: 1 -> 3
B: 2 -> 2
C: 3 -> 1
-- SAMPLE 2 --
impossible
-- SAMPLE 3 --
A: 1 -> 7
B: 2 -> 6
C: 3 -> 5
D: 4 -> 4
E: 5 -> 3
F: 6 -> 2
G: 7 -> 1
-- SAMPLE 4 --
A: 1 -> 4
B: 2 -> 1
A: 3 -> 5
B: 4 -> 2
A: 5 -> 6
B: 6 -> 3
-- SAMPLE 5 --
impossible
[see sample.test for more sample output]
File: permutation.txt
Author: Shai Simonson
Editor: Bob Walton
Date: Fri Oct 5 21:35:32 EDT 2018
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.