Bergerak tunggal
Papan adalah kotak persegi 2 dimensi tanpa batas, seperti papan catur tanpa batas. Sepotong dengan nilai N ( penggerak N) ) dapat bergerak ke bujur sangkar mana saja yang berjarak tepat dari akar kuadrat N dari bujur sangkar saat ini (jarak Euclidean diukur dari pusat ke pusat).
Sebagai contoh:
- Penggerak 1 dapat bergerak ke bujur sangkar mana saja yang berdampingan secara horizontal atau vertikal
- Penggerak 2 dapat bergerak ke bujur sangkar mana saja yang berdekatan secara diagonal
- Penggerak 5 bergerak seperti ksatria catur
Perhatikan bahwa tidak semua pemindah N dapat bergerak. Penggerak 3 tidak pernah dapat meninggalkan kuadrat saat ini karena tidak ada kuadrat di papan yang berjarak persis akar 3 dari kuadrat saat ini.
Bergerak ganda
Jika dibiarkan bergerak berulang kali, beberapa bagian dapat mencapai bujur sangkar apa saja di papan tulis. Misalnya, penggerak 1 dan penggerak 5 dapat melakukan hal ini. Penggerak 2 hanya bisa bergerak secara diagonal dan hanya bisa mencapai setengah dari kotak. Sepotong yang tidak bisa bergerak, seperti penggerak 3, tidak dapat mencapai salah satu kotak ( kotak awal tidak dihitung sebagai "tercapai" jika tidak ada gerakan terjadi) .
Gambar menunjukkan kotak mana yang bisa dijangkau. Lebih detail tentang hover. Klik untuk gambar yang lebih besar.
- Kotak yang dapat dijangkau dalam 1 atau lebih gerakan ditandai dengan warna hitam
- Kotak yang dapat dijangkau dengan tepat 1 gerakan ditunjukkan oleh potongan merah
(terlepas dari penggerak 3, yang tidak dapat bergerak)
Berapa proporsi papan yang bisa dicapai oleh N-mover?
Memasukkan
- Bilangan bulat positif N
Keluaran
- Proporsi dewan yang dapat dijangkau oleh penggerak-N
- Ini adalah angka dari 0 hingga 1 (keduanya termasuk)
- Untuk tantangan ini, output sebagai fraksi dalam istilah terendah, seperti 1/4, diperbolehkan
Jadi untuk input 10
, baik 1/2
dan 0.5
adalah output diterima. Output sebagai pembilang dan penyebut yang terpisah juga dapat diterima, termasuk bahasa yang tidak mendukung pecahan atau pecahan. Misalnya, 1 2
atau [1, 2]
.
Untuk output integer (0 dan 1), salah satu dari yang berikut ini adalah format yang dapat diterima:
- Untuk 0:
0
,0.0
,0/1
,0 1
,[0, 1]
- untuk 1:
1
,1.0
,1/1
,1 1
,[1, 1]
Mencetak gol
Ini kode golf. Skor adalah panjang kode dalam byte. Untuk setiap bahasa, kode terpendek menang.
Uji kasus
Dalam format input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
sumber
Jawaban:
JavaScript (Node.js) ,
144138125747370 byteCobalah online!
-4 byte terima kasih @Arnauld!
Pendekatan asli, 125 byte
Cobalah online!
Terinspirasi oleh video Pi bersembunyi dalam keteraturan prima oleh 3Blue1Brown.
Lipat gandakan semua nilai fungsi itu, ini dia.
Memperbarui
Berkat upaya kontributor dari Math.SE, algoritme sekarang didukung oleh bukti
sumber
Mathematica, 80 byte
Kode ini sebagian besar bergantung pada teorema matematika. Ide dasarnya adalah bahwa kode meminta kepadatan kisi yang diberikan beberapa set pembangkit.
Lebih tepatnya, kita diberi beberapa koleksi vektor - yaitu, mereka yang panjangnya kuadrat adalah N - dan diminta untuk menghitung kepadatan himpunan jumlah yang mungkin dari vektor-vektor ini, dibandingkan dengan semua vektor bilangan bulat. Matematika yang dimainkan adalah kita selalu dapat menemukan dua vektor (dan kebalikannya) yang "menghasilkan" (yaitu jumlah penjumlahannya) sama dengan kumpulan aslinya. LatticeReduce melakukan hal itu.
Jika Anda hanya memiliki dua vektor, Anda dapat membayangkan menggambar jajaran genjang identik yang berpusat pada setiap titik yang dapat dijangkau, tetapi yang panjang tepinya adalah vektor yang diberikan, sehingga bidang tersebut benar-benar ubin oleh jajaran genjang ini. (Bayangkan, misalnya, kisi bentuk "berlian" untuk n = 2). Luas setiap jajar genjang adalah penentu dari dua vektor penghasil. Proporsi yang diinginkan dari pesawat adalah kebalikan dari area ini, karena setiap jajaran genjang hanya memiliki satu titik yang dapat dijangkau di dalamnya.
Kode adalah implementasi yang cukup mudah: Hasilkan vektor, gunakan LatticeReduce, ambil determinan, lalu ambil resiprokal. (Tapi mungkin bisa bermain golf lebih baik)
sumber
d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
Bersih ,
189185172171 byteCobalah online!
Temukan setiap posisi yang dapat dijangkau dalam
n
kuadrat sisi panjang terpojok pada asal di kuadran pertama, lalun^2
bagi dengan membagi untuk mendapatkan bagian dari semua sel yang bisa dijangkau.Ini berfungsi karena:
n
bujur sangkar panjang ini, masing-masing terpojok pada titik yang dapat dijangkau dari asal seolah-olah itu adalah asal.++ +- -+ --
, memungkinkan ubin yang tumpang tindih diperpanjang melalui tiga kuadran lainnya dengan mirroring dan rotasi.sumber
Retina 0.8.2 ,
12682 byteCobalah online! Tautan termasuk kasus uji. Penjelasan:
Konversikan ke unary.
Membagi berulang kali dengan faktor-faktor utama formulir
4k+1
.Jika hasilnya bukan kotak atau dua kali kotak maka hasilnya adalah nol.
Hitung timbal balik sebagai pecahan desimal.
sumber
Regex (ECMAScript, timbal balik),
256163157948382 byte-93 bytes terima kasih kepada Neil
-6 bytes terima kasih lagi untuk Neil
-63 bytes dengan melakukan pembagian tanpa menangkap pembagi
-11 byte terima kasih kepada Grimy opsional opsional-divisi-oleh-konstanta dan akar kuadrat
-1 byte dengan menggerakkan kondisi pertandingan akhir dan mengembalikan tangkapan nilai ke dalam loop sebagai alternatif kedua, terima kasih kepada Grimy
Ini menggunakan matematika yang sama dengan jawaban JavaScript Shieru Asakoto .
Masukannya di unary. Karena regex murni hanya dapat kembali sebagai output substring dari input (yaitu bilangan alami kurang dari atau sama dengan input), atau "tidak cocok", regex ini mengembalikan kebalikan dari proporsi papan yang penggerak N-penggerak dapat meraih. Karena kebalikan dari 0 adalah tak terhingga, ia mengembalikan "tidak cocok" dalam kasus itu.
PERINGATAN SPOILER : Untuk akar kuadrat, regex ini menggunakan varian dari algoritma multiplikasi umum, yang tidak jelas dan bisa menjadi teka-teki yang bermanfaat untuk Anda kerjakan sendiri. Untuk informasi lebih lanjut, lihat penjelasan untuk bentuk algoritma ini di Temukan nomor Rocco .
^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1
Cobalah online!
Cobalah online! (hanya kasus uji)
Regex (ECMAScript + (? *), Output timbal balik),
207138132byteUsang dengan melakukan pembagian tanpa menangkap pembagi (yaitu sekarang identik dengan yang di atas).
Regex (ECMAScript 2018, output timbal balik),
212140134byteUsang dengan melakukan pembagian tanpa menangkap pembagi (yaitu sekarang identik dengan yang di atas).
Regex (ECMAScript, output fraksi), 80 byte
Dalam versi ini, pembilang dikembalikan dalam
\10
(nol jika tidak disetel / NPCG) dan penyebut dalam\7
.Berbeda dengan versi keluaran timbal balik:
Kelemahan besar dari spesifikasi keluaran seperti ini adalah tidak terdapat dalam program itu sendiri.
((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)
Cobalah online!
Cobalah online! (hanya kasus uji)
sumber
(((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)
untuk memeriksa apakah N atau N / 2 adalah bujur sangkar.Jelly ,
2524 byteTautan monadik menggunakan rute faktor utama.
Cobalah online!
Bagaimana?
25 sebelumnya adalah:
Forcer brute program penuh
;kodemungkinlebih lamadari rute faktor utama (saya mungkin akan mencoba nanti).Cobalah online!
Mulai dengan menciptakan gerakan tunggal sebagai koordinat kemudian berulang kali bergerak dari semua lokasi mencapai mengumpulkan hasil, mengambil modulo
n
masing-masing koordinat (untuk membatasi ken
olehn
kuadran) dan menjaga orang-orang yang berbeda sampai titik tetap tercapai; lalu akhirnya membagi hitungan dengann^2
sumber
05AB1E ,
272625 bytePort dari jawaban JavaScript @ShieruAsakoto , jadi pastikan untuk menambahkannya juga!
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
sumber
APL (Dyalog Extended) , 21 byte
Program ini menggunakan rute faktor utama. Saya berhutang budi kepada Adám, dzaima, H.PWiz, J.Sallé, dan ngn. APL Orchard adalah tempat yang tepat untuk belajar APL dan mereka selalu bersedia membantu
Cobalah online!
Tidak melakukanolf
Bagian 2 dari kode ini sama dengan dalam versi Dyalog Unicode di bawah ini, dan dalam penjelasan ini, saya akan fokus pada
⍭*1≠4|⍭
APL (Dyalog Unicode) ,
41403635 byte SBCSProgram ini menggunakan rute faktor utama. Belajar beberapa trik saat menulis ini dan saya sangat berhutang budi kepada Adám, dzaima, H.PWiz, J.Sallé, dan ngn. APL Orchard adalah tempat yang tepat untuk belajar APL dan mereka selalu bersedia membantu (atau posting ini tidak akan pernah turun :)
Sunting: -1 byte dari ngn. -2 byte dari Adám dan -2 lebih banyak dari ngn. -1 byte dari ngn.
Cobalah online!
Tidak melakukanolf
Ini adalah program dalam dua bagian:
sumber