Membangun pemecah teka-teki MU

16

The MU puzzle adalah teka-teki di mana Anda mengetahui apakah Anda dapat mengubah MImenjadi MUdiberikan operasi berikut:

  1. Jika string Anda berakhir I, Anda dapat menambahkan Usampai akhir. (mis. MI -> MIU)

  2. Jika string Anda dimulai dengan M, Anda dapat menambahkan salinan bagian setelah Mke string.
    (mis. MII -> MIIII)

  3. Jika string Anda berisi tiga berturut I- turut , Anda dapat mengubahnya menjadi U.
    (mis. MIII -> MU)

  4. Jika string Anda berisi dua berturut U- turut , Anda dapat menghapusnya. (mis MUUU -> MU.).

Tugas Anda adalah untuk membangun program yang menentukan apakah ini bisa dilakukan untuk string awal dan akhir.

Program Anda akan mengambil dua string sebagai input. Setiap string akan terdiri dari yang berikut:

  • satu M.

  • string hingga dua puluh sembilan Idan U.

Program Anda kemudian akan kembali true(atau representasi bahasa pemrograman Anda / YPLRT) jika string kedua dapat dijangkau dari string pertama, dan false(atau YPLRT) jika tidak.

Contoh input dan output:

MI  MII
true

MI  MU
false

MIIIIU  MI
true

Kode terpendek dalam bahasa apa pun untuk melakukan ini akan menang.

code-golf puzzle-solver Joe Z.
sumber
8
Saat ini saya sedang membaca Gödel, Escher, Bach dan berpikir untuk melakukan "lapangan golf 18 lubang" berdasarkan bab-babnya sesudahnya. Kira saya harus menemukan "hole 1" baru sekarang. ;)
Martin Ender
Ini hanya pertanyaan tingkat keterjangkauan yang intinya telah ditanyakan berkali-kali sebelumnya.
Peter Taylor
1
@PeterTaylor Saya pikir ada peluang bagus ini tidak akan diselesaikan dengan pencarian eksplisit dari grafik jangkauan. Aturan MIU memiliki banyak struktur, dan saya tidak akan terkejut jika ada algoritma langsung untuk menguji tingkat keterjangkauan tanpa mencari node perantara. Misalnya, node yang dapat dijangkau MIpersis di M(I|U)*mana jumlah Ibukan kelipatan 3. Dan pemeriksaan langsung seperti itu pasti membuat kode lebih pendek. Juga, saya tidak tahu tentang a-priori terikat pada panjang string yang diperlukan untuk langkah-langkah perantara, jadi pencarian langsung mungkin tidak praktis.
xnor
1
Saya sudah memikirkan masalah ini untuk sementara waktu dan belum mendekati solusi yang tidak kasar. Jika tidak ada yang menggigit, saya sarankan memposting versi pertanyaan yang lebih mudah, mungkin untuk memberikan derivasi mulai dari MIstring yang dapat dijangkau yang diberikan.
xnor
1
Apa yang seharusnya menjadi output jika IMdisediakan atau MUMMI?
Beta Decay

Jawaban:

7

Prolog SWI, 183 karakter

m(A,A).
m([i],[i,u]).
m([i,i,i|T],B):-m([u|T],B).
m([u,u|T],B):-m(T,B).
n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)).
n(A,B):-m(A,B).
s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y).

Bagaimana dengan Prolog, (karena tidak ada yang menjawab dalam 6 bulan). Untuk menjalankan, cukup gunakan "s (mi, mu)." Kode memecah atom menjadi karakter, lalu mencari solusinya.

swstephe
sumber
2
Ini secara salah mengembalikan false s(mi,miiii), dan secara umum apa pun yang membutuhkan lebih dari satu penerapan aturan 2 untuk membuktikan.
algorithmshark