Objective
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 tostdout
(or equivalent) - 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.
The Challenge
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
aaaabbbbcccc
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 aaaaccccbbbb
, bbbbaaaacccc
, and ccccbbbbaaaa
must all produce fatal errors, either at compiletime or runtime.
Submissions using this alternative mode should declare its use.
Scoring
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. ;)
Benchmark Strings
Abracadabra Alacazam
Is Miss. Mississauga Missing?
Ask Alaska's Alaskans
GGGGAAAATTTTCCCCgggaaatttccc
A Man A Plan A Canal Panama
CooliO
, outputoOoCli
? \$\endgroup\$Mspiisiipss
valid since the only repetition isii
which does not occur inMississippi
? \$\endgroup\$