Étant donné une liste d'entiers positifs, trouvez le nombre de triangles que nous pouvons former de telle sorte que leurs longueurs latérales soient représentées par trois entrées distinctes de la liste d'entrée.

(L'inspiration vient de CR .)

Détails

• Un triangle peut être formé si toutes les permutations des trois longueurs latérales $a,b,c$ satisfont l' inégalité stricte du triangle $$a + b > c.$$ (Cela signifie $a+b > c$ , $a+c>b$ et $b+c>a$ doivent tous tenir.)
• Les trois longueurs latérales $a,b,c$ doivent apparaître à des positions distinctes dans la liste, mais ne doivent pas nécessairement être distinctes deux à deux.
• L'ordre des trois nombres dans la liste d'entrée n'a pas d'importance. Si nous considérons une liste aet les trois nombres a[i], a[j], a[k](où i,j,ksont différents deux par deux), (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])etc., tous sont considérés comme le même triangle.
• La liste des entrées peut supposer contenir au moins 3 entrées.
• Vous pouvez supposer que la liste d'entrée est triée par ordre croissant.

Exemples

Un petit programme de test peut être trouvé ici sur Essayez-le en ligne!

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

Pour l'entrée de [1,2,3,...,n-1,n]ceci est A002623 .

Pour l'entrée de [1,1,...,1](longueur n), c'est A000292 .

Pour l'entrée des premiers nnuméros de Fibonacci ( A000045 ), c'est A000004 .

R , 62 52 40 34 octets

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

Essayez-le en ligne!

Solution Octave du port de Luis Mendo

Depuis a<=b<=c, la condition du triangle est équivalente à a+b-c>0. Le a+b-cest succinctement capturé par le produit matriciel [1,1,-1] * X, où Xse trouvent les 3 combinaisons du tableau d'entrée.

Il y avait beaucoup de suggestions d'améliorations faites par 3 personnes différentes dans les commentaires:

• Robert S. pour avoir suggéréscan .

• Robin Ryder pour avoir suggéré des améliorations à l'inégalité du triangle et cette étrange qui nécessite que l'entrée soit dans l' ordre décroissant (ce qui montre juste à quel point un format d'entrée flexible est important).

• et enfin Nick Kennedy pour ce qui suit:

R , 40 octets

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

Essayez-le en ligne!

Stax , 8 7 octets

Merci à récursif pour -1!

é═rê÷┐↨

Exécutez-le et déboguez-le sur staxlang.xyz!

Déballé (8 octets) et explication:

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

C'est une astuce intéressante. Si vous avez une séquence d'instructions qui se traduira toujours par 0 ou 1 et que vous devez compter les éléments d'un tableau qui donnent le résultat véridique à la fin de votre programme, F..+est un octet plus court que {..f%.

Suppose que la liste initiale est triée par ordre croissant. Sans cette hypothèse, collez un oau début pour 8 octets.

Haskell , 49 octets

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

Essayez-le en ligne!

Génère récursivement toutes les sous-séquences de l(inversé) et vérifie quelles longueurs 3 forment des triangles.

50 octets

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

Essayez-le en ligne!

La même idée, générer les sous-séquences avec mapM, en mappant chaque valeur lsoit à elle-même (inclure) soit 0(exclure).

50 octets

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

Essayez-le en ligne!

Essaie chaque point de partition pour prendre l'élément central b.

51 octets

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

Essayez-le en ligne!

La fonction q=scanr(:)[]génère la liste des suffixes. Beaucoup de problèmes proviennent de la nécessité d'envisager d'inclure des éléments égaux le bon nombre de fois.

52 octets

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

Essayez-le en ligne!

La fonction d'assistance q=scanr(:)[]génère la liste des suffixes.

57 octets

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

Essayez-le en ligne!

Brachylog , 11 octets

{⊇Ṫ.k+>~t}ᶜ

Essayez-le en ligne!

J'ai peut-être oublié de profiter de l'entrée triée dans mon ancienne solution:

Brachylog , 18 17 15 octets

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

Essayez-le en ligne!

{            }ᶜ    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 octets

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

Essayez-le en ligne!

Explication

C'est un code quelconque, c'est-à-dire une notation concise pour les fonctions lambda (qui ne fonctionne que dans des cas très simples). Chacun *est un espace réservé pour un argument. Nous prenons donc la liste des longueurs (qui apparaît en premier *), faisons toutes les combinaisons de 3 éléments (elles sortent toujours dans le même ordre que dans la liste d'origine, ce qui signifie que les combinaisons sont également triées), aplatissons la liste, puis prenez la liste 3 par 3, et filtrez ( grep) uniquement les triplets qui satisfont *+*>*, c'est-à-dire que la somme des deux premiers arguments est supérieure au troisième. Cela donne tous les triplets, et nous les comptons finalement en forçant le contexte numérique avec a +.

(Bien sûr, nous devons le tester uniquement pour le cas de "somme de deux plus petits> le plus grand". Si cela est vrai, l'autre tient trivialement, si ce n'est pas le cas, le triplet ne dénote pas des longueurs de triangle correctes et nous ne le faisons pas besoin de chercher plus loin.)

Rétine , 55 octets

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

Essayez-le en ligne! Le lien inclut des cas de test, mais avec les valeurs du 5e cas réduites pour lui permettre de se terminer aujourd'hui. Suppose une entrée triée. Explication: les expressions rationnelles n'aiment pas vraiment correspondre à plus d'une chose. Un regex normal serait capable de trouver toutes les valeurs qui pourraient être la jambe la plus courte d'un triangle. L' voption de Retina n'aide pas ici, sauf pour éviter une anticipation. Cependant, l' woption Retina est légèrement plus utile, car elle pourrait trouver la jambe la plus courte et la plus longue en même temps. Ce n'est pas suffisant pour ce défi, car il peut y avoir plusieurs jambes centrales.

\d+
*

Convertissez l'entrée en unaire.

L$`_+

Pour chaque numéro d'entrée ...

$<'

... créez une ligne qui est le tableau d'origine tronqué pour commencer à ce nombre. $'signifie normalement la chaîne après la correspondance, mais le <modifie pour signifier la chaîne après le séparateur précédent, évitant de gaspiller 2 octets $&. Chaque ligne représente donc toutes les solutions potentielles en utilisant ce nombre comme la jambe la plus courte.

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

Pour chacune de ces lignes, trouvez toutes les jambes moyennes et les plus longues possibles, mais assurez-vous que la différence est inférieure à la première jambe. Générez un _pour chaque combinaison de jambes correspondante.

_

Comptez le nombre total de triangles trouvés.

Python 3 , 73 octets

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

Essayez-le en ligne!

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

Python 2 , 72 octets

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

Essayez-le en ligne!

73 octets

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

Essayez-le en ligne!

05AB1E , 12 10 9 octets

Ma première utilisation de 05AB1E! Merci à [Grimy] pour -1!

3.Æʒ`α›}g

Essayez-le en ligne!ou suite de tests

Un port direct de ma réponse Stax. Obtenez toutes les combinaisons de trois entrées et comptez celles qui pourraient éventuellement former des triangles. C'est cette partie de comptage qui m'a vraiment attiré. J'y passe une charge d'octets. Lié à une erreur de recrue là-bas.

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 octets

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

Essayez-le en ligne!

Octave / MATLAB, 33 octets

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

Essayez-le en ligne!

Zsh , 66 octets

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

Essayez-le en ligne!

Relativement simple, tirant parti de l'entrée triée et incrémentant dans l'en- fortête (l'incrément se produit une fois par boucle parent ).

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 octets

^{-26 octets grâce à 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

L'entrée est dans la plage A:Ade la feuille active. La sortie est vers la fenêtre immédiate.

Étant donné que cela examine chaque combinaison de chaque cellule d'une colonne de 2 à ²⁰ cellules (soit près de 2 ⁶⁰ combinaisons), ce code n'est ... pas rapide. Vous pourriez le rendre beaucoup plus rapide mais au détriment des octets.

Fusain , 17 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Suppose une entrée triée. Explication:

   θ                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 octets

à3 ËÌÑ<Dx

Essayez-le

à3 ®o <Zx

Essayez-le

Wolfram Language (Mathematica) , 37 35 octets

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

Essayez-le en ligne!

Rubis , 41 octets

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

Essayez-le en ligne!

Pyth , 14 octets

*1sm>sPded.cQ3

Essayez-le en ligne!

          .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

Alternative (également 14 octets):

lfTm>sPded.cQ3

Perl 5 ( -p), 55 52 octets

en utilisant regex backtracking, -3 octets grâce à @Cows quack using ^au lieu de (?!)to fail et backtrack.

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

ou

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

TIO

Gelée , 9 octets

œc3+>ƭ/€S

Essayez-le en ligne!

Un lien monadique prenant comme argument une liste triée d'entiers et renvoyant le nombre de triangles.

Explication

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

Alternative 9s:

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

J , 40 octets

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

Essayez-le en ligne!

Bash , 123 octets

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

Essayez-le en ligne!

Un plaisir.

SNOBOL4 (CSNOBOL4) , 181 octets

	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

Essayez-le en ligne!

Force brute $O(n^3)$algorithme. Prend les entrées sous forme de liste séparée par des sauts de ligne et sort le nombre de triangles, ou une ligne vide pour 0. Ceci est probablement permis car SNOBOL traite la chaîne vide comme 0pour les calculs numériques.

C (clang) , 83 octets

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;}

Essayez-le en ligne!

Enregistré 1 grâce à @ceilingcat