Definisi

"Segitiga integer" adalah yang memiliki koordinat integer. Misalnya segitiga berikut adalah segitiga integer:

(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650.

Tugas

Tujuan dari tantangan ini adalah untuk menghitung semua segitiga integer (hingga kongruensi) dengan perimeter kurang dari n.

Masukan dan keluaran

Argumen akan diberikan sebagai bilangan bulat, dan output harus berupa jumlah segitiga dengan perimeter yang benar-benar kurang dari argumen.

Contohnya

Segitiga integer terkecil dengan perimeter sebangun dengan

(0, 0), (0, 1), (1, 0) which has perimeter 2 + sqrt(2) ≈ 3.414

Yang terkecil berikutnya adalah:

(0, 0), (0, 1), (1, 2) with perimeter 1 + sqrt(2) + sqrt(5) ≈ 4.650,
(0, 0), (0, 2), (1, 1) with perimeter 2 + 2sqrt(2)          ≈ 4.828,
(0, 0), (0, 2), (1, 0) with perimeter 3 + sqrt(5)           ≈ 5.236, and
(0, 0), (1, 2), (2, 1) with perimeter sqrt(2) + 2sqrt(5)    ≈ 5.886

Kasus uji:

a(1) = 0
a(2) = 0
a(3) = 0
a(4) = 1
a(5) = 3
a(6) = 5
a(7) = 11
a(8) = 18
a(9) = 29
a(10) = 44
a(12) = 94
a(20) = 738
a(30) = 3756
a(40) = 11875

Saya memiliki koordinat untuk masing-masing segitiga di Intisari ini .

Peringatan

Perhatikan bahwa dua segitiga yang tidak kongruen dapat memiliki perimeter yang sama:

(0, 0), (0, 3), (3, 0) and (0, 0), (0, 1), (3, 4) both have perimeter 6 + 3sqrt(2).

Juga perlu diingat bahwa ketimpangan itu ketat ; segitiga 3-4th pythagoras harus dihitung dengan (13), bukan (12).

Mencetak gol

Ini adalah kode-golf — kode terpendek menang!

Jelly , 28 27 25 23 byte

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S

Cobalah online!

Bagaimana itu bekerja

pḶŒcÆḊÐfḅı;I$€AṢ€QS€<¹S  Main link. Argument: n

 Ḷ                       Unlength; yield [0,...,n-1].
p                        Take the Cartesian product of [1,...,n] and [0,...,n-1].
  Œc                     Take all combinations of the resulting pairs.
                         The result are of the form [[a, b], [c, d]].
    ÆḊÐf                 Filter by determinant; keep only pairs of pairs for which
                         the determinant (ad - bc) is non-zero, i.e., those such
                         that [0, 0], [a, b], and [c, d] are not collinear.
        ḅı               Convert each pair [a, b] from base i (imaginary unit) to
                         integer, mapping it to ai + b.
             €           For each pair of complex numbers [p, q]: 
          ;I$              append their forward differences, yielding [p, q, p-q].
              A          Take the absolute value of each resulting complex number.
               Ṣ€        Sort each resulting array of side lengths.
                 Q       Unique; remove duplicates.
                  S€     Take the sum of each array, computing the perimeters.
                    <¹   Compare them with n.
                      S  Take the sum of the resulting Booleans.

Jelly ,  38  33 byte

-1 terima kasih kepada Erik the Outgolfer (membalikkan SP¬+÷/E$dengan menggunakan SẠ>÷/E$dan menggunakan ÇÐfalih-alih ÇÐḟ) -1 terima kasih kepada Bpk. Xcoder (tidak perlu meratakan sebelum penyortiran)
-2 terima kasih kepada Bpk. Xcoder ( S<¥Ðf³L-> S€<³S)
-1 mencuri trik dari sebuah revisi sebelumnya atas jawaban Dennis ( ṗ2’Œc-> p`⁺’- lebih banyak kasus yang berlebihan tetapi golfier!)

SẠ>÷/E$
p`⁺’ÇÐfµ_/ṭ⁸²S€Ṣµ€Q½S€<³S

Program lengkap mengambil bilangan bulat dan mencetak hasilnya.

Cobalah online! (terlalu lambat untuk menyelesaikan kasus uji 20+ di bawah 60an)

Bagaimana?

SẠ>÷/E$ - Link 1, straightLineFromOrigin?: coordinates       i.e. [[a,b],[c,d]]
S       - sum                                                     [a+c,b+d]
 Ạ       - all? (0 if either of a+c or b+d are 0 otherwise 1)      all([a+c,b+d])
      $ - last two links as a monad:
   ÷/   -   reduce by division                                    [a÷c,b÷d]
     E  -   all equal?  (i.e. 1 if on a non-axial straight line)  a÷c==b÷d 
  >     - greater than? (i.e. 1 if not on any line, 0 otherwise)  all([a+c,b+d])>(a÷c==b÷d)

p`⁺’ÇÐḟµ_/ṭ⁸²S€Ṣµ€Q½S€<³S - Main link: integer, n
p`                        - Cartesian product of implicit range(n) with itself
  ⁺                       - repeat (Cartesian product of that result with itself)
   ’                      - decrement (vectorises)
                          -  - i.e. all non-negative lattice point pairs up to x,y=n-1
     Ðf                   - filter keep only if:
    Ç                     -   call last link (1) as a monad
       µ         µ€       - monadic chain for €ach:
        _/                -   reduce with subtraction i.e. [a-c,b-d]
           ⁸              -   chain's left argument, [[a,b],[c,d]]
          ṭ               -   tack                   [[a,b],[c,d],[c-a,d-b]]
            ²             -   square (vectorises)    [[a²,b²],[c²,d²],[(c-a)²,(d-b)²]]
             S€           -   sum €ach               [[a²+b²],[c²+d²],[(c-a)²+(d-b)²]]
                          -    - i.e. the squares of the triangle's edge lengths
               Ṣ          -   sort
                  Q       - de-duplicate (get one of each congruent set of triangles)
                   ½      - square root (vectorises)  - get sides from squares of sides
                    S€    - sum €ach
                       ³  - program's 3rd argument, n
                      <   - less than?
                        S -   sum (number of such triangles)
                          - implicit print

JavaScript (ES7), 157 byte

f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

Uji kasus

Hanya nilai kecil yang dapat dihitung dengan ukuran tumpukan default sebagian besar mesin JS.

f=(n,i=n**4,o={})=>i--&&([p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),!o[k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&a+b+c<n&&(o[k]=P*q!=p*Q))+f(n,i,o)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9   // 29
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))

Versi non-rekursif, 165 byte

n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

Uji kasus

Versi ini juga berfungsi untuk (30) dan (40) , tetapi itu akan memakan terlalu banyak waktu untuk cuplikan.

let f =

n=>[...Array(n**4)].reduce((x,_,i,o)=>x+=!o[[p,P,q,Q]=[0,1,2,3].map(k=>i/n**k%n|0),k=[a=(H=Math.hypot)(p,P),b=H(p-q,P-Q),c=H(q,Q)].sort()]&(o[k]=P*q!=p*Q)&a+b+c<n,0)

;[
  1,  // 0
  2,  // 0
  3,  // 0
  4,  // 1
  5,  // 3
  6,  // 5
  7,  // 11
  8,  // 18
  9,  // 29
  10, // 44
  12, // 94
  20  // 738
]
.forEach(n => console.log('a(' + n + ') = ' + f(n)))

Julia 0,6 , 135 byte

Ulangi kemungkinan titik-titik non-asal untuk membentuk segitiga, mewakili mereka sebagai bilangan kompleks, mengurutkan panjang persegi dan menyimpannya dalam satu set untuk memeriksa kesesuaian. Menghindari titik kolinear dengan memeriksa bahwa sudut antara bilangan kompleksnya adalah nol. Kemudian mengembalikan panjang set. Lebih pendek untuk menggunakan panjang secara langsung, tetapi Anda mendapatkan jawaban yang salah a(40). Solusinya terlalu lambat untuk mencapai run a(40)karena peringatan penghentian, jadi saya memiliki tautan ke versi yang lebih cepat juga.

n->(q=Set();for x=0:n,y=1:n,a=1:n,b=0:n
r=x+y*im
t=a+b*im
g=sort(abs2.([r,t,r-t]))
sum(√g)<n&&angle(r/t)>0&&push!(q,g)
end;length(q))

Cobalah online!

Lebih cepat, versi lebih lama dengan penghinaan dihindari. Cobalah online! Penggunaan sqrt.(g)di tempat usang √guntuk akar kuadrat elementwise.

Bersih , 227 ... 143 byte

import StdEnv
@n#l=[0.0..n]
=sum[1\\p<-removeDup[sort(map(sqrt o\[u,v]=u*u+v*v)[[a-i,b-j],[a,b],[i,j]])\\a<-l,b<-l,i<-l,j<-l|a*j<>i*b]|sum p<n]

Cobalah online!

Mendeteksi segitiga kongruen melalui membandingkan tiga nilai yang dijumlahkan untuk membuat garis keliling, dan titik-titik kolinear dengan memverifikasi bahwa dua nilai terkecil tersebut tidak sama dengan yang ketiga.

Berikut adalah versi yang menggunakan pendekatan yang lebih cepat, lebih banyak memori,: Cobalah secara online!