Baru-baru ini saya membaca tentang teori grafik, terutama hypercubes dan memikirkan cara-cara menarik untuk membangun jalur padanya. Inilah yang saya pikirkan.
Seperti yang mungkin Anda ketahui, Anda dapat membuat hypercube n-dimensional dengan mengambil semua n-tuple yang terdiri dari 1
dan 0
sebagai simpul dan menghubungkannya, jika mereka berbeda dalam satu digit. Jika Anda menginterpretasikan digit biner ini sebagai angka integer, Anda berakhir dengan grafik dengan simpul numerik yang baik. Misalnya untuk n=3
:
Katakanlah Anda ingin berjalan-jalan di hypercube ini dan mulai dari titik awal 0
. Sekarang, bagaimana Anda menentukan titik mana yang ingin Anda kunjungi selanjutnya? Aturan yang saya buat adalah mengambil jumlah a
vertex tempat Anda berada, balikkan mod(a,n)
bitnya (pengindeksan berbasis nol) dan buka vertex yang dihasilkan. Secara formal aturan ini dapat didefinisikan secara rekursif sebagai
a[m+1] = xor(a[m], 2^mod(a[m],n)).
Dengan mengikuti aturan ini, Anda akan selalu tetap di kubus dan melakukan perjalanan di sepanjang tepi. Jalur yang dihasilkan terlihat seperti ini
Seperti yang Anda lihat, Anda akan berjalan dalam lingkaran! Bahkan, di semua dimensi dan untuk semua titik awal, jalur Anda akan berakhir dalam satu lingkaran. Misalnya untuk n=14
dan a[0]=0
terlihat seperti ini
Bagi seorang ambler yang rajin, panjang rute yang direncanakannya adalah informasi yang sangat penting. Jadi, tugas Anda adalah menulis fungsi atau program yang mengambil dimensi hypercube sebagai n
titik awal a[0]
sebagai input dan menampilkan jumlah simpul dalam loop yang dihasilkan.
Uji kasus
n a[0] Output
-----------------
3 0 6
14 0 50
5 6 8
17 3 346
Aturan
- Celah standar dilarang
- Output / Input dapat dalam format yang sesuai
- Anda mungkin menganggap
a[0]
sebagai simpul yang valid
Mencetak gol
Kode terpendek dalam byte menang.
Jika Anda memiliki informasi tambahan tentang topik ini, saya akan senang mendengarnya!
sumber
a[m+1] = xor(a[m], 2^mod(a[m],n))
, itu tidak relevan jika simpul milik hypercube, kan?a[m]
berada di hypercube,a[m+1]
akan terlalu. Dan karena Anda dapat menganggapa[0]
sebagai simpul yang valid, Anda tidak perlu peduli tentang hal-hal hypercube dan cukup ikuti aturannya.Jawaban:
Jelly, 9 byte
Membawa dua argumen baris perintah.
Coba di sini .
sumber
Haskell, 124
Ini menemukan lingkaran oleh algoritma dua-pointer-going-around-in-berbeda-kecepatan, dan sangat menggunakan / menyalahgunakan pendekatan Haskell untuk daftar (misalnya, kedua pointer sebenarnya daftar).
g
adalah fungsi yang menghitung jawabannya. berikann
dan kemudiana[0]
dan itu akan mengembalikan nomor kepada Anda (catatan yangn
harus didefinisikan sebagai tipeInt
untuk menghindari tipe ambiguitas).sumber
JavaScript (ES6), 69 byte
Pengembalian 18812 untuk (23, 10).
sumber
MATL ,
383728 byteIni berfungsi dalam versi bahasa saat ini (15.0.0) .
Cobalah online !
Penjelasan
sumber
Pyth,
2217 bytePenjelasan:
Coba di sini .
sumber