Latar Belakang
Sebuah jaringan segitiga adalah grid yang dibentuk oleh ubin pesawat secara teratur dengan segitiga sama sisi dengan panjang sisi 1. Gambar di bawah adalah contoh dari grid segitiga.
Sebuah titik kisi segitiga adalah titik dari segitiga membentuk grid segitiga.
The asal adalah titik tetap di pesawat, yang merupakan salah satu poin kisi segitiga.
Tantangan
Dengan bilangan bulat non-negatif n
, temukan jumlah titik kisi segitiga yang jarak Euclidean dari titik asal kurang dari atau sama dengan n
.
Contoh
Gambar berikut adalah contoh untuk n = 7
(hanya menampilkan area 60 derajat untuk kenyamanan, dengan titik A sebagai asal):
Uji Kasus
Input | Output
---------------
0 | 1
1 | 7
2 | 19
3 | 37
4 | 61
5 | 91
6 | 127
7 | 187
8 | 241
9 | 301
10 | 367
11 | 439
12 | 517
13 | 613
14 | 721
15 | 823
16 | 931
17 | 1045
18 | 1165
19 | 1303
20 | 1459
40 | 5815
60 | 13057
80 | 23233
100 | 36295
200 | 145051
500 | 906901
1000 | 3627559
Petunjuk : Urutan ini bukan OEIS A003215 .
Aturan
Aturan standar untuk kode-golf berlaku. Pengajuan terpendek menang.
Harap sertakan bagaimana Anda memecahkan tantangan dalam kiriman Anda.
n
, sehingga memiliki istilah dua kali lebih banyak dari yang Anda inginkan.n^2+1
ketentuan pertama OEIS A004016 .Jawaban:
Python 2 , 43 byte
Cobalah online!
Ini adalah ilmu hitam.
Menawarkan 250 rep untuk bukti tertulis.Lihatjawaban Lynnuntuk bukti dan penjelasan.sumber
Haskell , 48 byte
Cobalah online!
Menggunakan rumus "ilmu hitam" xnor:
Bukti kebenarannya, dan penjelasan tentang bagaimana xnor berhasil mengekspresikannya dalam 43 byte Python, dapat ditemukan di sini .
sumber
Bahasa Wolfram (Mathematica) ,
535150 byte-1 byte terima kasih kepada @miles
Cobalah online!
Bagaimana?
Alih-alih berpikir dalam hal ini:
Pikirkan seperti ini:
Jadi kami menerapkan matriks
[[sqrt(3)/2, 0], [1/2, 1]]
transformasi untuk mengubah gambar kedua ke yang pertama.Kemudian, kita harus menemukan lingkaran di kotak segitiga dalam hal koordinat Cartesian.
Jadi kami menemukan poin kisi
x, y
sedemikian rupax^2 + x y + y^2 <= r^2
Misalnya, dengan
r = 3
:sumber
x^2+x y+y^2
juga bisa berasal dari Hukum Cosinus dengan 120 derajat.x^2+x y+y^2
->x(x+y)+y^2
menyimpan bytex^2 + xy + y^2
juga dapat diturunkan dari norma bilangan bulat Eistenstein, yaitua^2 - ab + b^2
. Perhatikan bahwa tandaa
danb
tidak relevan kecuali dalam istilahab
sehingga memiliki jumlah solusi yang sama.Bahasa Wolfram (Mathematica) , 48 byte
Berdasarkan OEIS A004016 .
Cobalah online!
sumber
CJam (24 byte)
Ini adalah blok anonim (fungsi) yang mengambil satu argumen di stack dan meninggalkan hasilnya di stack. Test suite online . Perhatikan bahwa dua case terbesar terlalu lambat.
Penjelasan
alephalpha mencatat dalam komentar pada pertanyaan itu
Bukti saya tentang kebenaran formula itu didasarkan pada beberapa informasi yang diperoleh dari tautan OEIS alephalpha:
Diseksi kode
sumber
J , 27 byte
Cobalah online!
Berdasarkan metode JungHwan Min .
Penjelasan
sumber
APL (Dyalog Classic) , 23 byte
Cobalah online!
upeti kepada xnor ini dan lynn ini jawaban
tes terakhir dikomentari karena membutuhkan lebih banyak memori, misalnya
MAXWS=200M
dalam envsumber
Jeli , 14 byte
Penggunaan metode @ JungHwanMin .
Cobalah online!
sumber
Jelly ,
1513 byte-2 terima kasih kepada Dennis (hanya menambah kuadrat untuk menghindari penggabungan nol; hindari kepala dengan menggunakan modulo-slice post-difference daripada slice pra-perbedaan)
Menggunakan metode "ilmu hitam" untuk mengasah pada jawaban yang diekspos oleh xnor dalam jawaban Python mereka , tetapi menggunakan iterasi daripada rekursi (dan sedikit perhitungan kurang)
Tautan monadik yang menerima bilangan bulat non-negatif dan mengembalikan bilangan bulat positif.
Cobalah online! Atau lihat test-suite .
Bagaimana?
sumber
JavaScript (ES6), 65 byte
Ini adalah port dari solusi @ JungHwanMin .
Cobalah online!
Jawaban asli (ES7), 70 byte
Cukup berjalan melalui grid dan menghitung poin yang cocok.
Cobalah online!
sumber
true
bukan1
; 46 jika kita juga integer-bagi). Dan saya tidak tahu JavaScript cukup baik untuk golf divisi-integer~~(a/b)
, tapi saya yakin ada cara yang lebih pendek untuk mereka juga ..Java 8, 65 byte
Port jawaban @xnor dari Python 2 .
Cobalah online.
sumber
Pari / GP , 42 byte
Menggunakan built-in
qfrep
.Cobalah online!
sumber
C # (Visual C # Interactive Compiler) , 68 byte
Cobalah online!
Sama seperti orang lain, sayangnya. Saya tahu mungkin ada cara yang lebih baik untuk menulis ini, tetapi menyatakan dan memanggil lambda pada saat yang sama dalam c # bukanlah sesuatu yang saya lakukan, yah, pernah. Meskipun dalam pembelaan saya, saya tidak bisa memikirkan alasan yang bagus (di luar kode golf, tentu saja) untuk melakukannya. Namun, jika seseorang tahu bagaimana Anda bisa melakukan ini, beri tahu saya dan / atau mencuri kreditnya, saya kira.
sumber
Bahasa Wolfram (Mathematica) , 39 byte
Cobalah online!
Menggunakan transformasi koordinat JungHwan Min dan hanya menghitung solusi atas bilangan bulat.
sumber
05AB1E , 15 byte
Port of @JonathanAllan 's Jelly answer , yang pada gilirannya merupakan turunan dari rumus 'ilmu hitam' @ xnor .
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
sumber