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:

1. 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ć).

2. Ciąg źródłowy składa się z symboli ze swoim alfabecie.

3. Ciąg docelowy złożony z symboli z twojego alfabetu.

4. Zestaw reguł przepisywania przy użyciu znaków z alfabetu. (Zobacz poniżej definicję reguły przepisywania).

5. 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, Bi 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.

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:

_wW:!
_<:<_
Vv_:!
V_:_V
R:>>>>>>>>>>>>>
V#:#V
#w<:w#
>v_:_v
_wX:#
_!:!_
!:wLW_
L:<<<<<<<<<<<<<
#W:W#
!#_:_!#
_w<:w_
#<:<#
!:_VRv
>v#:#v
Uv_:#
_W:W_
_X:X_
>#:#>
#X:X#
U_:_U
Vv#:!URv
#wW:wLX!
>_:_>
!_:_!
_#!:#!_
U#:#U

171 punktów, złamane przez HyperNeutrino

Źródło: YAAAT

Cel: VW626206555675126212043640270477001760465526277571600601

Zasady:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Po prostu coś oczywistego do zrobienia. Rzeczywista sekwencja kroków przepisywania prawdopodobnie nie zmieści się w odpowiedzi SE.

33 punkty, złamane przez użytkownika71546

Prosty na początek.

Źródło: xnor
Cel: xor
Przepisz reguły:

x:xn
no:oon
nr:r
ooooooooooo:

Ostatnia reguła zabiera 11 znaków do pustego ciągu.

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)

← : ←⬛
→ : ⬛→
A⬛ : ⚪B
A⚪ : ⚪Ⓑ
⬛Ⓐ : E⚪
⚪Ⓐ : Ⓔ⚪
B⬛ : ⚪C
B⚪ : ⚪Ⓒ
Ⓑ⬛ : 🎂
Ⓑ⚪ : ⚪Ⓕ
⬛C : D⚪
⚪C : Ⓓ⚪
Ⓒ⬛ : ⬛B
Ⓒ⚪ : ⬛Ⓑ
D⬛ : ⚪E
D⚪ : ⚪Ⓔ
⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛
⬛E : A⚪
⚪E : Ⓐ⚪
Ⓔ⬛ : ⬛D
Ⓔ⚪ : ⬛Ⓓ
Ⓕ⬛ : ⚪C
Ⓕ⚪ : ⚪Ⓒ
⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

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^36534krokach, 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). Zasady

← : ←⬛
→ : ⬛→

oznacza, ż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 🎂. Aoznacza, że ​​głowa jest w stanie, Aa symbol pod głową to ⬛(0), podczas gdy Ⓐ oznacza, że ​​jest w stanie, Aa 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, Fponieważ zdarza się, że głowa nigdy nie kończy się w stanie Fz 1 pod nią).

Stan 🎂jest stanem zatrzymania. Ma specjalne zasady

⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

Jeś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

A⬛ : ⚪B
A⚪ : ⚪Ⓑ

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 stanu B, lub komórka może zawierać ⚪, w którym to przypadku powinna przejść do stanu Ⓑ, ponieważ jest ⚪pod spodem.

Podobnie,

⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛

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

    0   1

A   1RB 1LE
B   1RC 1RF
C   1LD 0RB
D   1RE 0LC
E   1LA 0RD
F   1RH 1RC

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, 1RHktó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łaby

Ⓑ⬛ : ⚪F

w

Ⓑ⬛ : 🎂

Dlatego Fw 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^36534kroków, aby się zatrzymać, ale 10^10^10^10^18705352kroków, co w rzeczywistości jest bardzo dużą liczbą.

48 punktów, złamane przez bb94

Alfabet: abc
Źródło: cbaabaabc
Cel: cbacbcabc
Reguły przepisywania:

ab: ba
bc: cb
ca: ac
ab: cc
bc: aa
ca: bb

287 punktów, bezpieczny

Źródło: YAAT

Cel:

VW644507203420630255035757474755142053542246325217734264734527745236024300376212053464720055350477167345032015327021403167165534313137253235506613164473217702550435776242713

Zasady:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

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 Cs wynosi:

22030661124527021657244569669713986649562044939414344827127551659400215941242670121250289039666163853124410625741840610262419007778597078437731811349579211

A głównymi czynnikami są:

220040395270643587721928041668579651570457474080109642875632513424514300377757
100120985046540745657156603717368093083538096517411033964934953688222272684423

Pierwszy numer mod 5 = 2, więc można uzyskać ostatni ciąg.

402 punkty

Alfabet: abcdefghijklmnopqrstu
Źródło: abcdoi
Cel: ioabcdnnnnnnnnnnnnnnnnnn
Reguły przepisywania:

ab: ba
ba: ab
ac: ca
ca: ac
dodać
da: ad
bc: cb
cb: bc
bd: db
db: bd
cd: dc
dc: cd
na: an
nb: bn
nc: cn
nd: dn
nm: mn
nj: jn
aoi: eag
boi: ebg
coi: ekg
doi: edg
ae: ha
be: hb
ce: hc
de: hd
ioa: kam
iob: kbm
ioc: kcm
iod: kdm
ma: aj
mb: bj
MC: CJ
md: dj
dg: rdnnnnnnnnnn
cg: qcnnnnn
bg: pbnn
ag: fan
cr: fc
br: fb
ar: fa
bq: fb
aq: fa
ap: fa
er: io
eq: io
ep: io
ef: io
hf: io
kd: dunnnnnnnnnn
kc: ctnnnnn
kb: bsnn
ka: aln
uc: cl
ub: bl
ua: al
tb: bl
ta: al
sa: al
um: oi
tm: oi
sm: oi
lm: oi
lj: oi
: n

Ostatnia reguła pozwala utworzyć tyle ns, ile potrzebujesz.

Brzydkie, jak się wydaje, w rzeczywistości jest całkiem fajne, w ten czy inny sposób ...

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:

spróbuj zrozumieć ciąg źródłowy, zanim przyjrzysz się regułom

Alfabet: ABEILRSTabcdefijlr

Źródło: SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE

Cel: SE

Przepisz reguły:

Ab: bA
bA: Ab
Aa: aA
aA: Aa
Dodać
dA: Ad
Ae: eA
eA: Ae
Af: fA
fA: Af
Ac: cA
cA: Ac
IA: AI
AI: IA
Bb: bB
bB: Bb
Ba: aB
aB: Ba
Bd: dB
eB: Be
Be: eB
dB: Bd
Bf: fB
fB: Bf
Bc: cB
cB: Bc
E: BE
S: SB
Ib: Abl
AIa: aI
IdB: dBI
BIe: eIB
AIf: AfI
BIfB: BfiLB
Lb: bL
La: aL
Le: eL
Ld: dL
Lf: fL
Lc: cL
ib: bi
ia: ai
tj .: ei
id: di
jeśli: fil
lb: bl
la: al
le: el
ld: dl
lf: fl
lc: cl
icl: ci
icL: cI
Ic: jRc
bj: jb
aj: ja
dj: jd
ej: je
br: rb
ar: ra
dr: rd
er: re
fr: rf
cr: rc
bR: Rb
aR: Ra
dR: Rd
eR: Re
fR: Rf
cR: Rc
cj: jrc
fjr: jf
fjR: Jeśli
TO
TB: T
BT: T
bT: T
aT: T
dT: T
eT: T
fT: T
cT: T
T:

Zauważ, że początkowo popełniłem kilka błędów, więc wynik został zmieniony. Niemniej jednak pomysł jest taki sam. Mam nadzieję, że nie będzie już więcej błędów.

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 5 Cs, więc 7 znaków)

Zasady:

P.  →  .PP
!.  →  !
x   →  AxB
x   →  
AB  →  BAC
CB  →  BC
CA  →  AC
[B  →  [
[A  →  {
{A  →  {
!   →  !m
mP  →  PmD
Dm  →  mD
DP  →  PD
!P  →  ?
?P  →  ?
!m  →  <
<m  →  <
C<D →  <

Jest 19 zasad, łączna liczba znaków = 67.

106 punktów - złamane przez HyperNeutrino

Alfabet: ABCDEFGHIJ

Źródło: FIABCJAGJDEHHID

Cel: F

Przepisać zasady:

B:DCIE
A:IFBA
D:EEFJ
C:GFIC
E:HBJG
F:FEBG
G:HFCJ
H:DIGB
I:FCAH
J:BHEA

EJGI:FF
FFF:J
FF:E
EE:D
DDEA:FI
I:F

Ok, HyperNeutrino udowodnił, że jest to nierozwiązywalne. Istnieje jednak inne rozwiązanie tego problemu.

Brać:

I E C D H G J A F B
1 2 3 4 5 6 7 8 9 10

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ąć.