Misalkan suatu hari Anda menggali melalui kotak besar kabel dan adaptor komputer yang tidak digunakan (USB ke USB mini, VGA ke DVI, dll.). Ada kabel kusut di mana-mana membuat berantakan, dan Anda bertanya-tanya apakah Anda bisa menyederhanakan hal-hal dengan menyatukan semua kabel dalam satu untaian panjang, dan kemudian menggulungnya.
Pertanyaannya adalah, mungkinkah menghubungkan semua kabel dan adaptor Anda dalam satu garis panjang seperti ini? Jelas tidak selalu mungkin, misalnya jika Anda hanya memiliki dua kabel dengan colokan yang sama sekali berbeda, mereka tidak dapat dihubungkan bersama. Tetapi jika Anda memiliki kabel ketiga yang dapat terhubung ke keduanya, maka Anda dapat merangkai semua kabel Anda.
Anda tidak peduli tentang jenis colokan yang ada di ujung untai semua kabel. Mereka tidak perlu saling menyambungkan untuk membentuk lingkaran. Anda hanya ingin tahu apakah membuat untai semua kabel itu mungkin, dan jika ya, bagaimana cara melakukannya.
Tantangan
Tulis program atau fungsi yang menggunakan string multiline di mana setiap baris menggambarkan salah satu kabel yang Anda miliki. Kabel terdiri dari satu atau lebih garis putus-putus ( -), dengan colokan di kedua ujungnya. Sebuah plug selalu merupakan salah satu dari 8 karakter ()[]{}<>.
Jadi ini beberapa kabel yang valid:
>->
(--[
}-{
<-----]
(---)
Tapi ini bukan:
-->
(--
)--
[{
---
Saat menghubungkan kabel, hanya colokan dengan tipe braket yang sama persis yang dapat dihubungkan bersamaan.
Jadi ini beberapa koneksi kabel yang valid:
...---((---...
...---))---...
...---]]---...
...---{{---...
...---<<---...
Dan ini tidak valid:
...---()---...
...---)(---...
...---{]---...
...---{[---...
...---><---...
...--->)---...
Jika semua kabel dalam input dapat disusun ulang dan dilampirkan bersama dalam satu untai panjang, maka hasilkan untai itu ke stdout pada satu baris (dengan baris tambahan opsional). Ketika ada beberapa solusi, Anda dapat memilih salah satu dari mereka untuk dihasilkan. Jika membuat untai tunggal tidak dimungkinkan, maka tidak menghasilkan apa-apa (atau mengeluarkan string kosong dengan baris baru tambahan opsional).
Misalnya, jika inputnya adalah
[-->
{---]
>----{
outputnya bisa
[-->>----{{---]
di mana semua kabel dirangkai.
Namun jika inputnya adalah
[-->
{---]
kabel tidak dapat dihubungkan sehingga tidak akan ada output.
Perhatikan bahwa kabel dapat dibalik sebanyak yang diperlukan untuk membuat koneksi. mis [-->dan <--]secara efektif kabel yang sama karena mereka dapat membuat jenis koneksi yang sama. Beberapa output mungkin bergantung pada membalik kabel input.
Sebagai contoh
(-[
}--]
bisa memiliki output
(-[[--{
di mana kabel kedua dibalik, atau
}--]]-)
di mana kabel pertama dibalik.
(Perhatikan bahwa secara umum membalik seluruh output valid karena sama seperti membalikkan setiap kabel secara individual.)
Panjang kabel dalam output tentu saja harus sesuai dengan panjang kabel input yang sesuai. Tetapi kabel dapat disusun ulang dan diputar sebanyak yang Anda inginkan untuk membuat untai semua kabel. Input akan selalu mengandung setidaknya satu kabel.
Kode terpendek dalam byte menang.
Uji Kasus
Kasus dengan output:
[-->
{---]
>----{
gives
[-->>----{{---]
or
[---}}----<<--]
(-[
}--]
gives
(-[[--{
or
}--]]-)
(-)
gives
(-)
[--{
gives
[--{
or
}--]
[-]
]-[
gives
[-]]-[
or
]-[[-]
[----->
)------------[
{--<
}---)
could give
[----->>--}}---))------------[
or
>--}}---))------------[[----->
or
}---))------------[[----->>--}
or
{--<<-----]]------------((---{
etc.
>-->
>->
>--->
could give
>-->>->>--->
or
>--->>-->>->
or
>->>-->>--->
or
<--<<---<<-<
etc.
(-]
]->
>-}
}-)
)-[
[-<
<-{
{-(
could give
(-]]->>-}}-))-[[-<<-{{-(
or
{-((-]]->>-}}-))-[[-<<-{
or
<-{{-((-]]->>-}}-))-[[->
etc.
Kasing tanpa keluaran:
[-->
{---]
[-]
[-]
(-]
]->
}-)
>->
>-->
]---]
[-------------------]
]-------------------[
[-----------------]
[-----------------]
{--[
]--}
Jawaban:
Tidak dapat dibaca , 3924 byte
Ini adalah pertama kalinya saya menerapkan struktur mirip panggilan-tumpukan di Unreadable.
(Versi pertama ini adalah lebih dari 5300 byte, hanya untuk memberikan gambaran tentang seberapa banyak saya bermain golf ini.)
Penjelasan
Pertimbangkan contoh input ini:
Sepanjang sebagian besar eksekusi, rekaman itu ditata sebagai berikut:
Sel 0 hingga 5 adalah lokasi untuk berbagai variabel.
Sel 6 dan seterusnya berisi semua informasi tentang set kabel di kotak Anda:
Sel-sel yang tersisa setelah "zero terminator" berisi tumpukan. Setiap "stackframe" adalah sel tunggal yang menunjuk ke sel pertama kabel (sel "steker awal"). Dalam contoh di atas, ketika program memutuskan telah menemukan solusi, tumpukan akan berisi 6 (mengacu pada
>--{, kabel pertama) dan 21 (merujuk ke{---], cermin dari kabel kedua).Program ini berlangsung dalam tiga tahap utama:
Tahap pertama (baca input dan buat struktur kabel) hanya menggunakan sel # 1 (yang akan saya panggil
p) dan # 2 (yang akan saya panggilch) dan beroperasi dalam loop sementara sebagai berikut:Sementara kondisi: bertambah
p6, baca karakter berikutnya (mulai plug) ke dalam sel*p, dan periksa tidak-1(EOF).Baca karakter selanjutnya
*(p+2), dan hitung*(p+1), sampai kita menemukan apa pun selain-(tanda hubung). Pada titik itu,*(p+1)akan berisi jumlah tanda hubung (panjang kabel) dan*(p+2)karakter non-tanda hubung terakhir (steker akhir). (Kami juga menyalin karakter tanda hubung ke sel # 5 sehingga kami dapat mengakses kode ASCII ini nanti pada tahap output.)Dalam loop sementara, cari steker cermin dan simpan di
*(p+3), lalu tambahkanp2, hingga*pnol. Loopnya terlihat seperti ini di pseudocode:Loop ini akan selalu melakukan dua iterasi (steker awal dan steker akhir) dan menyimpan hasilnya di sel keempat dan keenam kabel ini. Sekarang, jika Anda memperhatikan, Anda menyadari bahwa sel keenam memang lokasi yang benar untuk steker ujung cermin, tetapi steker awal cermin ada di sel yang berlabel "boolean menunjukkan kabel asli". Ini OK karena kita hanya perlu sel ini menjadi nilai bukan nol.
Karena
pbaru saja bertambah total 4, sekarang menunjuk ke sel berlabel "kabel penunjuk boolean sedang digunakan". Setel*(p+3)ke nilai*(p-1). Ini menempatkan plug awal cermin di tempat yang tepat.Baca (dan buang) satu karakter lagi (yang kami harapkan menjadi baris baru, tetapi program tidak memeriksanya).
pawalnya dimulai pada 0 tetapi bertambah 6 di dalam kondisi while, dengan demikian data kabel dimulai pada sel # 6.pbertambah 4 di dalam badan loop, dan dengan demikian total 10 untuk setiap kabel, yang persis apa yang kita butuhkan.Selama tahap kedua, sel # 0-4 ditempati oleh variabel yang saya akan menelepon
a,p,q,m, dannotdone. (Sel # 5 masih mengingat kode ASCII dari tanda hubung.)Untuk bersiap-siap untuk tahap 2, kita perlu mengatur
*pkembali ke 0 (sel berlabel "zero terminator") sehingga dapat bertindak sebagai terminator untuk daftar kabel; kami juga mengaturq(yang merupakan penunjuk tumpukan kami) kep+1(yaitu sel setelah "nol terminator"; ini adalah tempat tumpukan dimulai);*qke 1 (item pertama di stack; mengapa 1 akan terlihat kemudian); dannotdoneke 1. Semua ini dilakukan dalam satu pernyataan:Tahap kedua juga loop sementara. Kondisinya sederhana
notdone. Dalam setiap iterasi loop sementara itu, salah satu dari empat hal berikut ini dapat terjadi:*qke kabel lain yang memenuhi syarat (yang kami segera tandai sebagai "sedang digunakan" bersama dengan kembarannya) dan kemudian berulang (yaitu membuat susunan kerangka baru).*qkarena tidak ada kabel yang memenuhi syarat lebih lanjut, jadi kami perlu melacak kembali (menghapus stackframe dan menandai kabel sebelumnya dan kembarannya sebagai tidak lagi "digunakan").*qkarena tidak ada kabel yang memenuhi syarat lebih lanjut dan kami tidak dapat mundur karena kami telah mencapai bagian bawah tumpukan. Ini berarti tidak ada solusi.Badan loop memeriksa masing-masing dari empat kondisi ini dalam urutan ini. Berikut detailnya:
Atur
mdanpke 1 dan dalam satu loop sementara, bertambahp5 (sehingga iterasi melalui kabel) dan periksa apakah*(p+4)("digunakan") diatur. Jika tidak, setelmke 0. Pada akhir lingkaran itu,mberi tahu kami jika semua kabel sedang digunakan. Jika demikian, aturnotdoneke 0 untuk mengakhiri loop utama. Jika tidak, lanjutkan pada langkah 2 di bawah ini.Setel
pke*q(kabel di bagian atas tumpukan) dan dalam beberapa saat mirip dengan yang di atas, tambahkanp5 untuk beralih melalui kabel. Mulai dari*qmemastikan kami hanya mempertimbangkan yang belum kami pertimbangkan sebelumnya; Namun, ingat bahwa nilai awal untuk stackframe baru adalah 1, jadi kabel pertama yang dilihat adalah yang ada di sel 6, yang memang merupakan kabel pertama.Untuk setiap kabel, kita perlu memeriksa
*(p+4)untuk memastikan bahwa itu belum digunakan, dan juga apakah*(q-1)nol (artinya kita berada di bagian bawah tumpukan, sehingga tidak ada kendala pada steker start), atau*p(kabel mulai steker) sama dengan*(*(q-1)+2)(steker ujung kabel tepat di bawah di atas tumpukan). Kami memeriksa kesetaraan dengan mengaturake*(*(q-1)+2)danmke*p+1dan kemudian menurunkan keduanya dalam loop sementara. Itu+1karenamdikurangi di dalam kondisi sementara, sehingga dikurangi sekali lagia. Jikaanol di akhir ini, kedua colokan sama.Dengan demikian, jika salah satu dari
*(q-1)nol atau perbandingan kesetaraan berhasil, kabel memenuhi syarat. Atur*quntukpmengganti kabel di bagian atas tumpukan dengan yang baru; setelmke yang sama untuk menunjukkan bahwa kami menemukan kabel yang cocok; dan kemudian penurunanp. Penurunan itu adalah sedikit trik untuk menyebabkan loop sementara (iterasi melalui kabel) berakhir lebih awal; ia akan bertambahp5 lagi, sehingga membawanya ke sel yang berisi bendera "sedang digunakan" kabel ini, dan kami tahu itu nol karena kami baru saja memeriksanya. Akhirnya, setelah perulangan kabel sementara loop, kami memeriksa apakahmtidak nol. Jika demikian, kami menemukan kabel yang cocok danpmenunjuk pada bendera "sedang digunakan" untuk kabel yang cocok itu. Setel ke 1 untuk menandainya sebagai sedang digunakan. Juga diatur*(*(p-1) ? p+5 : p-5)ke 1 untuk menandai kembarannya seperti yang digunakan. Akhirnya, tambahkanqdan atur yang baru*qke 1 untuk membuat bingkai stack baru.Jika, setelah perulangan kabel sementara loop, kami temukan
mmenjadi nol, tidak ada lagi kabel yang cocok, jadi kami perlu mundur. Penguranganquntuk turun ke tumpukan dan memeriksa apakah masih menunjuk pada kabel (nilai bukan nol). Jika demikian, tandai kabel dan kembarannya karena tidak lagi digunakan. (Kami menyimpan nilai*qdalampuntuk membuat ekspresi ini lebih pendek dalam kode.)Jika, setelah decrementing
q, kami menemukan bahwa itu menunjuk pada nilai nol, maka itu adalah "terminator nol", yang berarti kami telah menurunkan tumpukan. Kami menyimpulkan bahwa tidak ada solusi. Kami menetapkannotdoneke 0 untuk mengakhiri loop utama.Tahap ketiga adalah tahap keluaran. Ada dua hal yang bisa terjadi:
Mudahnya, jika tidak ada solusi,
padalah nol karena kami menyetelnya ke nilai*qsebelum memeriksa nol; dan jika ada adalah solusi,pmenunjuk pada “nol terminator” karena hanya mengulangi melalui kabel, sehingga kita sekarang dapat menggunakanpuntuk iterate melalui stack. Jadi cukup lakukan iterate melalui stack, mengeluarkan untuk setiap kabel plug start (*(*p)), tanda hubung (dengan mengurangi*(*p+1)dalam loop sementara; dan menggunakan kode ASCII tanda hubung yang disimpan dalam sel # 5), dan plug akhir (*(*p+2)). Tidak masalah bahwa ini menghancurkan informasi panjang kabel; kita tidak membutuhkan itu lagi.sumber
CJam, 67
Cobalah online
Catatan: tautan menggunakan kode terbaru dari repositori (didorong tetapi belum dirilis), karena berisi perbaikan bug.
Penjelasan:
Program hanya mencoba semua permutasi dan semua orientasi kabel.
sumber
(-] ]-> >-} }-) )-[ [-< <-{ {-(.JavaScript (ES6), 206
Fungsi rekursif
Lebih mudah dibaca
Uji
sumber
Javascript, 800 Bytes
Jauh dari solusi yang dioptimalkan, tapi inilah hack cepat bersama-sama dalam javascript (tidak ada ecma5 mewah atau apa pun, karena saya tidak mengetahuinya).
Tidak digabungkan, ini dia ... Saya yakin paling tidak 2 untuk loop tidak perlu di sini dan memeriksa untuk input elemen tunggal di bagian atas dan satu elemen yang cocok di bagian bawah adalah stanky ... tetapi tampaknya berfungsi dan memproses input uji.
sumber
s.charAt(x)===s[x]Python 3, 217 byte
( Demo pada Ideone )
sumber
(-] ]-> >-} }-) )-[ [-< <-{ {-(?Lua, 477 byte
Menerima tali sebagai argumen baris perintah
sumber
Python 3.5,
448432427424286311 byte:( +25 karena ada bug di mana output mungkin lebih lama dari seharusnya untuk beberapa input )
Bekerja dengan sempurna!
kecuali input dengan 7 atau lebih nilai. Butuh waktu lama bagi mereka, kemungkinan besar karena itu harus melalui semua permutasi input ditambah input terbalik . Saya akan mencoba untuk memperbaikinya jika dan ketika saya bisa, tetapi untuk sekarang, ini tampaknya cukup baik.Semuanya baik sekarang! Kalau saja saya entah bagaimana bisa menggunakantry-exceptblok itu dalam pemahaman daftar, itu bisa sedikit lebih pendek, dan terlihat jauh lebih bagus. Meskipun demikian, sekarang bekerja untuk semua kasus uji, dan, terbaik dari semua, ia menggunakan tidak ada impor! :)Cobalah online! (Ideone) (284 byte di sini)
(Kiat: Untuk mencobanya, cukup pilih "garpu", lalu masukkan pilihan Anda, pisahkan spasi , dan pilih "jalankan")
Penjelasan
Pada dasarnya, yang terjadi adalah ...
Bdibuat dari input dengan membaginya di spasi putih menjadi "kabel" komponennya.Madalah string yang saya buat yang, ketika dievaluasi, mengembalikan daftar berdasarkanByang berisi semua kabel, tapi kali ini mundur .Mpada akhirnya disatukan denganBdirinya sendiri untuk membuat daftarf,, dengan semua orientasi yang mungkin dari "kabel".ddibuat, yang akan diinisialisasi dengan nilai pertama (nilaif[0]) darif.diterasi melalui, dan karakter terakhir setiap nilai dibandingkan dengan karakter pertama dari setiap elemenf, dan ketika kecocokan ditemukan, karakter itu muncul (atau dihapus) dan dikembalikan dari daftarf. Ini terjadi sampai aIndexErrordinaikkan, atau panjang daftardmelebihiBdan aNameErrordinaikkan setelah panggilan keE, keduanya ditangani, dan kemudiandisi daftar digabungkan ke dalam string dan dikembalikan selama panjang daftardlebih dari atau sama dengan panjang daftarB. Jika tidak, string kosong dikembalikan (''), karenadtidak sama panjang denganBmenandakan bahwa semua "kabel" dalam daftarBtidak bisa digabung menjadi satu "kabel" panjang.sumber
<!-- language: lang-python -->. Apa yang berubah?