Abstrak Penulisan Ulang Tantangan (Perampok)

9

Ini adalah tantangan agak mirip . Ini adalah utas perampok; utas polisi ada di sini .

Perampok

Polisi akan memposting sistem penulisan ulang abstrak. Tugas Anda adalah untuk memecahkan kiriman mereka dengan membuktikan bahwa string target dapat atau tidak dapat dicapai dari string sumber dengan menerapkan aturan penulisan ulang mereka. (Anda dapat melakukan ini dengan memposting urutan aturan penulisan ulang yang dimulai dengan string sumber dan berakhir dengan target, atau dengan membuktikan secara matematis bahwa ini ada, atau tidak, ada.)

Lihat utas polisi untuk detail dan definisi.

Nathaniel
sumber
Lakukan! Saya memberi hadiah pada pertanyaan yang salah, ini seharusnya menjadi tantangan polisi. Jadi seseorang akan mendapat hadiah acak.
Nathaniel
Jangan khawatir, saya telah mengembalikan hadiah itu.
James
@DJMcMayhem: Huh ... jadi itu sebabnya API SE mencantumkan pertanyaan ini sebagai fitur, tetapi tanpa jumlah hadiah atau tanggal penutupan. : o Oh well, saatnya menambahkan beberapa validasi input ke skrip pengguna saya.
Ilmari Karonen

Jawaban:

16

jimmy23013

Mari kita bekerja mundur untuk yang ini. Kami pertama-tama mengubah digit menjadi representasi biner mereka. Kami beralih dari VW626206555675126212043640270477001760465526277571600601ke VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. Selanjutnya, kami terus menerapkan kebalikan dari DCW:W+dan DW:W_sampai kami menghapus semua simbol. Hasil kami sekarang VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. Kami sekarang ingin membuat senar ini cocok VD+C+W; yaitu, kami ingin memindahkan semua Ds ke kiri semua Cs. Ini dapat dilakukan dengan membalikkan DCC:CD. Kami melakukan ini dengan mengulangi algoritma berikut:

  1. Temukan yang pertama Ddi sebelah kanan blok Cs.
  2. Pindahkan Dke kiri blok itu.
  3. Gandakan jumlah Cs.

Melalui beberapa matematika, kita dapat menentukan bahwa kita akan berakhir dengan 123 Ddetik dan 4638704741628490670592103344196019722536654143873 Cs (Anda benar tentang ini tidak pas dalam jawaban SE ... Saya ragu ini akan cocok jika disimpan sebagai keadaan semua atom di Bumi gabungan: P).

Jika kita terus menerapkan kebalikannya V:VD, kita dapat menyingkirkan semua Ditu sekarang, jadi kita dapatkan VCCC.......CCCW. Kami mengubah Vkembali menjadi YZ. Sekarang sudah YZCCC.......CCCW.

Kami ingin dapat menyingkirkan semua Cdan memilikinya dalam bentuk YAAA...AAABBB...BBBZW. Untungnya, ini bisa dilakukan dengan metode berikut. Pertama, kami melakukan inverse-apply YB:Y587912508217580921743211 kali untuk mendapatkan YBBB.......BBBZCCC.......CCCW. Kemudian, kami mengulangi urutan langkah-langkah berikut (di mana [?*]berarti sejumlah ?, tidak harus lebih besar dari nol):

  1. Inverse-berlaku CZ:ZC587912508217580921743211 kali untuk mendapatkanY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
  2. Inverse-berlaku CB:BCberkali-kali untuk mendapatkanY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
  3. Inverse-apply AZ:Zdan AB:BCAberkali-kali mendapatkanY[A*]ABBB.......BBBZCCC.......CCCW

Melalui induksi, kita melihat bahwa kita dapat memindahkan BZkombinasi hingga akhir (kecuali sebelum W) dan kemudian jumlah As adalah 1/587912508217580921743211 dari jumlah Cs, meninggalkan kita dengan 789012765809661838674788 As. Kami sekarang punya YAAA.......AAABBB.......BBBZW. Konversikan ZWkembali ke a U, lalu balik -terapkan U:BUberkali-kali agar hanya 2 Bdetik dan kemudian konversi BBUmenjadi T, dan sekarang Anda miliki YAAA.......AAAT. Kemudian, Anda bisa terbalik-menerapkan T:AAAAATberkali-kali untuk mendapatkan YAAATkarena jumlah As adalah 3 lebih besar dari kelipatan 5.

Terima kasih atas tantangannya!

HyperNeutrino
sumber
Apakah itu dinyatakan di mana saja atau apakah secara default berlaku inversi diizinkan?
Weijun Zhou
2
@WeijunZhou Maksudku, jika menerapkan A:Buntuk ABCmemberi BBC, itu jelas bahwa menerapkan kebalikan dari A:Buntuk BBCdapat memberikan ABC. Itu tidak secara khusus menyatakan bahwa itu diperbolehkan, tetapi saya dapat dengan mudah membalikkan langkah saya dan memiliki solusi "konvensional", hanya saja lebih mudah untuk mundur IMO.
HyperNeutrino
Maksud saya, misalnya, jika hanya ada satu aturan A:Bdan tidak dinyatakan bahwa berlaku terbalik diizinkan maka saya tidak berpikir Anda bisa beralih dari BBCke ABC. Kasus spesifik ini mungkin berbeda dan ada beberapa cara untuk pergi ke arah lain. Saya akan memeriksanya nanti.
Weijun Zhou
2
@HyperNeutrino ^^
Weijun Zhou
1
Program mana yang Anda gunakan untuk memfaktorkan ini dan berapa lama?
user202729
9

boboquack

Untuk string yang diberikan, ambil semua huruf (a = 0, b = 1, c = 2), jumlahkan semuanya dan ambil modulo 3. Kemudian tidak ada aturan penulisan ulang yang mengubah nilai itu. String sumber memiliki nilai 1, dan target memiliki nilai 2. Oleh karena itu, tidak ada kombinasi aturan yang akan mengubah string sumber menjadi string target.

bb94
sumber
9

feersum

Ini adalah teka-teki sokoban. Posisi awal adalah:

          ___#
#___####_____#
#_#_#_##_#_!##
##______##_###
##__####_#_###
###__###__

Posisi akhir adalah:

          ___#
#___####_____#
#_#_#_##_#_###
##____!__#_###
##__####_#_###
###__###__

Itu dapat dipecahkan menggunakan urutan kunci berikut:

←← → ↓ ← ↑ ←←←←←← ↓ ↓ → ↑ ← ↑↑↑ ←← ↓ → ↑ → ↓ ↓ → → → → → → → ↑↑ ↓ ↓ ← ↓ ← ↑ ← → ↑ ←←← ← ↑ ←← ↓ → → → → → ↓ → → ↑↑ → ↑↑ ← ↓ ←← ↓ ↓ → ↑ ← ↑ → → ↑ → → ↓ ← ↓ ←← ↓ ←← ↓ ↓ → ↓ ←←←←←←← ↑ ↑ ←← ↓ → → ↓ → ↓ ↓ ← ↑ ← ↑ → ↑↑ ←← ↓ → ↑ → ↓ ↓ ← ↓ → ↑ → → lanjutkan → ↓ ↓ ↓ ← ↑ → ↑ ←←←←←← → → → → → → ↑↑ ← ↓ → ↓ ← ↑↑ → → ↑ → → ↓ ← ↓ ← → ↑↑ ← ↓ ← ↓ ↑ ↓ ↑ → → ↓ ← ↑ ←← ↓ ↓ ↓ → → ↑↑ ↓ ↓ ←← ↑↑ → ↓ ↑↑ → ↑ → → ↓ ← ↓ ← ↓ ←← ↑↑ → → ↑ → ↓ ← ↓ ↓ ←←←←← ↑ ←← ↓ → → lanjutkan → ←←←←← ↑↑ ←← ↓ → → ↓ ↓ ← ↑ → → → →

Berikut ini adalah program bash yang mengubah urutan kunci menjadi perintah sed dan menerapkannya. Perintah sed hanya berisi penggantian perintah menggunakan aturan penulisan ulang yang ditentukan dalam jawaban polisi, dan perintah pelabelan dan percabangan yang tidak mengubah string. Ini mengkonfirmasi bahwa Anda bisa mendapatkan string target hanya menggunakan aturan penulisan ulang.

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"

Cobalah online!

Cobalah online (dengan kode pelepasan dihapus)!

Untuk naik dan turun, !:wLW_atau !:_VRvditerapkan untuk satu kali sesuai, dan aturan yang relevan diterapkan berulang kali hingga !muncul kembali. Untuk benar, salah satu !#_:_!#dan !_:_!diterapkan. Untuk kiri, salah satu _#!:#!_dan _!:!_diterapkan.

Lihat output di tautan untuk posisi setelah setiap gerakan.

jimmy23013
sumber
6

Tidak

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

Kami gunakan [X,Y]untuk menunjukkan proses Y Xs

Mulai dari xn[o,A]r,

  1. Menerapkan Aturan 2 begitu kita miliki x[o,2]n[o,A-1]r.
  2. Menerapkan Aturan 2 sekali lagi yang kita miliki x[o,4]n[o,A-2]r
  3. Menerapkan sampai oantara ndan rmenjadi 0, kita miliki x[o,2*A]nr.
  4. Menerapkan Aturan 3 begitu kita miliki x[o,2*A]r.
  5. Menerapkan Aturan 1 begitu kita miliki xn[o,2*A]r.

Jadi, kami memiliki algoritma untuk menghasilkan dari xn[o,A]rke xn[o,2*A]r.

Mulai dari xnor = xn[o,1]r, mengulangi 10 kali algoritma - kecuali dalam loop 10 kami berhenti di Langkah 4, memiliki x[o,1024]r.

Menerapkan Aturan 4, ini menghapus 1023 = 11 * 93 odetik, meninggalkan xor.

Shieru Asakoto
sumber
2

VortexYT

Tidak ada cara menghilangkan Fs tanpa membuat / menggunakan karakter lain; jadi, kita harus menggunakan I:Fsebagai langkah terakhir untuk mencapai target. Tidak ada aturan yang memberikan satu Itanpa karakter yang tidak diinginkan lainnya sehingga Anda tidak dapat mencapai string target.

Ekuivalen, jika Anda mencoba untuk memetakan mundur dari sumber, Anda hanya bisa mendapatkan dari Fke Isebelum Anda memiliki pilihan lagi.

HyperNeutrino
sumber
Ooch, itu menyakitkan. Namun ada solusi lain ...
VortexYT
@VortexYT oh benar, ada? hm, tidak tahu. tapi ya target tidak dapat memetakan kembali lebih dari satu langkah yang mungkin membuat ini satu ton lebih mudah dari yang Anda maksudkan: P
HyperNeutrino
2x lebih mudah tepatnya
VortexYT