Zielsetzung

Schreiben Sie eine Routine, die eine Zeichenfolge aus druckbaren ASCII-Zeichen ( s) akzeptiert und eine Zeichenfolge mit denselben Zeichen wie ( s) zurückgibt , die neu angeordnet wurde, sodass keine Teilzeichenfolge mit zwei Zeichen mehr als einmal vorkommt. Das Programm muss alle Benchmark-Zeichenfolgen (siehe unten) in jeweils weniger als einer Minute auf einem modernen Computer verarbeiten . Ich werde auch einen besonderen Bonus von 50 Wiederholungen für die Antwort mit der niedrigsten Punktzahl vergeben, die eine gültige 30-Zeichen-Zeichenfolge in weniger als einer Minute verarbeitet.

Bei einer gegebenen Eingabe Mississippiwäre dies beispielsweise eine gültige Ausgabe issiMspiips(es werden keine Teilzeichenfolgen mit zwei Zeichen zweimal angezeigt ), während dies eine ungültige Ausgabe wäre ipMsispiiss(da die Teilzeichenfolge iszweimal angezeigt wird).

Die Routine kann die Form haben:

• ein vollständiges Programm, das von stdin(oder einer gleichwertigen) oder der Befehlszeile gelesen und an stdout(oder einer gleichwertigen) Stelle ausgegeben wird
• Eine Funktion, die ein einzelnes Zeichenfolgenargument akzeptiert und eine Zeichenfolge zurückgibt

Sie können davon ausgehen, dass die Eingabezeichenfolge immer mindestens eine gültige Ausgabe zulässt.

Die Herausforderung

Ihre Routine muss 5 oder mehr Codezeilen enthalten, die durch Zeilenumbrüche voneinander getrennt sind. Leere Zeilen (einschließlich Zeilen, die nur Leerzeichen enthalten) werden in allen Kontexten ignoriert und zählen nicht zur Gesamtanzahl der Zeilen.

Das Vertauschen von zwei beliebigen Zeilen in Ihrem Quellcode muss einen schwerwiegenden Fehler verursachen. Mit "schwerwiegender Fehler" wird auf eine der folgenden Bedingungen verwiesen:

• Der Quellcode kann nicht kompiliert werden, und der Compiler / Interpreter meldet einen schwerwiegenden Fehler
• Die Routine wird mit einem schwerwiegenden Laufzeitfehler oder einer nicht behandelten Laufzeitausnahme abgebrochen
• Die Routine wird zu einem abrupten, abnormalen Programmabbruch gezwungen, der bis auf eine mögliche Fehlermeldung und / oder einen Stapelspeicherauszug keinerlei Ausgabe erzeugt

Alternativ können zusammenhängende Codeblöcke, die keine Zeilenumbrüche enthalten, anstelle von Zeilen verwendet werden. Diese Blöcke sollten in der Quelldatei jeweils in einer eigenen Zeile angezeigt werden, mit der Maßgabe, dass Zeilenumbrüche entfernt werden, bevor der Quellcode kompiliert / interpretiert wird.

Zum Beispiel der Code

aaaa
bbbb
cccc

würde kondensieren

aaaabbbbcccc

bevor sie ausgewertet werden.

In diesem Modus gilt die schwerwiegende Fehlerbedingung für das Austauschen von zwei Codeblöcken (und damit für das Austauschen von Zeilen im Quellcode, bevor Zeilenumbrüche entfernt werden). Daher wird in dem obigen Beispiel die Routinen aaaaccccbbbb, bbbbaaaaccccund ccccbbbbaaaamüssen alle fatalen Fehler produzieren, entweder in compiletime oder Laufzeit.

Bei Einsendungen, die diesen alternativen Modus verwenden, muss die Verwendung deklariert werden.

Wertung

Sei n die Anzahl der nicht leeren Textzeilen in Ihrer Quelldatei, mit n ≥ 5. Sei c die Anzahl der Bytes, die die längste Textzeile (nach Bytelänge) in Ihrer Quelldatei enthält, ohne nachfolgende Zeilenumbrüche.

Die Punktzahl einer Einreichung ergibt sich aus c ( n + 10).

Die Einsendung mit der niedrigsten Punktzahl ist der Gewinner.

Viel Glück. ;)

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))

Die eingebauten Funktionen von PHP machen es ziemlich einfach, dies schlecht zu machen. Der folgende Code mischt die Zeichenfolge nur, bis ein gültiges Ergebnis erhalten wird:

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

Benchmarks

Durchschnittliche und maximale Ausführungszeit berechnet mit folgendem Code:

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

Ergebnisse:

• Mississippi: Durchschnitt: 0,0002460 Sekunden; Max: 0,0005491 Sek
• Antikonstitutionsverzögerung: Durchschnitt: 0,0001470 Sekunden; Max: 0,0002971 Sek
• Pneumonoultramicroscopicsilicovolcanoconiosis: Avg: 0.0587177 secs; Max: 0,1668079 Sek
• Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft ^* : Avg: 9.5642390 secs; Max: 34.9904099 Sek
• baaacadaeafbbcbdbebfccdcecfdde ^† : Avg: 5,0858626 secs; Max: 9,8927171 Sek

^{* Ich habe zu geändert ä, aum Multibyte-Probleme zu vermeiden
. Es sind tatsächlich die ersten 30 Zeichen der De Bruijn-Sequenz für k = 'abcdef' und n = 2, wobei das erste 'b' verschoben wird, um eine sofortige Übereinstimmung zu vermeiden.}

Dyalog APL (11 (5 + 10) = 165)

f←{a←{⍴⍵}
b←a⌸2,/⍵
c←b⊢⍵[?⍨a⍵]
1∨.≠b:∇c⋄⍵
}

Beweis:

• Die Zeilen 1 und 5 begrenzen die Funktion. Das Vertauschen einer Zeile gegen eine andere würde dazu führen ⍵, dass eine Funktion außerhalb von a auftritt SYNTAX ERROR.
• Zeile 2 ist definiert b, kann also nicht gegen Zeilen ausgetauscht werden3 oder4 , die davon abhängen b. Es würde eine geben VALUE ERROR. (Und es kann natürlich nicht mit 1oder ausgetauscht 5werden.)
• Zeile 3 definiert c , kann also nicht gegen Zeile ausgetauscht werden 4, was von abhängt c. (Und wir haben bereits bewiesen, dass keine andere Leitung mit der Leitung ausgetauscht werden kann 3.)
• Zeile 4 hängt von den Variablen aus den Zeilen 2 und 3 ab und muss daher die letzte sein.

APL (Dyalog), 6 (5 + 10) = 90

{1∧.=
+/∘.≡⍨
2,/⍵:⍵
⋄∇⍵[
?⍨⍴⍵]}

Ich benutze die Alternative, also:

{1∧.=+/∘.≡⍨2,/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Dies ist derselbe alte Algorithmus.

Durch die Angabe
2,/⍵ eines Arrays von Zeichenpaaren in der Eingabezeichenfolge
+/∘.≡⍨wird ein numerisches Array der Anzahl der Paare generiert, die für jedes Paar gleich sind (einschließlich sich selbst).
1∧.= geprüft, ob jedes Element dieses Arrays gleich 1 ist, und die Ergebnisse werden logisch UND verknüpft

:⍵ Wenn das stimmt (1 ), geben Sie die Eingabezeichenfolge zurück

∇⍵[?⍨⍴⍵] sonst verschlüsseln Sie die Eingabezeichenfolge und führen Sie einen rekursiven Aufruf durch

Tauschen

Wenn Zeile 1 gegen Zeile 2 ausgetauscht wird, +/∘.≡⍨{...}ist das nur ein Durcheinander von Funktionen und Operatoren SYNTAX ERROR.
Wenn Zeile 1 mit Zeile 3 oder 4 vertauscht wird, haben Sie ⍵außerhalb einer Funktionsdefinition, und das ist ein SYNTAX ERROR.
Wenn Zeile 1 gegen Zeile 5 ausgetauscht wird, führt dies allein zu unsymmetrischen Klammern. Machen Sie sich SYNTAX ERRORalso keine Gedanken über die anderen 4 Syntaxfehler.

Wenn Zeile 5 mit Zeile 2/3/4 getauscht wird, haben Sie wieder ⍵außerhalb einer Funktionsdefinition. ( SYNTAX ERROR)

Wenn Zeile 2 gegen Zeile 3 ausgetauscht wird, erhalten Sie 1∧.=2,/⍵:⍵. Diese Syntax wird als Guard bezeichnet (man denke an eine Bedingung). Die Guard-Bedingung muss als 0oder 1oder als 1-Element-Array von 0oder ausgewertet werden 1. Hier ergibt sich eine komplexere Bewertung (ein Skalar mit einem Array aus zwei Elementen). Das ist also ein DOMAIN ERROR.
Wenn Zeile 2 gegen Zeile 4 ausgetauscht wird, erhalten Sie die Anweisung 1∧.=, die versucht, die Funktion anzuwenden∧.= ohne das erforderliche linke Argument . ( SYNTAX ERROR).

Wenn Zeile 3 gegen Zeile 4 ausgetauscht wird, erhalten Sie wieder eine Unordnung von Funktionen und Operatoren ( 1∧.=+/∘.≡⍨) SYNTAX ERROR.

Benchmarks
(Zahlen in Millisekunden)

Abracadabra Alacazam
11 1 3 5 2
Avg: 4.4

Is Miss. Mississauga Missing?
1260 2000 222 117 111
Avg: 742

Ask Alaska's Alaskans
7 2 3 3 4
Avg: 3.8

GGGGAAAATTTTCCCCgggaaatttccc
31 15 24 13 11
Avg: 18.8

A Man A Plan A Canal Panama
377 2562 23 301 49
Avg: 662.4

Ich denke immer noch über verschiedene Spaltungen nach. Ich habe auch eine deterministische, systematische Art, die Aufgabe zu erledigen. Ich kann es einfach nicht in einen Algorithmus verwandeln (den kreativen Teil von "Zahlen richtig machen" entfernen) und kann nicht sicherstellen, dass es jedes Mal funktioniert.

Haskell, 129 = 3x (33 + 10)

Dies verwendet den alternativen Modus.

imp
ort
 Da
ta.
Lis
t;a
%[]
=[[
]];
a%s
=[x
:j|
x<-
s,n
ot$
isI
nfi
xOf
[la
st 
a,x
]a,
j<-
(a+
+[x
])%
(s\
\[x
])]
;g 
s=[
]%s
!!0

oder in lesbarer Form:

import Data.List
a%[]=[[]]
a%s=[x:j|x<-s,not$isInfixOf[last a,x]a,j<-(a++[x])%(s\\[x])]
g s=[]%s!!0

Haskell ist eine sehr strenge Sprache. Zum Beispiel importmuss das zuerst kommen. die Definitionen vons müssen zusammenkommen; Alle Typen müssen übereinstimmen, und es gibt keine Möglichkeit, zwischen ihnen zu wechseln, und so weiter. Dies führt dazu, dass ein nicht schwerwiegender Fehler fast unmöglich ist. Tatsächlich ist es fast unmöglich, einen schwerwiegenden Laufzeitfehler zu haben.

Beachten Sie, dass if geine gültige Funktion ist, aber einen falschen Typ hat (jeder andere Typ [a]->[a]oder String -> Stringähnliches), als dies ein schwerwiegender Fehler ist, da es unmöglich ist, ihn anzuwendeng auf die Eingänge.

Ausgänge:

Abracadabar Alaazcma
Is Miss. iMsiasusgsa sMniig?s
Ask Alasak's lAaankss
GGAGTGCAATACTTCCggagtaacttcc
A Man AP la nAC  aalnnaPama