Count the number of triangles

Question

Given a list of positive integers, find the number of triangles we can form such that their side lengths are represented by three distinct entries of the input list.

(Inspiration comes from CR.)

Details

• A triangle can be formed if all permutations of the three side lengths \$a,b,c\$ satisfy the strict triangle inequality $$a + b > c.$$ (This means \$a+b > c\$, \$a+c>b\$ and \$b+c>a\$ must all hold.)
• The three side lengths \$a,b,c\$ must appear at distinct positions in the list, but do not necessarily have to be pairwise distinct.
• The order of the three numbers in the input list does not matter. If we consider a list a and the three numbers a[i], a[j], a[k] (where i,j,k are pairwise different), then (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k]) etc. all are considered as the same triangle.
• The input list can assumed to contain at least 3 entries.
• You can assume that the input list is sorted in ascending order.

Examples

A small test program can be found here on 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

For the input of [1,2,3,...,n-1,n] this is A002623.

For the input of [1,1,...,1] (length n) this is A000292.

For the input of the first n Fibonacci numbers (A000045) this is A000004.

Answer 1

Stax, 8 7 bytes

Thanks to recursive for -1!

é═rê÷┐↨

Run and debug it at staxlang.xyz!

Unpacked (8 bytes) and explanation:

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

That's a neat trick. If you have a sequence of instructions that will always result in 0 or 1 and you need to count the items from an array that yield the truthy result at the end of your program, F..+ is a byte shorter than {..f%.

Assumes the initial list is sorted ascending. Without this assumption, stick an o at the beginning for 8 bytes.

Answer 2

R, 62 52 40 34 bytes

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

Try it online!

Port of Luis Mendo's Octave solution

Since a<=b<=c, the triangle condition is equivalent to a+b-c>0. The a+b-c is succinctly captured by the matrix product [1,1,-1] * X, where X is the 3-combinations of the input array.

There were a lot of suggestions for improvements made by 3 different people in the comments:

• Robert S. for suggesting scan.

• Robin Ryder for suggesting improvements to the triangle inequality and this odd one which requires the input to be in descending order (which just goes to show how important a flexible input format is).

• and finally Nick Kennedy for the following:

R, 40 bytes

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

Try it online!

Answer 3

Haskell, 49 bytes

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

Try it online!

Recursively generates all subsequences of l (reversed), and checks which length-3 ones form triangles.

50 bytes

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

Try it online!

The same idea, generating the subsequences with mapM, by mapping each value in l either to itself (include) or 0 (exclude).

50 bytes

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

Try it online!

Tries every partition point to take the middle element b.

51 bytes

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

Try it online!

The function q=scanr(:)[] generates the list of suffixes. A lot of trouble comes from needing to consider including equal elements the right number of times.

52 bytes

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

Try it online!

The helper function q=scanr(:)[] generates the list of suffixes.

57 bytes

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

Try it online!

Answer 4

Brachylog, 11 bytes

{⊇Ṫ.k+>~t}ᶜ

Try it online!

I may have forgotten to take advantage of the sorted input in my old solution:

Brachylog, 18 17 15 bytes

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

Try it 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.

Answer 5

Perl 6, 35 bytes

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

Try it online!

Explanation

It's a Whatever code, i. e. a concise notation for lambda functions (that works only in very simple cases). Each * is a placeholder for one argument. So we take the list of lengths (that appears at the first *), make all combinations of 3 elements (they always come out in the same order as in the original list, so that means the combinations are sorted too), flatten the list, and then take the list 3-by-3, and filter (grep) only those triplets that satisfy *+*>*, i. e. that the sum of the first two arguments is greater than the third. That gives all the triplets, and we finally count them with forcing numeric context with a +.

(Of course we need to test it only for the case of "sum of two smaller > the largest". If this holds, the other hold trivially, if this does not, the triplet does not denote correct triangle lengths and we don't need to look further.)

Answer 6

Python 3, 73 bytes

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

Try it online!

This is the first naive, brute-force approach that comes to my mind. I'll update the post if I find a shorter solution using a different approach. Note that since the input is sorted, the tuple \$(a,b,c)\$ is also in the ascending order so it suffices to only check whether \$a+b>c\$ holds.

Answer 7

Retina, 55 bytes

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

Try it online! Link includes test cases, but with the values in the 5th case reduced to allow it to finish today. Assumes sorted input. Explanation: Regexes don't really like matching more than one thing. A normal regex would be able to find all of the values that could be a shortest leg of a triangle. Retina's v option doesn't help here, except to avoid a lookahead. However Retina's w option is slightly more helpful, as it would be able to find both the shortest and longest leg at the same time. That's not enough for this challenge though, as there might be multiple middle legs.

\d+
*

Convert the input to unary.

L$`_+

For each input number...

$<'

... create a line that's the original array truncated to start at that number. $' normally means the string after the match, but the < modifies it to mean the string after the previous separator, avoiding wasting 2 bytes on $&. Each line therefore represents all potential solutions using that number as the shortest leg.

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

For each of those lines, find all possible middle and longest legs, but ensuring that the difference is less than the first leg. Output a _ for each matching combination of legs.

_

Count the total number of triangles found.

Answer 8

05AB1E, 12 10 9 bytes

My first time using 05AB1E! Thanks to Grimmy for -1!

3.Æʒ`α›}g

Try it online! or test suite

A direct port of my Stax answer. Get all combinations of three entries and count those that could possibly form triangles. It's that counting part that really got me. I spend a load of bytes there. Bound to be some rookie mistake there.

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?

Answer 9

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

Try it 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:])

Try it online!

Answer 10

Octave / MATLAB, 33 bytes

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

Try it online!

Answer 11

JavaScript (ES6), 63 bytes

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

Try it online!

Answer 12

Zsh, 66 bytes

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

Try it online!

Relatively straightforward, taking advantage of the sorted input, and incrementing in the for header (the increment happens once per parent loop).

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

Answer 13

Pyth, 14 bytes

*1sm>sPded.cQ3

Try it 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 (also 14 bytes):

lfTm>sPded.cQ3

Answer 14

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

Try it online!

Saved 1 thanks to @ceilingcat

Answer 15

Excel VBA, 171 164 152 bytes

^{-26 bytes thanks to 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

Input is in the range A:A of the active sheet. Output is to the immediate window.

Since this looks at every combination of every cell in a column that's 2²⁰ cells tall (which is nearly 2⁶⁰ combinations), this code is... not fast. You could make it much faster but at the expense of bytes.

Answer 16

Java 8, 131 130 126 bytes

a->{int r=0,i=a.length,j,k,I,J,K;for(;i-->0;)for(I=a[j=i];j-->0;)for(J=a[k=j];k-->0;r+=I+J>K&I+K>J&J+K>I?1:0)K=a[k];return r;}

Straightforward approach. The triangle check is the same as my answer for the Is this a triangle? challenge.
-4 bytes thanks to @ceilingcat.

Try it online.

Explanation:

a->{                  // Method with integer-array parameter and integer return-type
  int r=0,            //  Result-integer, starting at 0
      i=a.length,j,k, //  Index-integers
      I,J,K;          //  Temp-integers
  for(;i-->0;)        //  Loop `i` in the range (length,0]:
    for(I=a[j=i];     //   Set `I` to the `i`th value
        j-->0;)       //   Inner loop `j` in the range (i,0]:
      for(J=a[k=j];   //    Set `J` to the `j`'th value
          k-->0       //    Inner loop `k` in the range (j,0]:
          ;           //      After every iteration:
           r+=        //       Increase the result by:
              I+J>K&I+K>J&J+K>I?
                      //        If `I`, `J`, and `K` form a triangle:
               1      //         Increase the result by 1
              :       //        Else:
               0)     //         Keep the result the same by increasing with 0
        K=a[k];       //     Set `K` to the `k`'th value
  return r;}          //  After the nested loops, return the result

Answer 17

Charcoal, 17 bytes

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

Try it online! Link is to verbose version of code. Assumes sorted input. Explanation:

   θ                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

Answer 18

Japt -x, 9 bytes

à3 ËÌÑ<Dx

Try it

à3 ®o <Zx

Try it

Answer 19

Wolfram Language (Mathematica), 37 35 bytes

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

Try it online!

Answer 20

Ruby, 41 bytes

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

Try it online!

Answer 21

Perl 5 (-p), 55 52 bytes

using regex backtracking, -3 bytes thanks to @Cows quack using ^ instead of (?!) to fail and backtrack.

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

or

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

TIO

Answer 22

Jelly, 9 bytes

œc3+>ƭ/€S

Try it online!

A monadic link taking a sorted list of integers as its argument and returning the number of triangles.

Explanation

œ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

Answer 23

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

Try it online!

A fun one.

Answer 24

J, 40 bytes

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

Try it online!

Answer 25

Nekomata + -n, 6 bytes

SƆ$đ+<

Attempt This Online!

SƆ$đ+<
S       Find a subset of the input
 Ɔ      Split the subset into the last element and the rest
  $đ    Check if the rest has exactly two elements
    +   Add these two elements
     <  Check if the last element is less than the sum

-n counts the number of solutions.

Answer 26

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

Try it online!

Brute force \$O(n^3)\$ algorithm. Takes input as a newline separated list and outputs the number of triangles, or an empty line for 0. This is probably allowable since SNOBOL treats the empty string as 0 for numerical calculations.

Answer 27

Scala, 280 bytes

280 bytes, it can be golfed much more.

---

Golfed version. Try it online!

def c(n:Int,l:List[Int]):List[List[Int]]=if(n==0)List(List())else if(n>l.size)List()else if(n==1)l.map(List(_))else{(for(i<-l.indices)yield{val h=l(i);val t=l.drop(i+1);c(n-1,t).map(h::_)}).toList.flatten}
def V(l:List[Int]):Int=c(3,l).count{case List(a,b,c)=>a+b>c&&a+c>b&&b+c>a}

Ungolfed version. Try it online!

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks._

object Main {
  def combination(n: Int, lst: List[Int]): List[List[Int]] = {
    if (n == 0) List(List())
    else if (n > lst.size) List()
    else if (n == 1) lst.map(List(_))
    else {
      (for (i <- lst.indices) yield {
        val head = lst(i)
        val tail = lst.drop(i + 1)
        combination(n - 1, tail).map(head :: _)
      }).toList.flatten
    }
  }

  def countValidTriangles(lst: List[Int]): Int = {
    val combinations = combination(3, lst)
    combinations.count {
      case List(a, b, c) => a + b > c && a + c > b && b + c > a
    }
  }

  def main(args: Array[String]): Unit = {
    val testCases = List(
      (List(1, 2, 3), 0),
      (List(1, 1, 1), 1),
      (List(1, 2, 3, 4), 1),
      (List(3, 4, 5, 7), 3),
      (List(1, 42, 69, 666, 1000000), 0),
      (List(12, 23, 34, 45, 56, 67, 78, 89), 34),
      (List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 50)
    )

    for ((lst, expected) <- testCases) {
      val output = countValidTriangles(lst)
      assert(output == expected, (lst, output, expected))
    }
  }
}

Answer 28

JavaScript (Node.js), 49 bytes

f=([v,...x],a,b)=>v?f(x,a,b)+(b?a+b>v:f(x,v,a)):0

Try it online!

Answer 29

Uiua, 27 bytes (SBCS)

/+≡(|1<+/∘⇌)≐▽▽=3≡/+.⋯⇡ⁿ⧻,2

Try it online!

Explanation

            ≐▽▽=3≡/+.⋯⇡ⁿ⧻,2   # Get all length 3 combinations
                           2   # Put 2 on the stack
                          ,    # Copy the array onto the stack
                         ⧻     # Get the length of the array
                        ⁿ      # Raise 2 to the power of the length
                       ⇡       # Create an array of all natural numbers less than the result
                     ⋯         # Convert to binary
                    .          # Copy the result
                 ≡/+           # For each binary number, add up the bits
               =3              # Check which add up to three
              ▽                # Keep rows of the binary array where the number of 1s is 3
            ≐▽                 # For each of the remaining binary numbers,
                               # keep items in the original array
/+≡(|1<+/∘⇌)                   # Calculate number of triangles
  ≡(|1     )                   # For each row in the resulting array:
          ⇌                    # Reverse the array
        /∘                     # Put the items onto the stack
       +                       # Add the first two numbers
      <                        # Check if the third number is less than the result
/+                             # Add up all the triangles

As part of this, I made the combinations part generic. This might be useful for future golfing. If someone can find a shorter way of doing this part, it may help many people.

≐▽▽=⊙(≡/+.⋯⇡ⁿ⧻,2)

Try it online!