Biorąc pod uwagę listę dodatnich liczb całkowitych, znajdź liczbę trójkątów, które możemy utworzyć, tak aby ich długości boków były reprezentowane przez trzy różne wpisy na liście wejściowej.

(Inspiracja pochodzi z CR .)

Detale

• Trójkąt można utworzyć, jeśli wszystkie kombinacje trzech długości boków spełniają ścisłą nierówność trójkąta(Oznacza to, że , oraz muszą być wszystkie.)$a,b,c$ $$a + b > c.$$ $a+b > c$$a+c>b$$b+c>a$
• Trzy długości boków muszą pojawić się w różnych pozycjach na liście, ale niekoniecznie muszą być odrębne parami.$a,b,c$
• Kolejność trzech liczb na liście wprowadzania nie ma znaczenia. Jeśli weźmiemy pod uwagę listę ai trzy liczby a[i], a[j], a[k](gdzie i,j,kpary są różne), to (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])itd. Wszystkie są uważane za ten sam trójkąt.
• Zakłada się, że lista wejściowa zawiera co najmniej 3 wpisy.
• Możesz założyć, że lista wejściowa jest posortowana w porządku rosnącym.

Przykłady

Mały program testowy można znaleźć tutaj na Wypróbuj online!

Input, Output:
[1,2,3]  0
[1,1,1]  1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50

Do wprowadzenia [1,2,3,...,n-1,n]tego należy A002623 .

Dla wprowadzenia [1,1,...,1](długości n) jest to A000292 .

Dla wprowadzenia pierwszych nliczb Fibonacciego ( A000045 ) jest to A000004 .

R , 62 52 40 34 bajtów

sum(c(1,1,-1)%*%combn(scan(),3)>0)

Wypróbuj online!

Rozwiązanie Octave dla portu Luisa Mendo

Ponieważ a<=b<=cwarunek trójkąta jest równoważny a+b-c>0. Jest a+b-cto zwięźle uchwycone przez iloczyn macierzy [1,1,-1] * X, gdzie Xsą 3 kombinacje macierzy wejściowej.

W komentarzach pojawiło się wiele sugestii dotyczących ulepszeń 3 różnych osób:

• Robertowi S. za sugestięscan .

• Robin Ryder za zasugerowanie poprawy nierówności trójkąta i tego dziwnego, który wymaga, aby dane wejściowe były w porządku malejącym (co po prostu pokazuje, jak ważny jest elastyczny format wejściowy).

• i wreszcie Nick Kennedy za:

R , 40 bajtów

y=combn(scan(),3);sum(y[3,]<y[1,]+y[2,])

Wypróbuj online!

Stax , 8 7 bajtów

Dzięki rekursywnemu dla -1!

é═rê÷┐↨

Uruchom i debuguj na staxlang.xyz!

Rozpakowane (8 bajtów) i objaśnienie:

r3SFE+<+
r           Reverse
 3S         All length-3 combinations
   F        For each combination:
    E         Explode: [5,4,3] -> 3 4 5, with 3 atop the stack
     +        Add the two shorter sides
      <       Long side is shorter? 0 or 1
       +      Add result to total

To fajna sztuczka. Jeśli masz sekwencję instrukcji, która zawsze spowoduje 0 lub 1 i musisz policzyć elementy z tablicy, która daje prawdziwy wynik na końcu programu, F..+jest to bajt krótszy niż {..f%.

Zakłada, że ​​początkowa lista jest posortowana rosnąco. Bez tego założenia trzymaj ona początku 8 bajtów.

Haskell , 49 bajtów

([]%)
[c,b,a]%l|a+b>c=1
p%(h:l)=(h:p)%l+p%l
_%_=0

Wypróbuj online!

Rekurencyjnie generuje wszystkie podciągi l(odwrócone) i sprawdza, które długości 3 tworzą trójkąty.

50 bajtów

f l=sum[1|[a,b,c]<-filter(>0)<$>mapM(:[0])l,a+b>c]

Wypróbuj online!

Ten sam pomysł, generowanie podsekwencji mapM, poprzez mapowanie każdej wartości ldo siebie (dołącz) lub 0(wyklucz).

50 bajtów

([]%)
p%(b:t)=sum[1|c<-t,a<-p,a+b>c]+(b:p)%t
_%_=0

Wypróbuj online!

Próbuje każdego punktu podziału, aby wziąć środkowy element b.

51 bajtów

f(a:t)=f t+sum[1|b:r<-scanr(:)[]t,c<-r,a+b>c]
f _=0

Wypróbuj online!

Funkcja q=scanr(:)[]generuje listę sufiksów. Wiele problemów wiąże się z koniecznością uwzględnienia równych elementów we właściwej liczbie razy.

52 bajty

q=scanr(:)[]
f l=sum[1|a:r<-q l,b:s<-q r,c<-s,a+b>c]

Wypróbuj online!

Funkcja pomocnicza q=scanr(:)[]generuje listę sufiksów.

57 bajtów

import Data.List
f l=sum[1|[a,b,c]<-subsequences l,a+b>c]

Wypróbuj online!

Brachylog , 11 bajtów

{⊇Ṫ.k+>~t}ᶜ

Wypróbuj online!

Być może zapomniałem skorzystać z posortowanych danych wejściowych w moim starym rozwiązaniu:

Brachylog , 18 17 15 bajtów

{⊇Ṫ¬{p.k+≤~t}}ᶜ

Wypróbuj online!

{            }ᶜ    The output is the number of ways in which
 ⊇                 a sublist of the input can be selected
  Ṫ                with three elements
   ¬{       }      such that it is not possible to show that
     p             for some permutation of the sublist
       k+          the sum of the first two elements
         ≤         is less than or equal to
      .   ~t}      the third element.

Perl 6 , 35 bajtów

+*.combinations(3).flat.grep(*+*>*)

Wypróbuj online!

Wyjaśnienie

Jest to dowolny kod, tzn. Zwięzły zapis funkcji lambda (który działa tylko w bardzo prostych przypadkach). Każdy *jest symbolem zastępczym dla jednego argumentu. Więc bierzemy listę długości (która pojawia się na początku *), tworzymy wszystkie kombinacje 3 elementów (zawsze wychodzą w tej samej kolejności jak na oryginalnej liście, więc to oznacza, że ​​kombinacje też są posortowane), spłaszcz listę, a następnie weźmy listę 3 na 3 i filtruj ( grep) tylko te trojaczki, które spełniają *+*>*, tzn. że suma dwóch pierwszych argumentów jest większa niż trzecia. To daje wszystkie trojaczki, a my w końcu je liczymy, wymuszając kontekst liczbowy za pomocą +.

(Oczywiście musimy to przetestować tylko w przypadku „sumy dwóch mniejszych> największych”. Jeśli to się trzyma, to drugie trzyma się trywialnie, jeśli nie, triplet nie oznacza poprawnej długości trójkąta, a my nie trzeba szukać dalej.)

Siatkówka , 55 bajtów

\d+
*
L$`_+
$<'
%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_
_

Wypróbuj online! Link zawiera przypadki testowe, ale ze zmniejszonymi wartościami w piątym przypadku, aby mógł zakończyć się dzisiaj. Zakłada posortowane dane wejściowe. Objaśnienie: Regeksy tak naprawdę nie lubią dopasowywać więcej niż jednej rzeczy. Zwykłe wyrażenie regularne byłoby w stanie znaleźć wszystkie wartości, które mogłyby być najkrótszą odnogą trójkąta. vOpcja Retina nie pomaga tutaj, z wyjątkiem uniknięcia spojrzenia w przód. Jednak wopcja Retiny jest nieco bardziej pomocna, ponieważ byłaby w stanie znaleźć zarówno najkrótszą, jak i najdłuższą nogę w tym samym czasie. To jednak nie wystarczy do tego wyzwania, ponieważ może być wiele środkowych nóg.

\d+
*

Przekształć dane wejściowe w jednoargumentowe.

L$`_+

Dla każdego numeru wejściowego ...

$<'

... utwórz linię, która jest oryginalną tablicą obciętą, aby rozpocząć od tego numeru. $'normalnie oznacza ciąg po dopasowaniu, ale <modyfikuje go, aby oznaczać ciąg po poprzednim separatorze, unikając marnowania 2 bajtów $&. Każda linia reprezentuje zatem wszystkie potencjalne rozwiązania wykorzystujące ten numer jako najkrótszą nogę.

%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_

Dla każdej z tych linii znajdź wszystkie możliwe środkowe i najdłuższe nogi, ale upewnij się, że różnica jest mniejsza niż pierwsza noga. Wyprowadź a _dla każdej pasującej kombinacji nóg.

_

Policz całkowitą liczbę znalezionych trójkątów.

Python 3 , 73 bajty

lambda l:sum(a+b>c for a,b,c in combinations(l,3))
from itertools import*

Wypróbuj online!

$(a,b,c)$$a+b>c$

Python 2 , 72 bajty

f=lambda l,p=[]:l>[]and(p==p[:2]<[sum(p)]>l)+f(l[1:],p)+f(l[1:],p+l[:1])

Wypróbuj online!

73 bajty

lambda l:sum(a+b>c for j,b in enumerate(l)for a in l[:j]for c in l[j+1:])

Wypróbuj online!

05AB1E , 12 10 9 bajtów

Mój pierwszy raz korzystam z 05AB1E! Dzięki [Grimy] za -1!

3.Æʒ`α›}g

Wypróbuj online! lub pakiet testowy

Bezpośredni port mojej odpowiedzi Stax. Zbierz wszystkie kombinacje trzech wpisów i policz te, które mogą tworzyć trójkąty. To ta licząca część, która naprawdę mnie dopadła. Tam spędzam mnóstwo bajtów. Związany z tym, że jest to jakaś pomyłka nowicjusza.

3.Æʒ`α›}g
3.Æ          List of length-3 combinations
   ʒ   }g    Count truthy results under operation:
    `          Push the two shorter sides, then the long one
     α         Absolute difference (negated subtraction in this case)
      ›        Remaining short side is longer?

JavaScript (ES6), 63 bajty

f=([v,...a],p=[])=>v?(!p[2]&p[0]+p[1]>v)+f(a,p)+f(a,[...p,v]):0

Wypróbuj online!

Octave / MATLAB, 33 bajty

@(x)sum(nchoosek(x,3)*[1;1;-1]>0)

Wypróbuj online!

Zsh , 66 bajtów

for a;z=$y&&for b (${@:2+y++})for c (${@:3+z++})((t+=c<a+b))
<<<$t

Wypróbuj online!

Stosunkowo proste, wykorzystujące posortowane dane wejściowe i zwiększające w fornagłówku (przyrost odbywa się raz na pętlę nadrzędną ).

for a;{
  z=$y
  for b (${@:2+y++});{   # subarray starting at element after $a
    for c (${@:3+z++})   # subarray starting at element after $b
      ((t+=c<a+b))
  }
}

Excel VBA, 171 164 152 bajtów

^{-26 bajtów dzięki TaylorScott}

Sub z
t=[A:A]
u=UBound(t)
For i=1To u-2
For j=i+1To u-1
For k=j+1To u
a=t(i,1):b=t(j,1):c=t(k,1)
r=r-(a+b>c)*(b+c>a)*(c+a>b)
Next k,j,i
Debug.?r
End Sub

Dane wejściowe mieszczą się A:Aw zakresie aktywnego arkusza. Dane wyjściowe są w bezpośrednim oknie.

Ponieważ analizuje każdą kombinację każdej komórki w kolumnie o wysokości 2 ²⁰ komórek (czyli prawie 2 ⁶⁰ kombinacji), ten kod nie jest ... szybki. Możesz zrobić to znacznie szybciej, ale kosztem bajtów.

Węgiel drzewny , 17 bajtów

ＩΣ⭆θ⭆…θκ⭆…θμ›⁺νλι

Wypróbuj online! Link jest do pełnej wersji kodu. Zakłada posortowane dane wejściowe. Wyjaśnienie:

   θ                Input array
  ⭆                 Map over elements and join
      θ             Input array
     …              Truncated to length
       κ            Outer index
    ⭆               Map over elements and join
          θ         Input array
         …          Truncated to length
           μ        Inner index
        ⭆           Map over elements and join
              ν     Innermost value
             ⁺      Plus
               λ    Inner value
            ›       Is greater than
                ι   Outer value
 Σ                  Take the digital sum
Ｉ                   Cast to string for implicit print

Japt -x , 9 bajtów

à3 ËÌÑ<Dx

Spróbuj

à3 ®o <Zx

Spróbuj

Wolfram Language (Mathematica) , 37 35 bajtów

Tr@Boole[2#3<+##&@@@#~Subsets~{3}]&

Wypróbuj online!

Rubin , 41 bajtów

->l{l.combination(3).count{|a,b,c|c<a+b}}

Wypróbuj online!

Pyth , 14 bajtów

*1sm>sPded.cQ3

Wypróbuj online!

          .cQ3  # All combinations of length 3 from Q (input), sorted in ascending order
   m            # map over that lambda d:
     sPd        #   sum(d[:-1])
    >   ed      #     > d[-1]
  s             # sum all of those (uses the fact that True = 1)
*1              # multiply by 1 so it doesn't output True if there's only one triangle

Alternatywa (także 14 bajtów):

lfTm>sPded.cQ3

Perl 5 ( -p), 55 52 bajtów

przy użyciu wyrażenia regularnego, -3 bajty dzięki kwakowi @Cows używają ^zamiast (?!)się nie udać i cofnąć.

$d='(\d++)';$_=/$d.* $d.* $d(?{$n++if$1+$2>$3})^/+$n

lub

$_=/(\d++).* (\d++).* (\d++)(?{$n++if$1+$2>$3})^/+$n

TIO

Galaretka , 9 bajtów

œc3+>ƭ/€S

Wypróbuj online!

Monadyczny link przyjmujący posortowaną listę liczb całkowitych jako argument i zwracający liczbę trójkątów.

Wyjaśnienie

œc3       | Combinations of length 3
     ƭ/€  | Reduce each using each of the following in turn:
   +      | - Add
    >     | - Greater than
        S | Sum (counts the 1s)

Alternatywne 9s:

œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S

J , 40 bajtów

1#.](+/*/@(->])])@#~2(#~3=1&#.)@#:@i.@^#

Wypróbuj online!

Bash , 123 bajty

for a;do for((i=2;i<=$#;i++)){ b=${!i};for((j=$[i+1];j<=$#;j++)){ c=${!j};T=$[T+(a<b+c&b<a+c&c<a+b)];};};shift;done;echo $T

Wypróbuj online!

Zabawna.

SNOBOL4 (CSNOBOL4) , 181 bajtów

	S =TABLE()
R	X =X + 1
	S<X> =INPUT	:S(R)
I	I =J =K =I + 1	LT(I,X)	:F(O)
J	J =K =J + 1	LT(J,X)	:F(I)
K	K =K + 1	LT(K,X - 1)	:F(J)
	T =T + 1 GT(S<I> + S<J>,S<K>)	:(K)
O	OUTPUT =T
END

Wypróbuj online!

Brutalna siła $O(n^3)$algorytm. Pobiera dane wejściowe jako listę oddzieloną znakiem nowej linii i wyświetla liczbę trójkątów lub pustą linię dla 0. Jest to prawdopodobnie dopuszczalne, ponieważ SNOBOL traktuje pusty ciąg znaków jak 0do obliczeń numerycznych.

C (brzęk) , 83 bajty

x,y,q;f(*a,z){for(x=y=q=0;z;q+=z>1&a[x-=x?1:2-y--]+a[y]>a[z])y=y>1?y:--z;return q;}

Wypróbuj online!

Zapisano 1 dzięki @ceilingcat