23
3
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 numbersa[i], a[j], a[k]
(wherei,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.
4
I think the challenge could be clearer about what counts as a distinct triangle. From the A000292 link, I take it
– xnor – 2019-08-27T19:22:46.067[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?2@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. – flawr – 2019-08-27T19:28:02.413