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

Polisi

Tugas Anda adalah mendefinisikan sistem penulisan ulang abstrak yang sulit dijangkau satu kata dari kata lain. Anda akan mempersiapkan hal-hal berikut:

1. Seperangkat simbol, disebut alfabet. (Anda dapat menggunakan karakter Unicode untuk ini, tapi jangan gunakan spasi putih, atau simbol yang sulit dibedakan satu sama lain.)

2. Sebuah tali sumber terdiri dari simbol-simbol dari alfabet Anda.

3. Sebuah String Target terdiri dari simbol-simbol dari alfabet Anda.

4. Satu set aturan penulisan ulang menggunakan karakter dari alfabet Anda. (Lihat di bawah untuk definisi aturan penulisan ulang.)

5. Bukti yang menunjukkan apakah string sumber Anda dapat dikonversi menjadi string target Anda dengan penerapan berturut-turut aturan penulisan ulang Anda. Bukti ini mungkin terdiri dari urutan aktual dari langkah-langkah penulisan ulang, atau bukti matematika bahwa urutan seperti itu harus ada, atau bukti matematika bahwa urutan seperti itu tidak ada.

Anda akan memposting empat pertama dari ini, menjaga kerahasiaan bukti; perampok akan mencoba memecahkan jawaban Anda dengan memberikan bukti sendiri bahwa string target Anda dapat atau tidak dapat dijangkau dari string sumber Anda. Jika kiriman Anda tidak retak dalam waktu dua minggu , Anda dapat menandainya sebagai aman dan mengeditnya sebagai bukti.

Pengajuan akan diberi skor sesuai dengan jumlah karakter dalam aturan penulisan ulang mereka dan string sumber dan target mereka, sebagaimana dirinci di bawah ini. Pemenang akan menjadi pengajuan tanpa retak dengan skor terendah.

Apa itu aturan penulisan ulang?

Aturan penulisan ulang hanyalah sepasang string dalam alfabet Anda. (Salah satu dari string ini mungkin kosong.) Aplikasi aturan penulisan ulang terdiri dari menemukan substring yang sama dengan string pertama dalam pasangan, dan menggantinya dengan yang kedua.

Contoh harus menjelaskan ini:

Misalkan alfabet adalah A, Bdan C; string sumbernya adalah " A"; string target adalah " C" dan aturan penulisan ulangnya adalah

A:B
B:BB
B:A
AA:C

maka string target dapat dijangkau dengan cara berikut:

A
B   (using rule 1)
BB  (using rule 2)
AB  (using rule 3)
AA  (using rule 3)
C   (using rule 4)

Mencetak gol

Skor Anda akan

• panjang string sumber Anda,
• ditambah panjang string target Anda,
• ditambah panjang semua string yang termasuk dalam aturan penulisan ulang Anda,
• ditambah satu poin ekstra untuk setiap aturan penulisan ulang.

Jika Anda menulis aturan penulisan ulang dengan pemisah titik dua seperti di atas, ini hanya panjang total semua aturan penulisan ulang (termasuk pemisah), ditambah panjang sumber dan string target. Skor yang lebih rendah lebih baik. Jumlah karakter berbeda dalam alfabet Anda akan digunakan untuk memutuskan ikatan, dengan lebih sedikit yang lebih baik.

Karunia

Saya ingin melihat jawaban yang benar-benar cocok untuk skor rendah. Saya akan memberikan 200 rep untuk jawaban pertama yang mendapat skor kurang dari 100 poin dalam tantangan ini dan tidak retak.

326 poin - Retak oleh jimmy23013

Levelnya adalah Picokosmos # 13 oleh Aymeric du Peloux (dengan modifikasi sepele). Saya mencoba untuk menemukan level berselera yang dapat diimplementasikan dengan "kotak" dan "dinding" menjadi karakter yang sama. Untuk level ini dimungkinkan dengan membuat titik choke pusat dua kolom lebih lebar daripada satu.

Aturan / string awal / target bisa bermain golf sedikit lebih, tapi ini hanya untuk bersenang-senang.

String awal:

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

String target:

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

Aturan:

_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 poin, dipecahkan oleh HyperNeutrino

Sumber: YAAAT

Target: VW626206555675126212043640270477001760465526277571600601

Aturan:

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

Hanya sesuatu yang jelas untuk dilakukan. Urutan sebenarnya dari langkah menulis ulang mungkin tidak cocok dengan jawaban SE.

33 poin, dipecahkan oleh user71546

Yang sederhana untuk memulai.

Sumber: xnor
Target: xor
Aturan penulisan ulang:

x:xn
no:oon
nr:r
ooooooooooo:

Aturan terakhir membutuhkan 11o ke string kosong.

139 poin (safe-ish)

Saya bermaksud jawaban ini menjadi retak, dan user202729 pada dasarnya menyelesaikannya di komentar, tetapi tidak ada yang memposting jawaban di utas perampok, jadi saya menandainya "safe-ish" dan termasuk bukti saya di bawah ini.

(Hal-hal ini jelas jauh lebih mudah dibuat daripada retak. Tidak ada yang mencoba untuk mendapatkan skor yang sangat rendah, dan mungkin ada lebih banyak kesenangan yang bisa didapat di akhir hal itu, jika tantangan ini pernah lepas landas. )

Inilah jawaban sendiri. Ini berpotensi sangat sulit, tetapi seharusnya mudah jika Anda mengetahui dari mana asalnya.

alfabet: ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→

sumber: ←A→

target: ←🎂→

Aturan: (spasi tidak signifikan)

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

Ini adalah versi ASCII , jika unicode tidak ditampilkan dengan baik untuk semua orang.

Bukti

Ini setara dengan pesaing terbaik saat ini untuk berang-berang sibuk enam negara . Berang-berang yang sibuk adalah mesin Turing yang berhenti setelah waktu yang sangat lama. Karena itu, string sumber ←A→memang dapat diubah menjadi string target ←🎂→, tetapi hanya setelah lebih dari 7*10^36534langkah, yang akan memakan waktu jauh lebih lama daripada usia alam semesta untuk implementasi fisik apa pun.

Pita mesin Turing diwakili oleh simbol ⬛(0) dan ⚪(1). Aturan

← : ←⬛
→ : ⬛→

berarti bahwa ujung kaset selalu dapat diperpanjang dengan lebih banyak nol. Jika kepala mesin Turing mendekati salah satu ujung pita, kita bisa menerapkan salah satu aturan ini, yang memungkinkan kita untuk berpura-pura bahwa pita itu tidak terbatas, dan mulai diisi dengan semua nol. (Simbol →dan ←tidak pernah dibuat atau dihancurkan, jadi mereka selalu ada di ujung rekaman itu.)

Kepala mesin Turing diwakili dengan simbol ABCDEⒶⒷⒸⒹⒺⒻdan 🎂. Aberarti kepala dalam keadaan Adan simbol di bawah kepala adalah a ⬛(0), sedangkan Ⓐ berarti itu dalam keadaan Adan simbol di bawahnya adalah ⚪(1). Ini dilanjutkan untuk negara bagian lain, dengan huruf yang dilingkari mewakili angka 1 di bawah kepala dan versi yang tidak dilingkari mewakili angka 0. (Tidak ada simbol Fkarena itu terjadi bahwa kepala tidak pernah berakhir dalam keadaan Fdengan angka 1 di bawahnya.)

Negara 🎂adalah keadaan tersendat-sendat. Ini memiliki aturan khusus

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

Jika keadaan penghentian tercapai, kita dapat berulang kali menerapkan aturan ini untuk "menyedot" semua rekaman itu (termasuk nol tambahan yang muncul dari perpanjangan pita lebih dari yang diperlukan), meninggalkan kita di negara bagian ←🎂→. Oleh karena itu masalah keterjangkauan bermuara pada apakah negara 🎂akan pernah tercapai.

Aturan yang tersisa adalah aturan transisi untuk mesin Turing. Misalnya aturannya

A⬛ : ⚪B
A⚪ : ⚪Ⓑ

dapat dibaca sebagai "jika mesin dalam keadaan A dan ada nol di bawah kepala, lalu tulis 1, ubah ke keadaan B dan bergerak ke kanan." Bergerak ke kanan membutuhkan dua aturan, karena sel kaset di sebelah kanan mungkin mengandung a ⬛, dalam hal ini mesin harus masuk ke keadaan B, atau sel mungkin berisi a ⚪, dalam hal itu harus masuk ke keadaan Ⓑ, karena ada di ⚪bawahnya.

Demikian pula,

⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛

berarti "jika mesin dalam keadaan D dan ada 1 di bawah kepala, lalu tulis 0, ubah ke keadaan C dan pindah ke kiri."

Mesin Turing yang digunakan ditemukan oleh Pavel Kropitz pada tahun 2010. Meskipun sering disebutkan dalam konteks berang-berang yang sibuk, tabel transisi sebenarnya agak sulit dilacak, tetapi dapat ditemukan misalnya di sini . Dapat ditulis sebagai

    0   1

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

yang dapat dibaca sebagai "jika mesin dalam keadaan A dan ada nol di bawah kepala, lalu tulis 1, ubah ke keadaan B dan bergerak ke kanan," dan seterusnya. Harus mudah, jika melelahkan, untuk memeriksa bahwa setiap entri tabel ini sesuai dengan sepasang aturan seperti dijelaskan di atas.

Satu-satunya pengecualian adalah aturan 1RHyang terjadi ketika mesin berada dalam keadaan F lebih dari 0, karena tampaknya cukup sia-sia untuk membuat mesin menulis angka 1 dan bergerak ke kanan ketika mesin itu bisa langsung berhenti begitu ia memasuki keadaan F lebih dari 0. Jadi saya mengubah aturan yang seharusnya

Ⓑ⬛ : ⚪F

ke

Ⓑ⬛ : 🎂

Inilah sebabnya mengapa tidak ada simbol Fdalam alfabet. (Ada beberapa 'golf' lain yang bisa saya buat, tetapi saya tidak ingin terlalu banyak mengaburkannya.)

Pada dasarnya itu. String target dapat dijangkau dari string sumber, tetapi hanya setelah sejumlah langkah konyol.

Satu lagi fakta yang menyenangkan: jika saya pernah menggunakannya

←A⚪⚪→

sebagai titik awal sebagai gantinya, maka tidak akan mengambil 7*10^36534langkah untuk berhenti, tetapi 10^10^10^10^18705352langkah-langkah, yang merupakan jumlah yang sangat besar.

48 poin, dipecahkan oleh bb94

Alfabet: abc
Sumber: cbaabaabc
Target: cbacbcabc
Aturan penulisan ulang:

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

287 poin, aman

Sumber: YAAT

Target:

VW644507203420630255035757474755142053542246325217734264734527745236024300376212053464720055350477167345032015327021403167165534313137253235506613164473217702550435776242713

Aturan:

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

Saya menemukan bahwa openssl jauh lebih mudah digunakan daripada gpg untuk tujuan ini.

Lihat celah HyperNeutrino ke versi yang lebih lemah. Dalam hal ini, Jumlah Cs adalah:

22030661124527021657244569669713986649562044939414344827127551659400215941242670121250289039666163853124410625741840610262419007778597078437731811349579211

Dan faktor utamanya adalah:

220040395270643587721928041668579651570457474080109642875632513424514300377757
100120985046540745657156603717368093083538096517411033964934953688222272684423

Angka pertama mod 5 = 2, jadi mungkin untuk mendapatkan string terakhir.

402 poin

Alfabet: abcdefghijklmnopqrstu
Sumber: abcdoi
Target: ioabcdnnnnnnnnnnnnnnnnnn
Aturan penulisan ulang:

ab: ba
ba: ab
ac: ca
ca: ac
tambah sebuah
da: ad
bc: cb
cb: bc
bd: db
db: bd
cd: dc
dc: cd
Naan
nb: bn
nc: cn
nd: dn
nm: mn
nj: jn
aoi: eag
boi: ebg
coi: ecg
doi: edg
ae: ha
menjadi: hb
ce: hc
de: hd
ioa: kam
iob: kbm
ioc: kcm
iod: kdm
ma: aj
mb: bj
mc: cj
md: dj
dg: rdnnnnnnnnnnn
cg: qcnnnnn
bg: pbnn
ag: penggemar
cr: fc
br: fb
ar: fa
bq: fb
aq: fa
ap: fa
er: io
eq: io
ep: io
ef: io
hf: io
kd: dunnnnnnnnnnn
kc: ctnnnnnn
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

Aturan terakhir memungkinkan Anda untuk membuat sebanyak yang nAnda butuhkan.

Jelek seperti yang terlihat, itu sebenarnya cukup bagus, dengan satu atau lain cara ...

1337 Poin

Jelas tidak kompetitif, dan butuh waktu terlalu lama untuk membuat (saya harap saya tidak membuat kesalahan).

Petunjuk:

cobalah untuk memahami string sumber sebelum melihat aturan

Alfabet: ABEILRSTabcdefijlr

Sumber: SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE

Target: SE

Aturan penulisan ulang:

Ab: bA
bA: Ab
Aa: aA
aA: Aa
Tambah sebuah
dA: Iklan
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: Jadilah
Jadilah: eB
dB: Bd
Bf: fB
fB: Bf
Bc: cB
cB: Bc
E: BE
S: SB
Ib: AbI
AIa: aI
IdB: dBI
BIe: eIB
Jika: AfI
BIfB: BfiLB
Lb: bL
La: aL
Le: eL
Ld: dL
Lf: fL
Lc: cL
ib: bi
besarbesaran: ai
yaitu: ei
id: di
jika: fil
lb: bl
la: al
le: el
ld: dl
Jika: 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: Jika
SAYA T
TB: T
BT: T
bT: T
aT: T
dT: T
eT: T
fT: T
cT: T
T:

Perhatikan bahwa saya membuat beberapa kesalahan pada awalnya, sehingga nilainya berubah. Namun demikian, idenya sama. Saya harap tidak ada lagi kesalahan sekarang.

154 Poin

Alfabet: P.!xABC[{mD<
Sumber: [x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 karakter)
Target: {CCCCC<(ada 5 Cs, jadi 7 karakter)

Aturan:

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 →  <

Ada 19 aturan, jumlah karakter = 67.

106 poin - dipecahkan oleh HyperNeutrino

Alfabet: ABCDEFGHIJ

Sumber: FIABCJAGJDEHHID

Target: F

Aturan Tulis Ulang:

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

Oke, HyperNeutrino telah membuktikan bahwa ini tidak dapat dipecahkan. Namun, ada solusi lain untuk ini.

Mengambil:

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

Nilai sumbernya genap. Nilai targetnya ganjil. Jika kita mengambil setiap sisi, total nilainya, dan ambil nilainya ke mod 2, nilainya tetap sama. Karena itu, ini tidak dapat dicapai.