Jest to nieco proof-golf -jak policjantów i-rabusiów wyzwanie. To jest wątek gliniarzy; wątek złodziei jest tutaj.
Gliny
Twoim zadaniem jest zdefiniowanie abstrakcyjnego systemu przepisywania, w którym trudno jest ustalić dostępność jednego słowa od drugiego. Przygotujesz następujące rzeczy:
Zestaw symboli zwany alfabetem. (Możesz używać do nich dowolnych znaków Unicode, ale nie używaj białych znaków lub symboli, które trudno od siebie odróżnić).
Ciąg źródłowy składa się z symboli ze swoim alfabecie.
Ciąg docelowy złożony z symboli z twojego alfabetu.
Zestaw reguł przepisywania przy użyciu znaków z alfabetu. (Zobacz poniżej definicję reguły przepisywania).
Dowód pokazujący, czy łańcuch źródłowy może zostać przekształcony w łańcuch docelowy przez kolejne stosowanie reguł przepisywania. Dowód ten może składać się z rzeczywistej sekwencji kroków przepisywania lub matematycznego dowodu, że taka sekwencja musi istnieć, lub matematycznego dowodu, że taka sekwencja nie istnieje.
Opublikujesz pierwsze cztery z nich, zachowując dowód w tajemnicy; złodzieje spróbują złamać twoją odpowiedź, przedstawiając własny dowód, że łańcuch docelowy może lub nie może zostać osiągnięty z ciągu źródłowego. Jeśli zgłoszenie nie zostanie złamane w ciągu dwóch tygodni , możesz oznaczyć je jako bezpieczne i edytować w dowodzie.
Zgłoszenia będą oceniane według liczby znaków w regułach przepisywania oraz ciągów źródłowych i docelowych, jak wyszczególniono poniżej. Zwycięzcą zostanie zgłoszenie bez oceny z najniższą liczbą punktów.
Co to jest zasada przepisywania?
Reguła przepisywania to po prostu para ciągów w twoim alfabecie. (Każdy z tych ciągów może być pusty.) Zastosowanie reguły przepisywania polega na znalezieniu podłańcucha, który jest równy pierwszemu ciągowi w parze, i zastąpieniu go drugim.
Przykład powinien to wyjaśnić:
Załóżmy, że alfabet to A
, B
i C
; ciąg źródłowy to „ A
”; ciąg docelowy to „ C
”, a reguły przepisywania są
A:B
B:BB
B:A
AA:C
wtedy łańcuch docelowy jest osiągalny w następujący sposób:
A
B (using rule 1)
BB (using rule 2)
AB (using rule 3)
AA (using rule 3)
C (using rule 4)
Punktacja
Twój wynik będzie
- długość łańcucha źródłowego,
- plus długość docelowego ciągu,
- plus długość wszystkich ciągów zawartych w regułach przepisywania,
- plus jeden dodatkowy punkt za każdą regułę przepisywania.
Jeśli napiszesz swoje reguły przepisywania za pomocą separatora dwukropka, jak powyżej, jest to tylko całkowita długość wszystkich reguł przepisywania (w tym separatora) plus długości ciągów źródłowych i docelowych. Im niższy wynik, tym lepiej. Liczba różnych znaków w twoim alfabecie zostanie wykorzystana do zerwania więzi, przy czym mniej będzie lepszych.
Hojność
Chciałbym zobaczyć odpowiedzi, które naprawdę pasują do niskich wyników. Przydzielę 200 powtórzeń pierwszej odpowiedzi, która zdobędzie mniej niż 100 punktów w tym wyzwaniu i nie zostanie złamana.
Mx -> Mxx
regułę, więc skończyłoby się to znacznie bardziej skomplikowane niż Hofstadtera oryginalny.Odpowiedzi:
326 punktów - Cracked przez jimmy23013
Poziom to Picokosmos # 13 autorstwa Aymeric du Peloux (z trywialną modyfikacją). Próbowałem znaleźć gustowny poziom, który można wdrożyć z „pudełkami” i „ścianami” będącymi tą samą postacią. Dla tego poziomu było to możliwe dzięki temu, że środkowy punkt dławika miał szerokość dwóch kolumn zamiast jednej.
Ciągi reguł / początkowej / docelowej można nieco pograć w golfa, ale to tylko dla zabawy.
Początkowy ciąg:
Ciąg docelowy:
Zasady:
źródło
171 punktów, złamane przez HyperNeutrino
Źródło:
YAAAT
Cel:
VW626206555675126212043640270477001760465526277571600601
Zasady:
Po prostu coś oczywistego do zrobienia. Rzeczywista sekwencja kroków przepisywania prawdopodobnie nie zmieści się w odpowiedzi SE.
źródło
VWx
tam, gdziex
jest utworzony z dowolnego ciągu binarnego_
(0) i+
(1), które oceniają na10*n+6
(w tym wiodącą_
;n
= nieujemną liczbę całkowitą), alex
podana (626...601
) jest tworzona z binarnej, która ocenia do10*n+3
(dla dużegon
).33 punkty, złamane przez użytkownika71546
Prosty na początek.
Źródło:
xnor
Cel:
xor
Przepisz reguły:
Ostatnia reguła zabiera 11 znaków do pustego ciągu.
źródło
139 punktów (bezpieczny)
Chciałem, aby ta odpowiedź została złamana, a użytkownik202729 zasadniczo rozwiązał ją w komentarzach, ale nikt nie opublikował odpowiedzi w wątku złodziei, więc zaznaczam ją jako „bezpieczną” i podaję poniżej mój dowód.
(Te rzeczy są najwyraźniej dużo łatwiejsze do zrobienia niż do złamania. Nikt jednak nie próbował uzyskać naprawdę niskiego wyniku, a na tym końcu rzeczy może być więcej zabawy, jeśli wyzwanie to kiedykolwiek się rozpocznie. )
Oto odpowiedź własna. Jest to potencjalnie bardzo trudne, ale powinno być łatwe, jeśli zastanawiasz się, skąd się wzięło.
alfabet:
ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→
źródło:
←A→
cel:
←🎂→
Reguły: (białe znaki nie są znaczące)
Oto wersja ASCII , na wypadek, gdyby unicode nie wyświetlał się dobrze dla wszystkich.
Dowód
Jest to równoważne z obecnym najlepszym konkurentem dla bobra zajętego przez sześć stanów . Zajęty bóbr to maszyna Turinga, która zatrzymuje się po naprawdę długim czasie. Z tego powodu łańcuch źródłowy
←A→
może rzeczywiście zostać przekształcony w łańcuch docelowy←🎂→
, ale dopiero po więcej niż7*10^36534
krokach, co zajęłoby znacznie więcej niż wiek wszechświata dla jakiejkolwiek fizycznej implementacji.Taśma maszyny Turinga jest reprezentowana przez symbole
⬛
(0) i⚪
(1). Zasadyoznacza, że końce taśmy można zawsze przedłużyć o więcej zer. Jeśli głowa maszyny Turinga kiedykolwiek zbliży się do jednego końca taśmy, możemy po prostu zastosować jedną z tych reguł, co pozwala nam udawać, że taśma jest nieskończona i zaczyna się od wszystkich zer. (Symbole
→
i←
nigdy nie są tworzone ani niszczone, więc zawsze znajdują się na końcach taśmy.)Głowa maszyny Turinga jest reprezentowana symbolami
ABCDEⒶⒷⒸⒹⒺⒻ
i🎂
.A
oznacza, że głowa jest w stanie,A
a symbol pod głową to⬛
(0), podczas gdy Ⓐ oznacza, że jest w stanie,A
a symbol pod nią to⚪
(1). Jest to kontynuowane w przypadku innych stanów, z zakreśloną literą reprezentującą 1 pod głową, a nieokreśloną wersją reprezentującą 0. (Nie ma symbolu,F
ponieważ zdarza się, że głowa nigdy nie kończy się w stanieF
z 1 pod nią).Stan
🎂
jest stanem zatrzymania. Ma specjalne zasadyJeśli stan zatrzymania zostanie kiedykolwiek osiągnięty, możemy wielokrotnie stosować te reguły, aby „zassać” całą taśmę (w tym wszelkie dodatkowe zera powstałe w wyniku przedłużenia taśmy bardziej niż to konieczne), pozostawiając nas w tym stanie
←🎂→
. Dlatego problem osiągalności sprowadza się do tego, czy stan🎂
zostanie kiedykolwiek osiągnięty.Pozostałe zasady są zasadami przejścia dla maszyny Turinga. Na przykład reguły
można odczytać jako „jeśli maszyna znajduje się w stanie A, a pod głową jest zero, to napisz 1, zmień na stan B i przejdź w prawo”. Przesunięcie w prawo wymaga dwóch reguł, ponieważ komórka taśmy po prawej stronie może zawierać a
⬛
, w takim przypadku komputer powinien przejść do stanuB
, lub komórka może zawierać⚪
, w którym to przypadku powinna przejść do stanuⒷ
, ponieważ jest⚪
pod spodem.Podobnie,
oznacza „jeśli maszyna znajduje się w stanie D, a pod głową jest 1, to napisz 0, zmień na stan C i przesuń w lewo”.
Użyta maszyna Turinga została odkryta przez Pavla Kropitza w 2010 roku. Chociaż często jest wymieniana w kontekście zajętych bobrów, jej rzeczywista tabela przejścia jest nieco trudna do wyśledzenia, ale można ją znaleźć na przykład tutaj . Można to zapisać jako
co można odczytać jako „jeśli maszyna jest w stanie A, a pod głową jest zero, a następnie napisz 1, zmień na stan B i przejdź w prawo” i tak dalej. Sprawdzanie, czy każdy wpis w tej tabeli odpowiada parze zasad opisanych powyżej, powinno być proste, jeśli jest pracochłonne.
Jedynym wyjątkiem jest reguła,
1RH
która występuje, gdy maszyna znajduje się w stanie F powyżej 0, ponieważ wydawało się dość bezcelowe, aby maszyna zapisała 1 i przesunęła się w prawo, kiedy mogła natychmiast zatrzymać się, jak tylko wejdzie w stan F ponad 0. Więc zmieniłem regułę, która byłabyw
Dlatego
F
w alfabecie nie ma symbolu . (Jest kilka innych „golfów”, które mogłem zrobić, ale nie chciałem tego zbytnio zasłaniać.)Zasadniczo to jest to. Ciąg docelowy jest osiągalny z ciągu źródłowego, ale tylko po absurdalnej liczbie kroków.
Jeszcze jeden fajny fakt: gdybym użył
←A⚪⚪→
zamiast tego jako punkt wyjścia nie trzeba by było
7*10^36534
kroków, aby się zatrzymać, ale10^10^10^10^18705352
kroków, co w rzeczywistości jest bardzo dużą liczbą.źródło
48 punktów, złamane przez bb94
Alfabet:
abc
Źródło:
cbaabaabc
Cel:
cbacbcabc
Reguły przepisywania:
źródło
287 punktów, bezpieczny
Źródło:
YAAT
Cel:
Zasady:
Odkryłem, że w tym celu openssl jest znacznie łatwiejszy w użyciu niż gpg.
Zobacz crack HyperNeutrino do słabszej wersji. W takim przypadku liczba
C
s wynosi:A głównymi czynnikami są:
Pierwszy numer mod 5 = 2, więc można uzyskać ostatni ciąg.
źródło
402 punkty
Alfabet:
abcdefghijklmnopqrstu
Źródło:
abcdoi
Cel:
ioabcdnnnnnnnnnnnnnnnnnn
Reguły przepisywania:
Ostatnia reguła pozwala utworzyć tyle
n
s, ile potrzebujesz.Brzydkie, jak się wydaje, w rzeczywistości jest całkiem fajne, w ten czy inny sposób ...
źródło
aoi:eog
toeog
miało byćeag
?1337 punktów
Zdecydowanie nie był konkurencyjny i stworzenie go zajęło zbyt dużo czasu (mam nadzieję, że się nie pomyliłem).
Wskazówka:
Alfabet:
ABEILRSTabcdefijlr
Źródło:
SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE
Cel:
SE
Przepisz reguły:
źródło
154 punktów
Alfabet:
P.!xABC[{mD<
Źródło:
[x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm
(61 znaków)Cel:
{CCCCC<
(jest 5C
s, więc 7 znaków)Zasady:
Jest 19 zasad, łączna liczba znaków = 67.
źródło
106 punktów - złamane przez HyperNeutrino
Alfabet:
ABCDEFGHIJ
Źródło:
FIABCJAGJDEHHID
Cel:
F
Przepisać zasady:
Ok, HyperNeutrino udowodnił, że jest to nierozwiązywalne. Istnieje jednak inne rozwiązanie tego problemu.
Brać:
Wartość źródła jest parzysta. Wartość celu jest nieparzysta. Jeśli weźmiemy każdą stronę, zsumujemy wartość i zabierzemy wartość do mod 2, wartości pozostaną takie same. Dlatego nie można tego osiągnąć.
źródło