22
\$\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\$
  • 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 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 at 19:28

24 Answers 24

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\$
  • \$\begingroup\$ What about this? \$\endgroup\$ – Robert S. Aug 27 at 21:20
  • 3
    \$\begingroup\$ x[3]<x[1]+x[2] is equivalent to 2*x[3]<sum(x): 51 bytes \$\endgroup\$ – Robin Ryder Aug 27 at 21:25
  • 4
    \$\begingroup\$ Actually, make that 45 bytes. Sorry for the multiple comments! \$\endgroup\$ – Robin Ryder Aug 27 at 21:42
  • 1
    \$\begingroup\$ @RobinRyder That [ alias is slick, really cleans up the approach. \$\endgroup\$ – CriminallyVulgar Aug 28 at 10:37
  • 2
    \$\begingroup\$ 40 \$\endgroup\$ – Nick Kennedy Aug 28 at 11:41
9
\$\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
    \$\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 at 23:52
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\$
4
\$\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\$
4
\$\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\$

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\$
3
\$\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\$
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\$

05AB1E, 12 10 9 bytes

My first time using 05AB1E! Thanks to [Grimy] 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\$
  • 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\$ – Kevin Cruijssen Aug 28 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 at 16:28
  • 2
    \$\begingroup\$ @KevinCruijssen Oh actually I guess 3.Æʒ`α›}g is 9. \$\endgroup\$ – Grimmy Aug 28 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\$ – Kevin Cruijssen Aug 28 at 17:12
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\$

Octave / MATLAB, 33 bytes

@(x)sum(nchoosek(x,3)*[1;1;-1]>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\$

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\$
  • \$\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\$ – Taylor Scott Sep 1 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\$ – Taylor Scott Sep 7 at 17:30
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\$

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\$
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\$
  • \$\begingroup\$ Can (?!) be ^? \$\endgroup\$ – Kritixi Lithos Aug 28 at 10:47
  • \$\begingroup\$ thanks it fails/backtrack well \$\endgroup\$ – Nahuel Fouilleul Aug 28 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\$

J, 40 bytes

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

Try it online!

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

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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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