Given a string containing a random sequence of unique characters A to Z (all upper case, no duplicates), determine the cut-and-paste" sort and output the sort sequence to a specific format (detailed below).
Definition of Cut-And-Paste Sort, by Example
This string contains 11 characters, of which
I form the longest "lengthy sequence" from left to right that is in alphabetic order. So we base the cut-and-paste around these key letters.
If there is more than one "lengthy sequence" of equal length, the code will always favor the lengthy sequence with the biggest "stretch" across the entire string.
In the case of a slightly different string than our original example,
AKGHJCFDEBI, there are three lengthy sequences of
AGHI, but the code will favor the sequence with the greatest stretch, which in this case is
AGHI because the distance between
I is greatest amongst the three as opposed to the
E in the first sequence and the
J in the second sequence. If there happens to be more than one lengthy sequence with the same stretch length, the first lengthy sequence in alphabetic order will be chosen, just to make it easy.
The cut-and-paste sort is simply a case of plucking the appropriate letters not within the key letters and placing them back in their respective positions in alphabetic order.
Then the sort from our original example would occur as follows:
Step 1: AKJCFEGHDBI Step 2: ABKJCFEGHDI (B gets cut and takes 8 steps to the left and gets pasted after A) Step 3: ABKJCDFEGHI (D gets cut and takes 4 steps to the left and gets pasted after C) Step 4: ABKJCDEFGHI (F gets cut and takes 1 step to the right and gets pasted after E) Step 5: ABKCDEFGHIJ (J gets cut and takes 7 steps to the right and gets pasted after I) Step 6: ABCDEFGHIJK (K gets cut and takes 8 steps to the right and gets pasted after J)
To make it easier for the purpose of this challenge we can rewrite this sort as:
where each letter represents the letter being cut, followed by a series of left or right arrows, represented by the
> characters. When the arrows end, it is implied that the letter is pasted.
Bear in mind that the number of letters being cut at any one time can be more than one, so long as the letters are sequential. So if there is a string that can have two or more letters cut at any one time, the code should favor using the larger rather than perform two or more individual cut-and-pastes as this will provide a more efficient cut-paste sort.
AKGHJCFDEBI Lengthy sequences: ACDE AGHJ AGHI; AGHI is chosen (longest stretch) Step 1: AKGHJCFDEBI Step 2: ABKGHJCFDEI (B<<<<<<<<) Step 3: ABCKGHJFDEI (C<<<<) Step 4: ABCDEKGHJFI (DE<<<<<) Note two or more letters can be moved as long as they are side-by-side Step 5: ABCDEFKGHJI (F<<<<) Step 6: ABCDEFKGHIJ (J>) Step 7: ABCDEFGHIJK (K>>>>) End result: B<<<<<<<<C<<<<DE<<<<<F<<<<J>K>>>>
The code must take an alphabetic upper case string with unique letters (Please assume that this string will always be upper case and with all unique letters, i.e. no dupliates), and perform a cut-paste sort according to the above rules and provide a formatted string simliar to
B<<<<<<<<C<<<<DE<<<<<F<<<<J>K>>>> providing the method of cutting and pasting respective letters to achieve a string in alphabetic order.
Result: (already sorted)
- Code Golf: Shortest code wins...
- Code must be in the form of a piece of STDIN/STDOUT code, or a function taking the input string as a parameter and returning the output string
- Code must be suported by a working version of the code or verified execution of test cases.
- In the event that there are two or more with the same character count, the winner will be chosen by the most upvotes.
- No silly loopholes