PROBLEM STATEMENT
There is the concept of a one-dimensional structure (a line), a two-dimensional
structure with right angles (a rectangle), a three-dimensional structure with
right angles (a rectangular prism), and the list goes on, but four-dimensional
and higher structures are usually not comprehensible and are hence not discussed.
They can, however, be made use of in cryptography. By arranging the letters of
a message into a multi-dimensional structure and reading them back off after
switching around the order of the dimensions, the message becomes scrambled,
and without the correct key, is undecipherable. (not really, just for the
purposes of this problem :-).
For example, the text "thequickbrownfoxes" has 18 letters, and fits nicely into
an 2x3x3 box of letters, with coordinates from (0,0,0) to (1,2,2). Starting at
0,0,0, we put the letter 't', and then 'h' goes at 0,0,1, 'e' goes at 0,0,2,
and 'q' goes at 0,1,0, etc.
When done, we have:
Layer 0 Layer 1
the row
qui nfo
ckb xes
Now, if we read them back off with the dimensions in the same order, we of
course get the original string. However, if we change the order of the
dimensions so that they are backwards, we start at (0,0,0) next is (1,0,0) then
(0,1,0), and (1,1,0), etc. Reading them of in this fashion, we obtain the string:
"trqncxhoufkeewiobs"
We can label the correct ordering as a sequence "012", where the highest number
increments first, and when it rolls over, the next digit corresponding to the
next lowest number in the translation increments. The backwards translation
just done would be labeled as "210".
Alternatively, we could use translations labeled "021", "102", "120", or "201".
Using only dimensions of 2 and 3, it is possible to obtain a relatively close
approximation to the size of the message. For instance, a message of length 14
fits well in a 2x2x2x2 box. If the message does not fit perfectly, it is padded
with any letter. For example, "helloworld", of length 10, fits best into a
2x2x3 box, so any two letters would be appended to it, yielding "helloworld--",
where '-' is any letter, number or a space. Note that you must always use a box
of the smallest possible size that will still fit. For instance, a String of
length 17 requires 2x3x3 = 18, and 2x2x2x3 = 24 is not allowed, since it is not
the smallest possible fit. Also note that as necessary, a box can have 1, 2, 3,
4, or 5 dimensions.
In order to make things just slightly more interesting, the length of the
scrambled message may be longer than the initial message. In this situation,
the dimensions of the box are determined by the length of the scrambled
message. For instance, given:
unscramble("short","this is a longer string"), "short" fits best into a 2x3
box, but "this is a longer string"
fits best into a 2x2x2x3 box, and thus the 2x2x2x3 size must be used.
When giving dimensions of a box, note that numbers are always given in
increasing order. That is, a 3x2 box is not allowable, but 2x3 is.
DEFINITION
Class name: Crypto
Method name: unscramble
Parameters: String, String
Returns: String[]
The method signature (make sure it is declared public) is:
String[] unscramble(String initial, String scrambled);
Given the initial and scrambled Strings, determine which (if any) of the
possible translations could have been used to scramble the String. Strings are
case-sensitive.
If multiple translations exist, return them all in lexicographical order. If no
possible translations exist, return a String[] of size 0.
If either initial or scrambled will not fit exactly into a box with dimensions
of only 2 and 3, they should be treated as though they are of the smallest
length which will fit, by padding them on the end with wildcards.
After unscrambling a String, to determine if they match or not, use the
following criterion. Wildcards in the initial word can match anything in the
same index in the scrambled word. Wildcards in the scrambled word can only
match wildcards in the same index in the inital word. Letters only match the
same letter in the same index in the other word.
In the following example, the 'h', 'e', and first 'l' match, since they are the
same in both words.
The second 'l' does not match, since it is a wildcard ('-') in the second word.
The 'o' does not match, since it is not the same in either word.
The '-' does match, since it is a wildcard in the first word and an 'o' in the
second.
"hello-"
"hel-lo"
TopCoder will enforce the following restrictions:
* initial and scrambled will be between 2 and 50 characters in length
* the length of initial will be less than or equal to the length of scrambled
* initial and scrambled will contain only letters (A-Z,a-z), digits (0-9,
inclusive), and spaces
Example:
unscramble("hello", "hleolo")
"hleolo" has length 6, and fits best into a 2x3 box, and thus we arrange
"hello-" into a 2x3 box.
We have two dimensions that we can rearrange, so we have two translations: "01"
and "10".
"01" is the initial case, which of course yields "hello-".
The other case, "10", yields "hleol-".
Since the '-' can be anything, the scrambled string matches "10".
Thus, the method returns {"10"}.
unscramble("goodbye cruel world","grdobooueudloe ru dlwlo b eybdyw wyeeoleuc
rwlodcl")
returns: {"2301"}.
unscramble("aaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaabaaaaaa")
returns: {"0213", "0312", "0321", "2013", "3012", "3021"}.