Wyzwanie abstrakcyjnego przepisywania (rabusie)

9

To jest trochę -lubić wyzwanie. 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.

Nataniel
źródło
Do'h! Złożyłem nagrodę za niewłaściwe pytanie, które miało być wyzwaniem dla gliniarzy. Więc ktoś dostanie losową nagrodę.
Nataniel
Nie martw się, zwróciłem nagrodę.
James
@DJMcMayhem: Huh ... więc dlatego API SE wymienia to pytanie jako polecane, ale bez kwoty nagrody ani daty zamknięcia. : o No cóż, czas dodać poprawność danych wejściowych do mojego skryptu użytkownika.
Ilmari Karonen

Odpowiedzi:

16

jimmy23013

Pracujmy wstecz nad tym. Najpierw przekształcamy cyfry w ich reprezentacje binarne. Idziemy od VW626206555675126212043640270477001760465526277571600601do VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. Następnie stosujemy odwrotność DCW:W+i DW:W_dopóki nie usuniemy wszystkich symboli. Nasz wynik jest teraz VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. Chcemy teraz dopasować ten ciąg VD+C+W; to znaczy, chcemy przesunąć wszystkie Ds na lewo od wszystkich Cs. Można to zrobić przez odwrócenie DCC:CD. Robimy to, powtarzając następujący algorytm:

  1. Znajdź pierwszy, Dktóry znajduje się po prawej stronie bloku Cs.
  2. Przesuń w Dlewo od tego bloku.
  3. Podwój liczbę Cs.

Za pomocą pewnej matematyki możemy ustalić, że skończymy z 123 Dsi 4638704741628490670592103344196019722536654143873 Cs (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ę wszystkich Ds, więc otrzymujemy VCCC.......CCCW. Przekształcamy z Vpowrotem w YZ. Teraz mamy YZCCC.......CCCW.

Chcemy móc pozbyć się wszystkich Ci mieć to w formie YAAA...AAABBB...BBBZW. Na szczęście można to zrobić następującą metodą. Po pierwsze, stosujemy odwrotnie YB:Y587912508217580921743211 razy, aby uzyskać YBBB.......BBBZCCC.......CCCW. Następnie powtarzamy następującą sekwencję kroków (gdzie [?*]oznacza dowolną liczbę ?, niekoniecznie większą od zera):

  1. Zastosuj CZ:ZCodwrotnie 587912508217580921743211 razy, aby uzyskaćY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
  2. CB:BCAby uzyskać, zastosuj odwrotnieY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
  3. Zastosuj odwrotnie AZ:Zi AB:BCAwiele razy, aby uzyskaćY[A*]ABBB.......BBBZCCC.......CCCW

Poprzez indukcję widzimy, że możemy przenieść BZkombinację do końca (z wyjątkiem przed W), a następnie liczba As wynosi 1/587912508217580921743211 liczby Cs, pozostawiając nam 7890127658096618386747843 As. Teraz mamy YAAA.......AAABBB.......BBBZW. Konwertuj z ZWpowrotem na a U, następnie zastosuj odwrotnie U:BUwiele razy, aby zachować tylko 2 Bs, a następnie przekonwertuj na BBUa T, a teraz masz YAAA.......AAAT. Następnie możesz zastosować odwrotnie T:AAAAATwiele razy, aby uzyskać, YAAATponieważ liczba As była 3 większa niż wielokrotność 5.

Dzięki za wyzwanie!

HyperNeutrino
źródło
Czy podano gdziekolwiek, czy domyślnie dozwolone jest stosowanie odwrotne?
Weijun Zhou,
2
@WeijunZhou Mam na myśli, że jeśli aplikujesz A:Bdo ABCdaje BBC, to oczywiste, że zastosowanie odwrotności A:Bdo BBCdaje ABC. 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.
HyperNeutrino,
Chodzi mi na przykład o to, że jeśli istnieje tylko jedna reguła A:Bi nie jest zaznaczone, że dozwolone jest stosowanie odwrotne, to nie sądzę, że można przejść od BBCdo ABC. Ten konkretny przypadek może być inny i istnieje jakiś sposób, aby pójść w innym kierunku. Sprawdzę to później.
Weijun Zhou,
2
@HyperNeutrino ^^
Weijun Zhou
1
Którego programu użyłeś do faktoryzacji tego i ile to zajęło?
user202729,
9

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.

bb94
źródło
9

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:

← ↑ → ↓↓ ← ↑ ← budżetu osobistego budżetu ↓↓ → ↑ ← ↑↑ ← ← ↓ → ↑ → ↓↓ → SIEM SIEM SIEMraj ↓ → ↑↑ ↓↓ ← ↓ ← ↑ → ↑ ← ← ↑ ←, ↓ → → SIEM SIEM, ↓ → ↑ ↑↑ → ↑↑ ← ↓ ←, ↓↓ → ↑ ← ↑ →, ↑ → → ↓ ← ↓ ← budżetu ↓↓ → ↑ ← ↑ ← ↑ ↓ → SIEM ↓ → ↓↓ ← ↑ ← ↑ → ↑↑ ← ↑ ↓ → ↑ → ↓↓ ← ↓ → ↑ → → SIEM → BHD ↑ ↑ ← ↓ → ↓ ← ↑ ↑ → ​​↑ ↑ → ​​BH ↓ ← ↓ ← → ↑ ↑ ← ↓ ← ↓ ↑ → SIEM ↓ ← ↑ ← ← ↓↓↓ → ↑ ↑↑ → ↓ ↑↑ → ↑ → ▼ ↓ ← ↓ ← ↓ ← ↑ ↑ ↑ → ​​↑ ↑ → ​​↓ ← ↓↓ ← sprzętu publicznego ↑ ↑ opcji ↓ → SIEM ↓↓ ← ↑ → → BHB

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.

s="___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__"
input=

while
    printf '\n%80s\n' "$s"|fold -w14
    read -n 1
    [ "$REPLY" = $'\e' ]
do
    read -n 2
    case "$REPLY" in
    [A)
        s="$(sed '
s:!:wLW_:
        :a
s:L:<<<<<<<<<<<<<:
s:#w<:w#:
s:_w<:w_:
s:_<:<_:
s:#<:<#:
s:#wW:wLX!:
s:_W:W_:
s:#W:W#:
s:_wW:!:
s:_X:X_:
s:#X:X#:
s:_wX:#:
        ta' <<<"$s")";;
    [B)
        s="$(sed '
s:!:_VRv:
        :a
s:R:>>>>>>>>>>>>>:
s:>v#:#v:
s:>v_:_v:
s:>_:_>:
s:>#:#>:
s:Vv#:!URv:
s:U_:_U:
s:U#:#U:
s:Uv_:#:
s:V_:_V:
s:V#:#V:
s:Vv_:!:
        ta' <<<"$s")";;
    [C)
        s="$(sed '
s:!#_:_!#:
        te
s:!_:_!:
        :e' <<<"$s")";;
    [D)
        s="$(sed '
s:_#!:#!_:
        te
s:_!:!_:
        :e' <<<"$s")";;
    esac
    input="$input${REPLY:1}"
done

echo "$input"

Wypróbuj online!

Wypróbuj online (bez kodu ucieczki)!

W górę i w dół !:wLW_lub !:_VRvstosuje 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.

jimmy23013
źródło
6

xnor

Zasada 1 x:xn Zasada 2 no:oon Zasada 3 nr:r Zasada 4ooooooooooo:

Używamy [X,Y]do wskazania przebiegu Y Xs

Począwszy od xn[o,A]r,

  1. Stosowanie reguły 2, gdy tylko będziemy x[o,2]n[o,A-1]r.
  2. Ponownie stosujemy zasadę 2 x[o,4]n[o,A-2]r
  3. Stosujemy, dopóki os pomiędzy ni nie rosiągnie 0, mamy x[o,2*A]nr.
  4. Stosowanie reguły 3, gdy tylko będziemy x[o,2*A]r.
  5. Stosowanie Reguły 1, gdy tylko będziemy xn[o,2*A]r.

Mamy więc algorytm do generowania od xn[o,A]rdo xn[o,2*A]r.

Zaczynając od xnor = xn[o,1]r, powtórzenie 10 razy algorytmu - z wyjątkiem 10. pętli zatrzymujemy się w kroku 4, mając x[o,1024]r.

Stosując Regułę 4, usuwa się 1023 = 11 * 93 os, pozostawiając xor.

Shieru Asakoto
źródło
2

VortexYT

Nie ma możliwości wyeliminowania Fs bez tworzenia / używania innych znaków; dlatego musimy użyć I:Fjako ostatniego kroku, aby dotrzeć do celu. Żadna reguła nie daje singla Ibez 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 Fdo, Izanim nie będziesz mieć więcej opcji.

HyperNeutrino
źródło
Ooch, to boli. Jest jednak inne rozwiązanie ...
VortexYT,
@VortexYT o tak, naprawdę? hm, nie wiedziałem. ale tak, cel nie może odwzorować więcej niż jednego kroku, co prawdopodobnie uczyniło to tonę łatwiejszą niż zamierzałeś: P
HyperNeutrino
2x łatwiej być dokładnym
VortexYT