Ini adalah tantangan polisi dan perampok yang agak mirip golf . 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.
Jawaban:
jimmy23013
Mari kita bekerja mundur untuk yang ini. Kami pertama-tama mengubah digit menjadi representasi biner mereka. Kami beralih dari
VW626206555675126212043640270477001760465526277571600601
keVW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+
. Selanjutnya, kami terus menerapkan kebalikan dariDCW:W+
danDW:W_
sampai kami menghapus semua simbol. Hasil kami sekarangVDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW
. Kami sekarang ingin membuat senar ini cocokVD+C+W
; yaitu, kami ingin memindahkan semuaD
s ke kiri semuaC
s. Ini dapat dilakukan dengan membalikkanDCC:CD
. Kami melakukan ini dengan mengulangi algoritma berikut:D
di sebelah kanan blokC
s.D
ke kiri blok itu.C
s.Melalui beberapa matematika, kita dapat menentukan bahwa kita akan berakhir dengan 123
D
detik dan 4638704741628490670592103344196019722536654143873C
s (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 semuaD
itu sekarang, jadi kita dapatkanVCCC.......CCCW
. Kami mengubahV
kembali menjadiYZ
. Sekarang sudahYZCCC.......CCCW
.Kami ingin dapat menyingkirkan semua
C
dan memilikinya dalam bentukYAAA...AAABBB...BBBZW
. Untungnya, ini bisa dilakukan dengan metode berikut. Pertama, kami melakukan inverse-applyYB:Y
587912508217580921743211 kali untuk mendapatkanYBBB.......BBBZCCC.......CCCW
. Kemudian, kami mengulangi urutan langkah-langkah berikut (di mana[?*]
berarti sejumlah?
, tidak harus lebih besar dari nol):CZ:ZC
587912508217580921743211 kali untuk mendapatkanY[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
CB:BC
berkali-kali untuk mendapatkanY[A*]BCBCBC.......BCBCBCZCCC.......CCCW
AZ:Z
danAB:BCA
berkali-kali mendapatkanY[A*]ABBB.......BBBZCCC.......CCCW
Melalui induksi, kita melihat bahwa kita dapat memindahkan
BZ
kombinasi hingga akhir (kecuali sebelumW
) dan kemudian jumlahA
s adalah 1/587912508217580921743211 dari jumlahC
s, meninggalkan kita dengan 789012765809661838674788A
s. Kami sekarang punyaYAAA.......AAABBB.......BBBZW
. KonversikanZW
kembali ke aU
, lalu balik -terapkanU:BU
berkali-kali agar hanya 2B
detik dan kemudian konversiBBU
menjadiT
, dan sekarang Anda milikiYAAA.......AAAT
. Kemudian, Anda bisa terbalik-menerapkanT:AAAAAT
berkali-kali untuk mendapatkanYAAAT
karena jumlahA
s adalah 3 lebih besar dari kelipatan 5.Terima kasih atas tantangannya!
sumber
A:B
untukABC
memberiBBC
, itu jelas bahwa menerapkan kebalikan dariA:B
untukBBC
dapat memberikanABC
. 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.A:B
dan tidak dinyatakan bahwa berlaku terbalik diizinkan maka saya tidak berpikir Anda bisa beralih dariBBC
keABC
. Kasus spesifik ini mungkin berbeda dan ada beberapa cara untuk pergi ke arah lain. Saya akan memeriksanya nanti.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.
sumber
feersum
Ini adalah teka-teki sokoban. Posisi awal adalah:
Posisi akhir adalah:
Itu dapat dipecahkan menggunakan urutan kunci berikut:
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.
Cobalah online!
Cobalah online (dengan kode pelepasan dihapus)!
Untuk naik dan turun,
!:wLW_
atau!:_VRv
diterapkan 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.
sumber
Tidak
Kami gunakan
[X,Y]
untuk menunjukkan proses YX
sMulai dari
xnor = xn[o,1]r
, mengulangi 10 kali algoritma - kecuali dalam loop 10 kami berhenti di Langkah 4, memilikix[o,1024]r
.Menerapkan Aturan 4, ini menghapus 1023 = 11 * 93
o
detik, meninggalkanxor
.sumber
VortexYT
Tidak ada cara menghilangkan
F
s tanpa membuat / menggunakan karakter lain; jadi, kita harus menggunakanI:F
sebagai langkah terakhir untuk mencapai target. Tidak ada aturan yang memberikan satuI
tanpa 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
F
keI
sebelum Anda memiliki pilihan lagi.sumber