Tantangan
Tantangan ini akan memiliki Anda menulis sebuah program yang mengambil dua bilangan bulat n
dan m
dan output jumlah non-berpotongan loop pada n
oleh m
torus yang dibuat oleh mulai (0,0)
dan hanya mengambil langkah-langkah ke atas dan ke kanan. Anda dapat menganggap torus sebagai kisi-kisi dengan sampul di bagian atas dan bawah serta di samping.
Ini adalah kode-golf sehingga byte paling sedikit menang.
Contoh
Misalnya, jika inputnya adalah n=m=5
, satu jalan valid adalah
(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3) -> (2,4) ->
(2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) ->
(0,3) -> (1,3) -> (1,4) ->
(1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) -> (3,4) -> (4,4) ->
(0,4) -> (0,0)
seperti yang ditunjukkan pada gambar.
Beberapa contoh input / output
f(1,1) = 2 (up or right)
f(1,2) = 2 (up or right-right)
f(2,2) = 4 (up-up, up-right-up-right, right-right, right-up-right-up)
f(2,3) = 7
f(3,3) = 22
f(2,4) = 13
f(3,4) = 66
f(4,4) = 258
code-golf
combinatorics
grid
topology
Peter Kagey
sumber
sumber
Jawaban:
Jelly , 28 byte
Tautan monadik yang menerima daftar
[m,n]
,, yang menghasilkan hitungan.TIO-jt1qe1v9 ... meskipun ada sedikit gunanya, itu terlalu tidak efisien.
(Saya bahkan tidak bisa menjalankan
[2,3]
secara lokal dengan ram 16GB)!Bagaimana?
Brute force - menciptakan koordinat versi ubin yang cukup besar kemudian menyaring set daya dari titik-titik ini ke jalur dengan tetangga hanya meningkat satu per satu arah, kemudian menyaring mereka yang mulai dari koordinat minimal (yaitu asal) dan, pada saat yang sama, hapus koordinat awal ini dari masing-masing. Kemudian gunakan modulo aritmatika untuk membungkus kembali ke torus dan menyaring semua yang mengandung koordinat duplikat (yaitu yang mengandung persimpangan) dan, akhirnya, menyaring mereka yang memiliki koordinat akhir minimal (yaitu berakhir kembali pada titik asal) dan menghasilkan panjang hasil.
sumber
Python 2 , 87 byte
Cobalah online!
Yang menarik di sini adalah menggunakan bilangan kompleks
z
untuk menyimpan koordinat posisi saat ini. Kita dapat naik dengan menambahkan1
dan bergerak ke kanan dengan menambahkan1j
. Yang mengejutkan saya, modulo bekerja pada bilangan kompleks dengan cara yang memungkinkan kita menangani pembungkus untuk setiap dimensi secara terpisah: melakukan%m
tindakan pada bagian nyata, dan%(n*1j)
bertindak pada bagian imajiner.sumber
k:=x+y*m
. Itu membuat saya bertanya-tanya apakah akan lebih pendek untuk digunakank
secara langsung untuk(x,y)
, menggunakanx+y*m
daripadax+y*1j
. Sayang sekali Python 3 tidak memungkinkan modulus kompleks.JavaScript (ES6), 67 byte
Mengambil input sebagai
(m)(n)
.Cobalah online!
Untuk membuatnya bekerja untuk input apa pun, kita bisa menggunakan BigInts untuk 73 byte :
Cobalah online!
JavaScript (ES6),
76 7372 byteMengambil input sebagai
(m)(n)
.Cobalah online!
Berkomentar
sumber
Haskell,
8880 byteCobalah online!
Simple brute force: coba semua kombinasi atas / kanan, menjatuhkan yang berpotongan (kami menjaga semua posisi yang kami kunjungi dalam daftar
a
) dan menghitung yang akhirnya mengenai posisi(0,0)
lagi.Kasus dasar dari rekursi adalah ketika kami mengunjungi posisi untuk kedua kalinya (
elem(x,y)a
). Hasilnya adalah0^0
=1
ketika posisi adalah(0,0)
dan diperhitungkan terhadap jumlah loop atau0
(0^x
, denganx
non-nol) sebaliknya dan tidak menambah jumlah loop.Edit: -8 byte terima kasih kepada @xnor.
sumber
|elem(x,y)a=0^(x+y)
, dan(0!0)[]
dapat0!0$[]
.Jelly , 44 byte
Cobalah online!
sumber
Java 8, 120 byte
Cobalah online.
sumber
CJam (50 karakter)
Demo online . Ini adalah program yang mengambil dua input dari stdin.
Akhirnya kami punya jawaban untuk pertanyaan itu
Pembedahan
sumber
Jelly ,
5439 byteCobalah online!
Saya telah memposting ini sebagai jawaban terpisah untuk Jelly saya yang lain karena ini adalah metode yang sama sekali berbeda. Ini pada prinsipnya lebih dekat dengan jawaban @ Arnauld. Ini menggunakan fungsi rekursif yang bekerja melalui setiap jalur yang mungkin sampai mencapai titik yang sudah harus, dan kemudian mengembalikan hasil pemeriksaan apakah itu kembali ke awal. Saya menduga beberapa byte lagi bisa dicukur. Sekarang diubah menjadi menggunakan operator slice. Ini bekerja dengan baik hingga 5x5. Kedalaman rekursi harus paling banyak mx n.
sumber