Write a routine that accepts a string of printable ASCII characters, s, and returns a string containing the same characters as s, reordered so that no two-character substring appears more than once. The program must process all benchmark strings (see below) in under one minute each on a modern computer. I will also award a special bonus of 50 rep to the lowest scoring answer that processes any valid 30-character string in under one minute.
For example, given the input
Mississippi, a valid output would be
issiMspiips (no two-character substrings appear twice), while an invalid output would be
ipMsispiiss (since the substring
is appears twice).
The routine may take the form of:
- a complete program reading from
stdin(or equivalent) or the command line, and outputting to
- a function accepting a single string argument and returning a string
You may assume that the input string always admits at least one valid output.
Your routine must comprise 5 or more lines of code separated by newlines. Empty lines (which includes lines containing only whitespace) are ignored in all contexts and do not count towards total line count.
Swapping any two lines in your source code must produce a fatal error. By "fatal error", we refer to any of the following conditions:
- the source code fails to compile, with the compiler/interpreter declaring a fatal error
- the routine aborts with a runtime fatal error or an unhandled runtime exception
- the routine is forced into an abrupt, abnormal program termination that produces no output of any kind except for a possible error message and/or stack dump
Alternatively, contiguous blocks of code containing no newline characters may be used in place of lines. These blocks should each be displayed on their own line in the source file, with the understanding that newlines are stripped out before the source code is compiled/interpreted.
For example, the code
aaaa bbbb cccc
would condense to
before being evaluated.
In this mode, the fatal error condition applies to swapping any two code blocks (and thus to swapping lines in the source code before newlines are stripped out). Hence in the above example the routines
ccccbbbbaaaa must all produce fatal errors, either at compiletime or runtime.
Submissions using this alternative mode should declare its use.
Let n be the number of non-empty textlines in your source file, with n ≥ 5. Let c be the number of bytes comprised by the longest textline (by byte length) in your source file, not counting any trailing newline.
A submission's score is given by c(n + 10).
The submission with the lowest score is the winner.
Best of luck. ;)
Abracadabra Alacazam Is Miss. Mississauga Missing? Ask Alaska's Alaskans GGGGAAAATTTTCCCCgggaaatttccc A Man A Plan A Canal Panama
Mspiisiipssvalid since the only repetition is
iiwhich does not occur in