The Fatal Error Challenge 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 to stdout (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 &geq; 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
PHP, score = 289 (17×(7+10))

PHP's built-in functions make it quite easy to do this badly. The following code just shuffles the string until a valid result is obtained:

function f($s){
while(preg_match(
'/(..).*?\1/',$s)
+preg_match('/(.'
.')\1\1/',$s))$s=
str_shuffle(
$s);return $s;}




Benchmarks

Average and maximum execution times calculated using the following code:

$s = 'Mississippi';
$t_total = 0;
$t_max = 0;
for ($i=0; $i&lt;10; $i++) {
  $t0 = microtime(true);
  echo f($s);
  $t = microtime(true) - $t0;
  printf("  %10.7f\n",$t);
  $t_total += $t;
  if ($t &gt; $t_max) $t_max = $t;
}
printf("Avg: %10.7f secs; Max: %10.7f secs\n",$t_total/$i, $t_max);


Results:


Mississippi: Avg:  0.0002460 secs; Max:  0.0005491 secs
Anticonstitutionnellement: Avg:  0.0001470 secs; Max:  0.0002971 secs
Pneumonoultramicroscopicsilicovolcanoconiosis: Avg:  0.0587177 secs; Max:  0.1668079 secs
Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft*: Avg:  9.5642390 secs; Max: 34.9904099 secs
baaacadaeafbbcbdbebfccdcecfdde†: Avg:  5.0858626 secs; Max:  9.8927171 secs


* I changed ä to a to avoid multi-byte issues
† This was the hardest 30-character string I could come up with. It's actually the first 30 characters of the De Bruijn sequence for k='abcdef' and n=2, with the first 'b' moved to avoid an instant match.