Tantangan
Anda diberi dua string bit berbeda dengan panjang yang sama. (Misalnya, 000
dan 111
.) Tujuan Anda adalah menemukan jalur dari satu ke yang lain sehingga:
- Pada setiap langkah, Anda mengubah hanya satu bit (Anda dapat pergi dari
000
ke salah001
,010
,100
). - Anda tidak dapat mengunjungi string bit yang sama dua kali.
- Jalan itu selama mungkin, di bawah kendala-kendala ini.
Misalnya, beralih dari 000
ke 111
, kita dapat mengambil jalan
000, 001, 011, 010, 110, 100, 101, 111
yang mengunjungi semua string 8 bit dengan panjang 3, sehingga harus menjadi yang terpanjang yang mungkin.
Aturan
- Celah standar berlaku.
- Anda dapat mengambil input sebagai dua string nol dan satu, atau dua array nol dan satu, atau sebagai dua array nilai boolean.
- Anda tidak boleh mengambil input sebagai dua bilangan bulat dengan representasi biner yang tepat (menulis
000
dan111
sebagai0
dan7
tidak valid). - Jika Anda mau, Anda bisa menggunakan panjang string bit sebagai input.
- Program Anda diizinkan untuk mengeluarkan lintasan dengan mencetak string bit yang dikunjungi satu per satu, atau dengan mengembalikan array string bit yang dikunjungi (masing-masing dalam format yang sama dengan input).
- Output Anda harus mencakup awal dan akhir jalur (yang merupakan input Anda).
- Ini adalah kode-golf , kode terpendek dalam byte yang menang.
Contohnya
0 1 -> 0, 1
10 01 -> 10, 00, 01 or 10, 11, 01
000 111 -> any of the following:
000, 100, 110, 010, 011, 001, 101, 111
000, 100, 101, 001, 011, 010, 110, 111
000, 010, 110, 100, 101, 001, 011, 111
000, 010, 011, 001, 101, 100, 110, 111
000, 001, 101, 100, 110, 010, 011, 111
000, 001, 011, 010, 110, 100, 101, 111
1001 1100 -> 1001, 0001, 0000, 0010, 0011, 0111, 0101, 0100, 0110, 1110, 1010, 1011, 1111, 1101, 1100 (other paths exist)
code-golf
binary
graph-theory
Misha Lavrov
sumber
sumber
Jawaban:
Sekam ,
27 2624 byteBrute force, jadi sangat lambat. Cobalah online!
Penjelasan
Sekam membaca secara alami dari kanan ke kiri.
sumber
Mathematica, 108 byte
Memasukkan:
Keluaran:
sumber
Mathematica, 175 byte
Pertanyaan pertama yang bagus!
Memasukkan
sumber
Haskell ,
212207 byteIni mungkin terlalu lama, tetapi akhirnya berhasil sekarang. (Terima kasih kepada @Lynn untuk trik produk kartesian !) Thansk @nimi untuk -5 byte!
Cobalah online!
Penjelasan:
sumber
x<-mapM id$[1>0,1<0]<$b
[True,False]
? Jika[False,True]
juga berfungsi, Anda bisa menggunakannya[0>1..]
.Bool
adalahEnum
, dan aku lupa bahwa<$
tersedia (pertama kali mencoba*>
yang tidak di Prelude)!Mathematica
116114 byteDengan beberapa byte tersimpan berkat Misha Lavrov.
Input (8 dimensi)
Output (panjang = 254, setelah 1,82 detik)
Tuples[{0,1},{l=Length@#}],{2}]
& menghasilkan angka 0 ... 8 sebagai daftar biner.Bagian luar
Tuples...{2}
menghasilkan semua pasangan nomor biner yang dipesan.Plus@@x
jumlah masing-masing pasangan, menghasilkan kembar tiga dari 0, 1.Cases....Count[Plus@@x, 1]==1
mengembalikan semua jumlah yang mengandung satu 1. Ini muncul ketika dua angka biner asli dihubungkan oleh satu sisi.Rules
menghubungkan simpul grafik, setiap simpul menjadi angka biner.Graph
membuat grafik yang sesuai dengan simpul dan tepi tersebut.FindPath
menemukan hingga 2 ^ n jalur yang menghubungkan titik a ke titik b, angka yang diberikan.Last
mengambil jalan terpanjang dari ini.Untuk tiga dimensi, grafik dapat direpresentasikan dalam bidang seperti yang ditunjukkan di sini:
Untuk input,
{0,0,0}, {1,1,1}
berikut ini adalah output:{{{0, 0, 0}, {0, 0, 1}, {0, 1, 1}, {0, 1, 0}, {1, 1, 0}, {1, 0, 0}, {1, 0, 1}, {1, 1, 1}}}
Jalur ini dapat ditemukan dalam grafik di atas.
Itu juga dapat dipahami sebagai jalur berikut dalam 3-ruang, di mana setiap titik berhubungan dengan suatu titik
{x,y,z}
. {0,0,0} mewakili asal dan {1,1,1} mewakili titik "berlawanan" dalam satuan kubus.Jadi jalur solusi sesuai dengan traverse tepi di sepanjang unit kubus. Dalam hal ini, jalannya adalah Hamiltonian: ia mengunjungi setiap simpul satu kali (yaitu tanpa penyeberangan dan tidak ada simpul dihilangkan).
sumber
2^(l+2)
di kode Anda?Haskell ,
141123 byteMenggunakan daftar bilangan bulat. Cobalah online!
Penjelasan
Fungsi utamanya adalah
!
, dan fungsi bantu adalah#
danc
. Diberikan daftar bit,c
berikan semua cara yang memungkinkan untuk membalik salah satunya, misalnya[0,1,1] -> [[1,1,1],[0,0,1],[0,1,0]]
.Fungsi
#
mengambil daftar daftar ("memori") dan daftar ("bitstring awal"). Itu membangun semua jalur hypercube yang dimulai dengan elemen awal, hanya mengandung bitstring yang berbeda, dan tidak menginjak string dalam memori.Fungsi utama
!
mengikat semuanya. Trik yang saya gunakan di sini adalahp*>x
(x
berulanglength p
kali) alih-alihlength p
. Karena pengulangan yang lebih lamax
datang kemudian dalam urutan alami daftar,maximum
memilih jalur terpanjang dalam kedua kasus, karena koordinat pasangan pertama dibandingkan sebelum yang kedua.sumber
Jelly ,
2527 byte+2 byte untuk memperbaiki bug dengan golf saya :( mudah-mudahan saya akan menemukan cara yang lebih pendek.
Program lengkap yang menggunakan bit-string menggunakan
1
dan2
* sebagai daftar. Argumennya adalahfrom
danto
. Program ini mencetak daftar daftar yang sama.*
0
dan1
dapat digunakan sebagai pengganti byte (tambahkan’
antaraL2ṗ
danŒ!ç€...
untuk pengurangan).Cobalah online!
Bagaimana?
memperbarui ...
sumber
[1,1]
dan[2,2]
menghasilkan output[[1, 1], [2, 1], [1, 2], [2, 2]]
ketika saya Coba Online, yang bukan jalur yang valid.