Cel

Napisz procedurę, która akceptuje ciąg drukowalnych znaków ASCII, s , i zwraca ciąg zawierający te same znaki, co s , uporządkowany w taki sposób, aby nie składał się z dwóch znaków więcej niż jeden raz. Program musi przetworzyć wszystkie ciągi testów porównawczych (patrz poniżej) w niecałą minutę na każdym nowoczesnym komputerze . Przyznam również specjalną premię 50 powtórzeń do odpowiedzi o najniższym wyniku, która przetwarza dowolny prawidłowy ciąg 30 znaków w mniej niż minutę.

Na przykład, biorąc pod uwagę dane wejściowe Mississippi, poprawne dane wyjściowe to issiMspiips(żadne podciągi dwuznakowe nie pojawią się dwa razy), podczas gdy nieprawidłowe dane wyjściowe to ipMsispiiss(ponieważ podłańcuch ispojawia się dwa razy).

Procedura może przybrać postać:

• pełny program odczytujący z stdin(lub równoważny) lub z wiersza poleceń i wysyłający do stdout(lub równoważny)
• funkcja przyjmująca pojedynczy argument ciągu i zwracająca ciąg

Możesz założyć, że ciąg wejściowy zawsze dopuszcza co najmniej jedno prawidłowe wyjście.

Wyzwanie

Procedura musi zawierać 5 lub więcej wierszy kodu oddzielonych znakami nowej linii. Puste linie (w tym linie zawierające tylko białe znaki) są ignorowane we wszystkich kontekstach i nie liczą się do całkowitej liczby linii.

Zamiana dowolnych dwóch wierszy w kodzie źródłowym musi powodować błąd krytyczny. Przez „błąd krytyczny” odnosimy się do dowolnego z następujących warunków:

• kod źródłowy nie kompiluje się, a kompilator / interpreter deklaruje błąd krytyczny
• procedura przerywa się z błędem krytycznym środowiska wykonawczego lub nieobsługiwanym wyjątkiem środowiska uruchomieniowego
• procedura jest zmuszana do nagłego, nienormalnego zakończenia programu, które nie generuje żadnego wyjścia, z wyjątkiem możliwego komunikatu o błędzie i / lub zrzutu stosu

Alternatywnie , zamiast wierszy można zastosować ciągłe bloki kodu nie zawierające znaków nowej linii. Te bloki powinny być wyświetlane w osobnych wierszach w pliku źródłowym, przy założeniu, że znaki nowej linii są usuwane przed skompilowaniem / interpretacją kodu źródłowego.

Na przykład kod

aaaa
bbbb
cccc

skropliłbym się

aaaabbbbcccc

przed oceną.

W tym trybie warunek krytyczny błędu dotyczy zamiany dowolnych dwóch bloków kodu (a zatem zamiany wierszy w kodzie źródłowym przed usunięciem nowych linii). Tak więc, w powyższym przykładzie Procedury aaaaccccbbbb, bbbbaaaacccci ccccbbbbaaaamusi śmiertelnych błędów produktu, bądź na compiletime lub starcie.

Zgłoszenia korzystające z tego alternatywnego trybu powinny deklarować jego użycie.

Punktacja

Niech n będzie liczbą niepustych linii tekstowych w pliku źródłowym, gdzie n ≥ 5. Niech c będzie liczbą bajtów złożoną z najdłuższej linii tekstowej (w bajtach długości) w pliku źródłowym, nie licząc żadnej nowej linii.

Punktacja podana jest przez c ( n + 10).

Zgłoszenie o najniższym wyniku jest zwycięzcą.

Powodzenia. ;)

Ciągi wzorcowe

Abracadabra Alacazam
Is Miss. Mississauga Missing?
Ask Alaska's Alaskans
GGGGAAAATTTTCCCCgggaaatttccc
A Man A Plan A Canal Panama

PHP, wynik = 289 (17 × (7 + 10))

Wbudowane funkcje PHP ułatwiają to źle. Poniższy kod po prostu tasuje ciąg znaków, aż do uzyskania prawidłowego wyniku:

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

Benchmarki

Średni i maksymalny czas wykonania obliczony przy użyciu następującego kodu:

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

Wyniki:

• Missisipi: Średnio: 0,0002460 s; Maks .: 0,0005491 sek
• Anticonstitutionnellement: Śr .: 0,0001470 s; Maks .: 0,0002971 sek
• Pneumonoultramicroscopicsilicovolcanoconiosis: Śr .: 0,0587177 s; Maks .: 0,1668079 sek
• Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft ^* : Avg: 9.5642390 secs; Maks .: 34,9904099 sek
• baaacadaeafbbcbdbebfccdcecfdde ^† : Avg: 5.0858626 secs; Maks .: 9,8927171 sek

^{* Zmieniłem, äaby auniknąć problemów z wieloma bajtami
† To był najtrudniejszy ciąg 30 znaków, jaki mogłem wymyślić. To właściwie pierwsze 30 znaków w sekwencji De Bruijn dla k = „abcdef” i n = 2, przy czym pierwsze „b” jest przesunięte, aby uniknąć natychmiastowego dopasowania.}

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

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

Dowód:

• Linie 1 i 5 ograniczają funkcję. Zamiana dowolnej linii na te spowodowałaby ⍵wystąpienie poza funkcją, która jest a SYNTAX ERROR.
• Linia 2 określa b, więc nie można jej zamienić na linie 3lub 4, które zależą b. Byłoby VALUE ERROR. (I oczywiście nie można go zamienić na jedno 1lub 5drugie.)
• Linia 3 określa c, więc nie można jej zamienić na linię 4, która zależy od c. (I już udowodniliśmy, że żadnej innej linii nie można zamienić na linię 3).
• Wiersz 4 zależy od zmiennych z wiersza 2 i 3 i dlatego musi być ostatni.

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

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

Korzystam z alternatywy, więc:

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

To jest ten sam stary algorytm.

Wyjaśnienie
2,/⍵ daje tablicę par znaków w ciągu wejściowym
+/∘.≡⍨generuje tablicę liczbową określającą, ile par jest równych każdej parze (w tym samej),
1∧.=sprawdza, czy każdy element tej tablicy jest równy 1, i logiczne ORAZ wyniki razem

:⍵Jeśli to prawda ( 1), zwróć ciąg wejściowy

∇⍵[?⍨⍴⍵] w przeciwnym razie wymieszaj łańcuch wejściowy i wykonaj rekurencyjne wywołanie

Zamiana

Jeśli linia 1 zostanie zamieniona na linię 2, to skończy się +/∘.≡⍨{...}to bałaganem funkcji i operatorów, który daje SYNTAX ERROR.
Jeśli linia 1 jest zamieniona na linię 3 lub 4, oznacza to, że masz ⍵poza definicją funkcji i to jest SYNTAX ERROR.
Jeśli linia 1 zostanie zamieniona na linię 5, spowodowałoby to niezbalansowane same nawiasy klamrowe SYNTAX ERROR, więc nie martw się o pozostałe 4 błędy składniowe.

Jeśli linia 5 zostanie zamieniona na linię 2/3/4, znowu masz ⍵poza definicją funkcji. ( SYNTAX ERROR)

Jeśli linia 2 zostanie zamieniona na linię 3, skończysz na 1∧.=2,/⍵:⍵. Ta składnia nazywa się strażnikiem (traktuj ją jako warunkową). Warunek ochronny musi oceniać do 0lub 11-elementowej tablicy 0lub 1. Tutaj ocenia się na coś bardziej złożonego (skalar zawierający 2-elementową tablicę). Więc to jest DOMAIN ERROR.
Jeśli wiersz 2 zostanie zamieniony na wiersz 4, otrzymasz instrukcję 1∧.=, która próbuje zastosować funkcję ∧.=bez wymaganego lewego argumentu. ( SYNTAX ERROR).

Jeśli linia 3 zostanie zamieniona na linię 4, znowu pojawi się bałagan funkcji i operatorów ( 1∧.=+/∘.≡⍨), więc otrzymujesz SYNTAX ERROR.

Benchmarki
(liczby w milisekundach)

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

Nadal myślę o różnych podziałach. Mam też deterministyczny, systematyczny sposób wykonywania tego zadania. Po prostu nie mogę przekształcić go w algorytm (zabrać kreatywną część „poprawiania liczb”) i nie mogę się upewnić, że zadziała za każdym razem.

Haskell, 129 = 3x (33 + 10)

używa to trybu alternatywnego.

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

lub w czytelnej formie:

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 jest bardzo surowym językiem. na przykład importmusi być na pierwszym miejscu; definicje smuszą się łączyć; wszystkie typy muszą się zgodzić i nie ma sposobu, aby między nimi rzucić i tak dalej. prowadzi to do błędu, który nie jest krytyczny, prawie niemożliwy. w rzeczywistości błąd krytyczny środowiska wykonawczego jest prawie prawie niemożliwy.

Zauważ, że jeśli gjest to prawidłowy funkcja ale ma niewłaściwy typ (dowolny typ różnych następnie [a]->[a]albo String -> Stringi tym podobne), niż jest to błąd krytyczny, ponieważ nie da się zastosować gdo wejść.

wyjścia:

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