Bestimmen Sie anhand einer Liste positiver Ganzzahlen die Anzahl der Dreiecke, die wir so bilden können, dass ihre Seitenlängen durch drei verschiedene Einträge in der Eingabeliste dargestellt werden.

(Inspiration kommt von CR .)

Einzelheiten

• Ein Dreieck kann gebildet werden, wenn alle Permutationen der drei Seitenlängen die strenge Dreieckungleichung erfüllen(Dies bedeutet, dass , und alle gelten müssen.)$a,b,c$ $$a + b > c.$$ $a+b > c$$a+c>b$$b+c>a$
• Die drei Seitenlängen müssen an unterschiedlichen Positionen in der Liste erscheinen, müssen aber nicht unbedingt paarweise unterschiedlich sein.$a,b,c$
• Die Reihenfolge der drei Zahlen in der Eingabeliste spielt keine Rolle. Betrachten wir eine Liste aund die drei Zahlen a[i], a[j], a[k](wo i,j,kpaarweise verschieden sind), dann werden (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])usw. alle als das gleiche Dreieck betrachtet.
• Die Eingabeliste kann mindestens 3 Einträge enthalten.
• Sie können davon ausgehen, dass die Eingabeliste aufsteigend sortiert ist.

Beispiele

Ein kleines Testprogramm finden Sie hier auf Try it 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

Für die Eingabe ist [1,2,3,...,n-1,n]dies A002623 .

Für die Eingabe von [1,1,...,1](Länge n) ist dies A000292 .

Für die Eingabe der ersten nFibonacci-Zahlen ( A000045 ) ist dies A000004 .

R , 62 52 40 34 Bytes

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

Probieren Sie es online!

Port von Luis Mendos Octave-Lösung

Da a<=b<=cist die Dreieckbedingung äquivalent zu a+b-c>0. Das a+b-cwird prägnant durch das Matrixprodukt erfasst [1,1,-1] * X, wobei Xdie 3-Kombinationen des Eingabearrays sind.

In den Kommentaren gab es viele Verbesserungsvorschläge von 3 verschiedenen Personen:

• Robert S. für den Vorschlagscan .

• Robin Ryder für die Vorschläge zur Verbesserung der Dreiecksungleichung und diese ungerade, bei der die Eingabe in absteigender Reihenfolge erfolgen muss (was nur zeigt, wie wichtig ein flexibles Eingabeformat ist).

• und schlussendlich Nick Kennedy für Folgendes:

R , 40 Bytes

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

Probieren Sie es online!

Stax , 8 7 Bytes

Danke an rekursiv für -1!

é═rê÷┐↨

Führen Sie es aus und debuggen Sie es unter staxlang.xyz!

Entpackt (8 Bytes) und Erklärung:

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

Das ist ein ordentlicher Trick. Wenn Sie eine Folge von Anweisungen haben, die immer zu 0 oder 1 führt, und Sie die Elemente aus einem Array zählen müssen, die am Ende Ihres Programms das wahrheitsgemäße Ergebnis liefern, F..+ist ein Byte kürzer als{..f% .

Angenommen, die ursprüngliche Liste ist aufsteigend sortiert. Setzen Sie ohne diese Annahme ein oam Anfang für 8 Bytes.

Haskell , 49 Bytes

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

Probieren Sie es online!

Generiert rekursiv alle Untersequenzen von l(umgekehrt) und prüft, welche Länge-3-Einsen Dreiecke bilden.

50 Bytes

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

Probieren Sie es online!

Dieselbe Idee, die Untersequenzen mit zu generieren mapM, indem jeder Wert lentweder auf sich selbst (include) oder 0(exclude) abgebildet wird .

50 Bytes

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

Probieren Sie es online!

Versucht jeden Partitionspunkt, das mittlere Element zu nehmen b.

51 Bytes

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

Probieren Sie es online!

Die Funktion q=scanr(:)[]generiert die Liste der Suffixe. Eine Menge Ärger entsteht, wenn Sie berücksichtigen müssen, dass gleiche Elemente die richtige Anzahl von Malen enthalten.

52 Bytes

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

Probieren Sie es online!

Die Hilfsfunktion q=scanr(:)[]generiert die Liste der Suffixe.

57 Bytes

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

Probieren Sie es online!

Brachylog , 11 Bytes

{⊇Ṫ.k+>~t}ᶜ

Probieren Sie es online!

Möglicherweise habe ich vergessen, die sortierte Eingabe in meiner alten Lösung zu nutzen:

Brachylog , 18 17 15 Bytes

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

Probieren Sie es 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 Bytes

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

Probieren Sie es online!

Erläuterung

Es ist ein Whatever-Code, dh eine kurze Notation für Lambda-Funktionen (das funktioniert nur in sehr einfachen Fällen). Jedes *ist ein Platzhalter für ein Argument. Also nehmen wir die Liste der Längen (die am ersten erscheint *), machen alle Kombinationen von 3 Elementen (sie kommen immer in der gleichen Reihenfolge wie in der ursprünglichen Liste heraus, was bedeutet, dass die Kombinationen auch sortiert sind), reduzieren die Liste, und nimm dann die Liste 3-mal-3 und filter ( grep) nur die Triplets, die erfüllen *+*>*, dh die Summe der ersten beiden Argumente ist größer als das dritte. Das gibt alle Drillinge und wir zählen sie schließlich, indem wir den numerischen Kontext mit a erzwingen+ .

(Natürlich müssen wir es nur für den Fall von "Summe von zwei kleineren> dem größten" testen. Wenn dies zutrifft, gilt das andere trivial, wenn dies nicht zutrifft, bezeichnet das Triplett nicht die richtigen Dreieckslängen und wir tun es nicht muss weiter schauen.)

Netzhaut , 55 Bytes

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

Probieren Sie es online! Link enthält Testfälle, wobei jedoch die Werte im fünften Fall reduziert wurden, damit der Vorgang heute beendet werden kann. Setzt sortierte Eingabe voraus. Erläuterung: Regexe mögen es nicht wirklich, mehr als eine Sache abzugleichen. Ein normaler Regex könnte alle Werte finden, die ein kürzester Abschnitt eines Dreiecks sein könnten. Die vOption von Retina hilft hier nicht weiter, außer um einen Lookahead zu vermeiden. Die wOption von Retina ist jedoch etwas hilfreicher, da sowohl das kürzeste als auch das längste Bein gleichzeitig gefunden werden können. Dies ist jedoch nicht genug für diese Herausforderung, da möglicherweise mehrere Mittelbeine vorhanden sind.

\d+
*

Konvertieren Sie die Eingabe in Unary.

L$`_+

Für jede eingegebene Nummer ...

$<'

... erstellen Sie eine Zeile, deren ursprüngliches Array ab dieser Nummer abgeschnitten ist. $'bedeutet normalerweise die Zeichenfolge nach dem Abgleich, <ändert sie jedoch so, dass sie die Zeichenfolge nach dem vorherigen Trennzeichen bedeutet, sodass keine 2 Bytes mehr verschwendet werden $&. Jede Zeile repräsentiert daher alle möglichen Lösungen, wobei diese Nummer als kürzester Abschnitt verwendet wird.

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

Suchen Sie für jede dieser Linien alle möglichen mittleren und längsten Beine, stellen Sie jedoch sicher, dass der Unterschied kleiner als das erste Bein ist. Geben Sie _für jede passende Beinkombination ein aus.

_

Zählen Sie die Gesamtzahl der gefundenen Dreiecke.

Python 3 , 73 Bytes

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

Probieren Sie es online!

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

Python 2 , 72 Bytes

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

Probieren Sie es online!

73 Bytes

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

Probieren Sie es online!

05AB1E , 12 10 9 Bytes

Mein erstes Mal mit 05AB1E! Danke an [Grimy] für -1!

3.Æʒ`α›}g

Probieren Sie es online! oder Testsuite

Ein direkter Port meiner Stax-Antwort. Holen Sie sich alle Kombinationen von drei Einträgen und zählen Sie diejenigen, die möglicherweise Dreiecke bilden könnten. Es ist dieser zählende Teil, der mich wirklich erwischt hat. Ich gebe dort eine Menge Bytes aus. Ich bin fest entschlossen, dort ein Anfängerfehler zu sein.

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 Byte

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

Probieren Sie es online!

Oktave / MATLAB, 33 Bytes

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

Probieren Sie es online!

Zsh , 66 Bytes

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

Probieren Sie es online!

Relativ einfach, unter Ausnutzung der sortierten Eingabe und Inkrementierung des forHeaders (die Inkrementierung erfolgt einmal pro übergeordneter Schleife).

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 Bytes

^{-26 Bytes dank 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

Die Eingabe liegt im Bereich A:Ades aktiven Blattes. Die Ausgabe erfolgt in das unmittelbare Fenster.

Da hiermit jede Kombination jeder Zelle in einer Spalte betrachtet wird, die 2 bis ²⁰ Zellen hoch ist (was fast 2 bis ⁶⁰ Kombinationen entspricht), ist dieser Code ... nicht schnell. Sie könnten es viel schneller machen, aber auf Kosten von Bytes.

Kohle , 17 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Setzt sortierte Eingabe voraus. Erläuterung:

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

à3 ËÌÑ<Dx

Versuch es

à3 ®o <Zx

Versuch es

Wolfram Language (Mathematica) , 37-35 Bytes

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

Probieren Sie es online!

Ruby , 41 Bytes

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

Probieren Sie es online!

Pyth , 14 Bytes

*1sm>sPded.cQ3

Probieren Sie es 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

Alternative (auch 14 Bytes):

lfTm>sPded.cQ3

Perl 5 (-p ), 55 52 Bytes

mit Regex Backtracking, -3 Bytes dank @Cows Quacksalber mit ^ anstelle von (?!)Fail und Backtracking.

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

oder

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

TIO

Gelee , 9 Bytes

œc3+>ƭ/€S

Probieren Sie es online!

Ein monadischer Link, der eine sortierte Liste von Ganzzahlen als Argument verwendet und die Anzahl der Dreiecke zurückgibt.

Erläuterung

œ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 Bytes

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

Probieren Sie es online!

Bash , 123 Bytes

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

Probieren Sie es online!

Ein lustiger.

SNOBOL4 (CSNOBOL4) , 181 Bytes

	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

Probieren Sie es online!

Rohe Gewalt $O(n^3)$Algorithmus. Nimmt die Eingabe als durch neue Zeilen getrennte Liste und gibt die Anzahl der Dreiecke oder eine leere Zeile für aus 0. Dies ist wahrscheinlich zulässig, da SNOBOL die leere Zeichenfolge wie 0bei numerischen Berechnungen behandelt.

C (clang) 83 Bytes

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

Probieren Sie es online!

1 Dank an @ceilingcat gespeichert