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 is
pojawia 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 dostdout
(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
, bbbbaaaacccc
i ccccbbbbaaaa
musi ś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
CooliO
, wyjścieoOoCli
?Mspiisiipss
ważny, ponieważ jedyne powtórzenieii
nie występujeMississippi
?Odpowiedzi:
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:
Benchmarki
Średni i maksymalny czas wykonania obliczony przy użyciu następującego kodu:
Wyniki:
* Zmieniłem,
ä
abya
uniknąć 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.
źródło
Dyalog APL (11 (5 + 10) = 165)
Dowód:
⍵
wystąpienie poza funkcją, która jest aSYNTAX ERROR
.b
, więc nie można jej zamienić na linie3
lub4
, które zależąb
. ByłobyVALUE ERROR
. (I oczywiście nie można go zamienić na jedno1
lub5
drugie.)c
, więc nie można jej zamienić na linię4
, która zależy odc
. (I już udowodniliśmy, że żadnej innej linii nie można zamienić na linię3
).źródło
APL (Dyalog), 6 (5 + 10) = 90
Korzystam z alternatywy, więc:
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łanieZamiana
Jeśli linia 1 zostanie zamieniona na linię 2, to skończy się
+/∘.≡⍨{...}
to bałaganem funkcji i operatorów, który dajeSYNTAX ERROR
.Jeśli linia 1 jest zamieniona na linię 3 lub 4, oznacza to, że masz
⍵
poza definicją funkcji i to jestSYNTAX 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ć do0
lub1
1-elementowej tablicy0
lub1
. Tutaj ocenia się na coś bardziej złożonego (skalar zawierający 2-elementową tablicę). Więc to jestDOMAIN 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 otrzymujeszSYNTAX ERROR
.Benchmarki
(liczby w milisekundach)
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.
źródło
Haskell, 129 = 3x (33 + 10)
używa to trybu alternatywnego.
lub w czytelnej formie:
Haskell jest bardzo surowym językiem. na przykład
import
musi być na pierwszym miejscu; definicjes
muszą 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
g
jest to prawidłowy funkcja ale ma niewłaściwy typ (dowolny typ różnych następnie[a]->[a]
alboString -> String
i tym podobne), niż jest to błąd krytyczny, ponieważ nie da się zastosowaćg
do wejść.wyjścia:
źródło