Definicja

„Trójkąt całkowity” to taki, który ma współrzędne całkowite. Na przykład następujący trójkąt jest trójkątem całkowitym:

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

Zadanie

Celem tego wyzwania jest policzenie wszystkich trójkątów całkowitych (do zgodności) o obwodzie mniejszym niż n.

Wejście i wyjście

Argument zostanie podany jako liczba całkowita, a wynik powinien być liczbą trójkątów o obwodzie ściśle mniejszym niż argument.

Przykłady

Najmniejszy całkowity trójkąt na obwodzie jest zgodny z

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

Kolejne najmniejsze to:

(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

Przypadki testowe:

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

Mam współrzędne dla każdego z trójkątów w tej Gist .

Ostrzeżenia

Zauważ, że dwa nie przystające trójkąty mogą mieć ten sam obwód:

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

Pamiętaj również, że nierówność jest surowa ; trójkąt pitagorejski 3-4-5 powinien być policzony jako (13), a nie (12).

Punktacja

To jest golf golfowy - wygrywa najkrótszy kod!

Galaretka , 28 27 25 23 bajtów

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

Wypróbuj online!

Jak to działa

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.

Galaretka ,  38  33 bajtów

-1 dzięki Erikowi Outgolfer (inwertowanie SP¬+÷/E$przy użyciu SẠ>÷/E$i użyciu ÇÐfzamiast ÇÐḟ) -1 dzięki Panu Xcoderowi (nie trzeba spłaszczać przed sortowaniem)
-2 dzięki Panu Xcoderowi ( S<¥Ðf³L-> S€<³S)
-1 kradnącego lewę z wcześniejsza wersja odpowiedzi Dennisa ( ṗ2’Œc-> p`⁺’- więcej zbędnych przypadków, ale golfista!)

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

Pełny program przyjmujący liczbę całkowitą i drukujący wynik.

Wypróbuj online! (zbyt wolno, aby ukończyć testy 20+ w wieku poniżej 60 lat)

W jaki sposób?

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 bajtów

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)

Przypadki testowe

Tylko małe wartości mogą być obliczone przy domyślnym rozmiarze stosu większości silników 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)))

Wersja nierekurencyjna, 165 bajtów

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)

Przypadki testowe

Ta wersja działa również w wersjach (30) i (40) , ale fragment kodu zajmie zbyt dużo czasu.

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 bajtów

Iteruj nad możliwymi punktami niebędącymi początkami, aby utworzyć trójkąt, przedstawić je jako liczby zespolone, posortować długości kwadratów i przechowywać je w zestawie, aby sprawdzić zgodność. Unika punktów kolinearnych, sprawdzając, czy kąt między ich liczbami zespolonymi jest niezerowy. Następnie zwraca długość zestawu. Krótsze jest użycie długości bezpośrednio, ale masz złą odpowiedź na a(40). Rozwiązanie jest zbyt wolne, aby można go było uruchomić z a(40)powodu ostrzeżenia o wycofaniu, więc mam też link do szybszej wersji.

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))

Wypróbuj online!

Szybsza, dłuższa wersja bez przestarzałości. Wypróbuj online! Używa sqrt.(g)zamiast przestarzałego √gdla pierwiastkowego pierwiastka kwadratowego.

Czysty , 227 ... 143 bajtów

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]

Wypróbuj online!

Wykrywa przystające trójkąty, porównując trzy wartości, które sumują się do obwodu, oraz punkty współliniowe, sprawdzając, czy dwie najmniejsze takie wartości nie sumują się do trzeciej.

Oto wersja, która wykorzystuje szybsze, bardziej obciążające pamięć podejście: Wypróbuj online!