To jest trochę proof-golf-lubić policjanci i złodziejewyzwanie. To jest nić rabusiów; wątek gliniarzy jest tutaj .
Rabusie
Gliniarze opublikują abstrakcyjne systemy przepisywania. Twoim zadaniem jest złamanie ich zgłoszeń poprzez udowodnienie, że docelowy ciąg znaków może lub nie może zostać osiągnięty z ciągu źródłowego poprzez zastosowanie ich reguł przepisywania. (Możesz to zrobić, publikując sekwencję reguł przepisywania, która zaczyna się od ciągu źródłowego, a kończy na celu lub matematycznie dowodzi, że to istnieje lub nie istnieje.)
Zobacz wątek gliniarzy, aby uzyskać szczegółowe informacje i definicje.
Odpowiedzi:
jimmy23013
Pracujmy wstecz nad tym. Najpierw przekształcamy cyfry w ich reprezentacje binarne. Idziemy od
VW626206555675126212043640270477001760465526277571600601
doVW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+
. Następnie stosujemy odwrotnośćDCW:W+
iDW:W_
dopóki nie usuniemy wszystkich symboli. Nasz wynik jest terazVDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW
. Chcemy teraz dopasować ten ciągVD+C+W
; to znaczy, chcemy przesunąć wszystkieD
s na lewo od wszystkichC
s. Można to zrobić przez odwrócenieDCC:CD
. Robimy to, powtarzając następujący algorytm:D
który znajduje się po prawej stronie blokuC
s.D
lewo od tego bloku.C
s.Za pomocą pewnej matematyki możemy ustalić, że skończymy z 123
D
si 4638704741628490670592103344196019722536654143873C
s (miałeś rację co do tego, że nie pasuje do odpowiedzi SE ... Wątpię, czy pasowałoby to, gdyby były przechowywane jako stany wszystkich atomów na Ziemi połączone: P).Jeśli nadal będziemy stosować odwrotność
V:VD
, możemy teraz pozbyć się wszystkichD
s, więc otrzymujemyVCCC.......CCCW
. Przekształcamy zV
powrotem wYZ
. Teraz mamyYZCCC.......CCCW
.Chcemy móc pozbyć się wszystkich
C
i mieć to w formieYAAA...AAABBB...BBBZW
. Na szczęście można to zrobić następującą metodą. Po pierwsze, stosujemy odwrotnieYB:Y
587912508217580921743211 razy, aby uzyskaćYBBB.......BBBZCCC.......CCCW
. Następnie powtarzamy następującą sekwencję kroków (gdzie[?*]
oznacza dowolną liczbę?
, niekoniecznie większą od zera):CZ:ZC
odwrotnie 587912508217580921743211 razy, aby uzyskaćY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
CB:BC
Aby uzyskać, zastosuj odwrotnieY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
AZ:Z
iAB:BCA
wiele razy, aby uzyskaćY[A*]ABBB.......BBBZCCC.......CCCW
Poprzez indukcję widzimy, że możemy przenieść
BZ
kombinację do końca (z wyjątkiem przedW
), a następnie liczbaA
s wynosi 1/587912508217580921743211 liczbyC
s, pozostawiając nam 7890127658096618386747843A
s. Teraz mamyYAAA.......AAABBB.......BBBZW
. Konwertuj zZW
powrotem na aU
, następnie zastosuj odwrotnieU:BU
wiele razy, aby zachować tylko 2B
s, a następnie przekonwertuj naBBU
aT
, a teraz maszYAAA.......AAAT
. Następnie możesz zastosować odwrotnieT:AAAAAT
wiele razy, aby uzyskać,YAAAT
ponieważ liczbaA
s była 3 większa niż wielokrotność 5.Dzięki za wyzwanie!
źródło
A:B
doABC
dajeBBC
, to oczywiste, że zastosowanie odwrotnościA:B
doBBC
dajeABC
. Nie jest wyraźnie stwierdzone, że jest to dozwolone, ale mogę łatwo cofnąć swoje kroki i mieć „konwencjonalne” rozwiązanie, po prostu łatwiej jest cofnąć się do IMO.A:B
i nie jest zaznaczone, że dozwolone jest stosowanie odwrotne, to nie sądzę, że można przejść odBBC
doABC
. Ten konkretny przypadek może być inny i istnieje jakiś sposób, aby pójść w innym kierunku. Sprawdzę to później.boboquack
Dla danego ciągu weź wszystkie litery (a = 0, b = 1, c = 2), zsumuj je i weź moduł 3. Wtedy żadna z reguł przepisywania nie zmieni tej wartości. Łańcuch źródłowy ma wartość 1, a cel ma wartość 2. Dlatego żadna kombinacja reguł nie przekształci łańcucha źródłowego w łańcuch docelowy.
źródło
feersum
To jest łamigłówka Sokoban. Pozycja początkowa to:
Pozycja końcowa to:
Można to rozwiązać za pomocą następującej sekwencji klawiszy:
Oto program bash, który konwertuje sekwencję klawiszy na komendy sed i stosuje je. Komendy sed zawierają tylko komendy zastępujące przy użyciu reguł przepisywania zdefiniowanych w odpowiedzi policjanta oraz komendy oznaczania i rozgałęziania, które nie modyfikują łańcucha. Potwierdza, że można uzyskać ciąg docelowy przy użyciu tylko reguł przepisywania.
Wypróbuj online!
Wypróbuj online (bez kodu ucieczki)!
W górę i w dół
!:wLW_
lub!:_VRv
stosuje się odpowiednio raz, a odpowiednie reguły stosuje się wielokrotnie, aż!
pojawi się ponownie. Na prawo, jeden!#_:_!#
i!_:_!
jest stosowana. Dla lewej stosowana jest jedna z_#!:#!_
i_!:!_
.Zobacz wynik w linkach dla pozycji po każdym ruchu.
źródło
xnor
Używamy
[X,Y]
do wskazania przebiegu YX
sZaczynając od
xnor = xn[o,1]r
, powtórzenie 10 razy algorytmu - z wyjątkiem 10. pętli zatrzymujemy się w kroku 4, mającx[o,1024]r
.Stosując Regułę 4, usuwa się 1023 = 11 * 93
o
s, pozostawiającxor
.źródło
VortexYT
Nie ma możliwości wyeliminowania
F
s bez tworzenia / używania innych znaków; dlatego musimy użyćI:F
jako ostatniego kroku, aby dotrzeć do celu. Żadna reguła nie daje singlaI
bez innych niepożądanych znaków, więc nie możesz dostać się do ciągu docelowego.Odpowiednio, jeśli spróbujesz zmapować wstecz od źródła, możesz dostać się od
F
do,I
zanim nie będziesz mieć więcej opcji.źródło