27
\$\begingroup\$

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.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ I think the challenge could be clearer about what counts as a distinct triangle. From the A000292 link, I take it [1,1,1,1] allows 4 "different" triangles, all [1,1,1], to be chosen using any three of the 1's? But, it's not 24 because the three 1's are chosen unordered, i.e. it's a subset of three indices rather than an ordered list? \$\endgroup\$
    – xnor
    Aug 27, 2019 at 19:22
  • 2
    \$\begingroup\$ @xnor Thatnks for pointing this out, that all seems correct - I just added a point in the details. I hope that makes it clearer now. \$\endgroup\$
    – flawr
    Aug 27, 2019 at 19:28

29 Answers 29

10
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ r3SFE+<+ packs to 7. It uses a foreach loop to add the filter results. Addition is one of the operations that's a no-op when only a single element is present. \$\endgroup\$
    – recursive
    Aug 27, 2019 at 23:52
10
\$\begingroup\$

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:

R, 40 bytes

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

Try it online!

\$\endgroup\$
8
  • \$\begingroup\$ What about this? \$\endgroup\$
    – Robert S.
    Aug 27, 2019 at 21:20
  • 3
    \$\begingroup\$ x[3]<x[1]+x[2] is equivalent to 2*x[3]<sum(x): 51 bytes \$\endgroup\$ Aug 27, 2019 at 21:25
  • 4
    \$\begingroup\$ Actually, make that 45 bytes. Sorry for the multiple comments! \$\endgroup\$ Aug 27, 2019 at 21:42
  • 1
    \$\begingroup\$ @RobinRyder That [ alias is slick, really cleans up the approach. \$\endgroup\$ Aug 28, 2019 at 10:37
  • 2
    \$\begingroup\$ 40 \$\endgroup\$ Aug 28, 2019 at 11:41
6
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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?
\$\endgroup\$
4
  • 2
    \$\begingroup\$ I'm sure Grimy will come up with something shorter, since he usually does on my answers. ;) But your answer looks fairly similar what I had in mind. Only difference is that I've used ì (reverse each) before the filter instead of the Š (triple swap) inside the filter. Alternatively, you could also use ε...}O instead of ʒ...}g, but the byte-count remains the same. PS: Your byte count of 10 and TIO are correct, but your actual answer still has an unnecessary explicit y which can be removed. :) Nice first answer though, so +1 from me. \$\endgroup\$ Aug 28, 2019 at 7:19
  • \$\begingroup\$ Sorry to disappoint @KevinCruijssen, all I have is 3.ÆʒRÆd_}g, which is the same bytecount. \$\endgroup\$
    – Grimmy
    Aug 28, 2019 at 16:28
  • 2
    \$\begingroup\$ @KevinCruijssen Oh actually I guess 3.Æʒ`α›}g is 9. \$\endgroup\$
    – Grimmy
    Aug 28, 2019 at 16:30
  • \$\begingroup\$ @Grimy Haha, knew it. xD Pretty straight-forward golf now that I see it.. But you're usually better in coming up with those kind of golfs (or golfs in general..), as I mentioned in my first comment. ;p \$\endgroup\$ Aug 28, 2019 at 17:12
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Octave / MATLAB, 33 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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))
  }
}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
2
\$\begingroup\$

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 220 cells tall (which is nearly 260 combinations), this code is... not fast. You could make it much faster but at the expense of bytes.

\$\endgroup\$
2
  • \$\begingroup\$ You can drop the () in the sub statement, the space in Debug.? r and can drop Next:Next:Next to Next k,j,i. aside from that - well its still doing 2**60 combinations but it works \$\endgroup\$ Sep 1, 2019 at 4:42
  • \$\begingroup\$ Oh and hey, you can drop out some more by replacing the if line with r=r-(a+b>c)*(b+c>a)*(c+a>b) \$\endgroup\$ Sep 7, 2019 at 17:30
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Thanks \$\endgroup\$ Oct 19 at 8:07
1
\$\begingroup\$

Charcoal, 17 bytes

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

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
I                   Cast to string for implicit print
\$\endgroup\$
1
\$\begingroup\$

Japt -x, 9 bytes

à3 ËÌÑ<Dx

Try it

à3 ®o <Zx

Try it

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 37 35 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 41 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Can (?!) be ^? \$\endgroup\$
    – user41805
    Aug 28, 2019 at 10:47
  • \$\begingroup\$ thanks it fails/backtrack well \$\endgroup\$ Aug 28, 2019 at 11:47
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

J, 40 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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))
    }
  }
}
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.