Tulis sebuah program atau fungsi yang mengambil dalam kotak teks persegi panjang di mana setiap sel adalah suatu A
atau a B
. Semua A
sel akan membentuk bentuk yang terhubung sederhana , yaitu mereka semua akan terhubung secara ortogonal tanpa lubang (huruf diagonal tetangga tidak dihitung sebagai terhubung). Demikian juga, semua B
sel akan membentuk bentuk lain yang terhubung sederhana. Kotak akan selalu mengandung setidaknya satu A
dan setidaknya satu B
.
Bayangkan kisi-kisi itu sebenarnya adalah dua potong plastik tipis berbentuk balok, diwakili oleh bagian A
dan B
. Jika ditempatkan rata di atas meja, bisakah kedua potongan itu digeser terpisah sambil menjaga keduanya tetap rata di atas meja?
Cetak atau kembalikan nilai kebenaran jika keduanya A
dan B
bentuk dapat dipisahkan seperti ini hanya dengan menariknya terpisah. Jika tidak, mencetak atau mengembalikan falsy nilai.
Misalnya input
AAA
ABB
AAA
benar karena BB
bagian tersebut dapat digeser ke kanan, memisahkannya dari A
:
AAA
A BB
AAA
Namun inputnya
AAAA
ABBA
ABAA
palsu karena tidak ada cara untuk menggeser A
dan B
membagi bagian tanpa membuatnya tumpang tindih.
Kode terpendek dalam byte menang. Jika diinginkan, Anda dapat menggunakan dua karakter ASCII distik yang bisa dicetak untuk menggantikan A
dan B
.
Contoh Truthy (dipisahkan oleh garis kosong)
BBB
BAA
BBB
BA
A
B
AB
AB
AAA
BBB
AAAAB
ABBBB
ABBA
ABBA
AAAA
AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB
AAAAAAAAAAAA
ABABABABABAB
BBBBBBBBBBBB
BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB
AAA
BAA
AAA
Contoh-contoh Palsu
BBBB
BAAB
BABB
BBBB
BAAB
AABB
BBBBBBB
BBBBBAB
AAAAAAB
BBBBBBB
BAAA
BABA
BBBA
AABA
AAAA
AAAAAAA
ABBBBBA
AAAAABA
BBBBBBA
BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBAABBB
BBBBBBBB
BBBBBBBB
AAA
ABA
BBA
ABA
AAA
CJam,
3332201917 byteVersi revisi, dengan dukungan besar-besaran dari @ Sp3000 dan @ MartinBüttner:
Cobalah online
Kontribusi
Algoritma dan Bukti
Berikut ini menjelaskan kriteria puzzle yang terpisah secara horizontal. Huruf vertikal dapat ditentukan dengan melihat kolom alih-alih baris, atau mentranspos matriks karakter dan melihat baris lagi.
Saya akan menggunakan istilah "stretch" untuk urutan maksimum dari huruf yang sama. Misalnya, baris berikut memiliki masing-masing 1, 2, dan 3 peregangan:
Saya juga akan menggunakan istilah "interlocked" untuk baris / puzzle yang tidak dapat digeser terpisah.
Pengamatan utama adalah bahwa teka-teki dapat meluncur terpisah jika dan hanya jika semua baris memiliki paling banyak 2 peregangan . Atau terbalik, itu saling terkait jika dan hanya jika ada baris dengan lebih dari 2 peregangan .
Berikut ini mungkin tidak memenuhi syarat sebagai bukti matematika yang ketat, tetapi saya percaya bahwa itu membuat penjelasan yang meyakinkan mengapa ini harus terjadi.
Sangat mudah untuk melihat bahwa teka-teki itu saling terkait jika memiliki baris lebih dari 2 peregangan. Melihat satu baris dengan 3 bagian:
jelas bahwa itu mencegah puzzle dari meluncur terpisah karena
A
peregangan terkunci di antaraB
peregangan. Ini berarti bahwa baris saling bertautan, yang pada gilirannya membuat seluruh teka-teki saling bertautan.Arah kebalikan dari bukti tidak begitu jelas. Kita perlu menunjukkan bahwa tidak ada teka-teki yang saling terkait di mana semua baris hanya memiliki 1 atau 2 peregangan. Dimulai dengan beberapa pengamatan:
A
danB
, puzzle jelas tidak saling bertautan. Dalam hal ini, semuaA
sel tersisa dari semuaB
sel, atau sebaliknya, dan tidak ada tabrakan saat menggeser kedua bagian secara terpisah.Satu-satunya kasus rumit adalah teka-teki di mana kita memiliki baris dengan 2 peregangan dengan urutan berbeda. Saya akan menunjukkan bahwa puzzle semacam itu tidak ada di bawah spesifikasi yang diberikan. Untuk menunjukkan ini, mari kita lihat sebagian puzzle yang memang memiliki konfigurasi ini, di mana
.
wildcard:Sekarang, spesifikasi mengatakan bahwa kedua sel
A
danB
hanya terhubung di semua teka-teki yang valid. Untuk membuatA
sel terhubung di sebagian puzzle di atas, kami memiliki dua opsi:Kami melingkari salah satu peregangan
B
, misalnya:Untuk melakukan ini, kita harus memperpanjang salah satu baris untuk memiliki 3 peregangan, jadi ini tidak akan pernah memberi kita teka-teki yang valid di mana semua baris memiliki paling banyak 2 peregangan.
Kami menghubungkan mereka di jalur langsung:
The
A
sel sekarang hanya terhubung, dan belum ada baris dengan lebih dari 2 membentang. Namun,B
sel - sel juga perlu dihubungkan secara sederhana. Jalur langsung sekarang diblokir olehA
sel-sel yang terhubung , dan satu-satunya cara untuk menghubungkanB
sel - sel adalah untuk loop di sekitar salah satu pereganganA
sel. Ini mengarah kembali ke kasus 1, di mana kita tidak bisa melakukan itu tanpa membuat baris 3 peregangan.Untuk menghitung peregangan, implementasinya menggunakan operator CJam RLE.
Penjelasan Kode
sumber
JavaScript (ES6),
108107989182 byteDemo langsung . Diuji di Firefox. Mengambil input sebagai string yang dibatasi-baris baru.
Suntingan:
\n
ke baris literal.g
fungsi dan memanggil RegExp langsung pada array alih-alih menggunakanfind
.Bagaimana itu bekerja
Versi sebelumnya:
a
dan bagi dengan baris baru menjadi array string.a
dan simpan diT
. Gunakanmap
untuk beralih di atas setiap elemena
, pisahkan string ke dalam array karakter, dan gunakanmap
lagi untuk menambahkani
karakter th pada baris kei
baris thT
. Karena setiap elemenT
tidak diinisialisasi, pada akhirnya akan terlihat seperti"undefinedAAABBA"
, tetapi ini tidak masalah.g
yang cocok dengan pola/AB+A|BA+B/
. Jika cocok, potongan-potongan dikunci ke arah yang diberikan karena kemudian ada satu setB
s diapit antara dua atau lebihA
s atau sebaliknya.g
untuk menguji semua elemen bloka
dan transposinyaT
untuk kecocokan menggunakanfind
. Jika keduanya cocok, maka bagian-bagiannya terkunci di kedua arah, sehingga menghasilkan nilai falsy, sebaliknya yang benar.sumber
Javascript (ES6), 118
Penjelasan:
sumber
JavaScript (ES6) 72
74Edit 2 byte yang disimpan thx @NotthatCharles
Saya memiliki pemahaman intuitif bahwa jika satu potong dapat meluncur hanya sebagian kecil dari langkah, maka itu gratis. Kasing saat ini mengkonfirmasi hal ini.
Jadi saya periksa hanya satu langkah di setiap arah.
Karakter yang digunakan: 1 dan 0
2 byte lebih banyak untuk menggunakan 2 karakter yang dapat dicetak seperti A dan B
Tes menjalankan cuplikan di bawah ini di peramban yang mendukung EcmaScript 6 (mendukung operator penyebaran - IE Firefox)
sumber
s[p+o]=='0'
sepertinya agak panjang. Bisakah itu diganti dengan1-s[p+o]
, atau setidaknyas[p+o]==0
?=='A'
dapat digantikan oleh<'B'
. Sama untuk=='B'
x+s[p+o]=='AB'
?Mathematica
10069 byteDengan 31 byte besar yang disimpan, terima kasih kepada @Martin Buttner,
Memformat input sebagai matriks karakter; itu juga membuat transpos matriks. Jika salah satu matriks atau transposinya tidak lebih dari 2 run per baris maka puzzle tersebut dapat meluncur.
{a,a,b,b,b}
memiliki 2 run huruf.{a,a,b,a,a}
memiliki 3 run huruf.{a,a,b,a,a,a,b,b,b,b,b,b,b,b}
memiliki 4 huruf.sumber
Dyalog APL, 22 byte
Coba di sini. Ini adalah fungsi yang mengambil dalam array karakter 2D, dan mengembalikan
1
untuk instance geser dan0
untuk yang non-sliding. Algoritma ini mirip dengan sebagian besar jawaban lain: periksa matriks dan transposinya bahwa tidak ada baris yang berisi lebih dari satu pasangan huruf yang berdekatan. Untuk matriks input 4x3fungsi dapat dipanggil sebagai
yang menghasilkan
1
.Penjelasan
sumber
JavaScript (ES6), 94 byte
Metode alternatif dengan ukuran yang sama:
Ini mengembalikan
1
untuk input yang benar dan0
untuk kepalsuan. Saya mulai mengerjakan ini sebelum jawaban lain telah diposting. Saya juga awalnya mencoba menggunakan pemahaman array ES7, tapi itu berakhir sekitar 10 karakter lebih lama dari metode ini.Cobalah:
Saran diterima!
sumber