Dada uma lista de números inteiros positivos, encontre o número de triângulos que podemos formar, de modo que seus comprimentos laterais sejam representados por três entradas distintas da lista de entrada.

(A inspiração vem do CR .)

Detalhes

• Um triângulo pode ser formado se todas as permutações dos três comprimentos laterais satisfizerem a desigualdade estrita do triângulo(Isso significa que , e devem ser mantidos.)$a,b,c$a + b > c . a + b > c a + c > b b + c > a $$a + b > c.$$ $a+b > c$$a+c>b$$b+c>a$
• Os três comprimentos laterais devem aparecer em posições distintas da lista, mas não precisam necessariamente ser distintos aos pares.$a,b,c$
• A ordem dos três números na lista de entrada não importa. Se considerarmos uma lista ae os três números a[i], a[j], a[k](em que i,j,kos pares são diferentes), (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])etc. todos serão considerados como o mesmo triângulo.
• Pode-se presumir que a lista de entrada contenha pelo menos três entradas.
• Você pode assumir que a lista de entrada está classificada em ordem crescente.

Exemplos

Um pequeno programa de teste pode ser encontrado aqui em Experimente 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

Para a entrada [1,2,3,...,n-1,n]deste é A002623 .

Para a entrada de [1,1,...,1](comprimento n), isso é A000292 .

Para a entrada dos primeiros nnúmeros de Fibonacci ( A000045 ), é A000004 .

R , 62 52 40 34 bytes

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

Experimente online!

Solução Octave do porto de Luis Mendo

Desde a<=b<=c, a condição do triângulo é equivalente a a+b-c>0. O a+b-cé capturado de forma sucinta pelo produto da matriz [1,1,-1] * X, onde Xestão as 3 combinações da matriz de entrada.

Houve muitas sugestões de melhorias feitas por três pessoas diferentes nos comentários:

• Robert S. por sugerirscan .

• Robin Ryder, por sugerir melhorias na desigualdade do triângulo, e essa estranha que exige que a entrada seja em ordem decrescente (o que apenas mostra o quão importante é um formato de entrada flexível).

• e finalmente Nick Kennedy para o seguinte:

R , 40 bytes

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

Experimente online!

Stax , 8 7 bytes

Obrigado ao recursivo por -1!

é═rê÷┐↨

Execute e depure-o em staxlang.xyz!

Descompactado (8 bytes) e explicação:

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

Esse é um truque legal. Se você tiver uma sequência de instruções que sempre resultará em 0 ou 1 e precisar contar os itens de uma matriz que produza o resultado verdadeiro no final do seu programa, F..+é um byte menor que {..f%.

Assume que a lista inicial está classificada em ordem crescente. Sem essa suposição, cole um ono início por 8 bytes.

Haskell , 49 bytes

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

Experimente online!

Gera recursivamente todas as subsequências de l(invertida) e verifica quais de comprimento 3 formam triângulos.

50 bytes

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

Experimente online!

A mesma idéia, gerando as subsequências com mapM, mapeando cada valor lpara si mesmo (incluir) ou 0(excluir).

50 bytes

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

Experimente online!

Tenta cada ponto de partição para pegar o elemento do meio b.

51 bytes

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

Experimente online!

A função q=scanr(:)[]gera a lista de sufixos. Muitos problemas advêm da necessidade de considerar a inclusão de elementos iguais o número certo de vezes.

52 bytes

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

Experimente online!

A função auxiliar q=scanr(:)[]gera a lista de sufixos.

57 bytes

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

Experimente online!

Braquilog , 11 bytes

{⊇Ṫ.k+>~t}ᶜ

Experimente online!

Talvez eu tenha esquecido de aproveitar as entradas classificadas na minha solução antiga:

Brachylog , 18 17 15 bytes

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

Experimente 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(*+*>*)

Experimente online!

Explicação

É um código Whatever, ou seja, uma notação concisa para funções lambda (que funciona apenas em casos muito simples). Cada *um é um espaço reservado para um argumento. Então, pegamos a lista de comprimentos (que aparece no primeiro *), fazemos todas as combinações de 3 elementos (elas sempre saem na mesma ordem que na lista original, de modo que significa que as combinações também são classificadas), achatamos a lista, e depois pegue a lista 3 por 3 e filtre ( grep) apenas os trigêmeos que satisfazem *+*>*, ou seja, que a soma dos dois primeiros argumentos seja maior que o terceiro. Isso fornece todos os trigêmeos, e finalmente os contamos forçando o contexto numérico com a +.

(É claro que precisamos testá-lo apenas para o caso de "soma de dois menores> o maior". Se isso ocorrer, o outro será trivial, se isso não acontecer, o trigêmeo não indica comprimentos de triângulo corretos e não o fazemos. precisa procurar mais.)

Retina , 55 bytes

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

Experimente online! O link inclui casos de teste, mas com os valores no quinto caso reduzidos para permitir que ele termine hoje. Pressupõe entrada classificada. Explicação: As expressões regulares não gostam muito de corresponder a mais de uma coisa. Um regex normal seria capaz de encontrar todos os valores que poderiam ser a menor perna de um triângulo. A vopção de Retina não ajuda aqui, exceto para evitar uma reação contrária. No entanto, a wopção de Retina é um pouco mais útil, pois seria possível encontrar a perna mais curta e a mais longa ao mesmo tempo. Isso não é suficiente para esse desafio, pois pode haver várias pernas do meio.

\d+
*

Converta a entrada para unário.

L$`_+

Para cada número de entrada ...

$<'

... crie uma linha com a matriz original truncada para iniciar nesse número. $'normalmente significa a sequência após a correspondência, mas a <modifica para significar a sequência após o separador anterior, evitando desperdiçar 2 bytes $&. Cada linha, portanto, representa todas as soluções possíveis usando esse número como a perna mais curta.

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

Para cada uma dessas linhas, encontre todas as pernas médias e mais longas possíveis, mas garanta que a diferença seja menor que a primeira perna. Saída a _para cada combinação de pernas correspondente.

_

Conte o número total de triângulos encontrados.

Python 3 , 73 bytes

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

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

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

Experimente online!

05AB1E , 12 10 9 bytes

Minha primeira vez usando 05AB1E! Obrigado a [Grimy] por -1!

3.Æʒ`α›}g

Experimente online! ou suíte de teste

Uma porta direta da minha resposta Stax. Obtenha todas as combinações de três entradas e conte as que possam formar triângulos. É essa parte da contagem que realmente me pegou. Eu gasto uma carga de bytes lá. Vinculado a ser algum erro de novato lá.

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 bytes

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

Experimente online!

Oitava / MATLAB, 33 bytes

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

Experimente online!

Zsh , 66 bytes

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

Experimente online!

Relativamente simples, aproveitando a entrada classificada e aumentando o forcabeçalho (o incremento acontece uma vez por loop pai ).

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 graças a 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

A entrada está no intervalo A:A da planilha ativa. A saída é para a janela imediata.

Como isso examina todas as combinações de todas as células de uma coluna com 2 ²⁰ células de altura (que são quase 2 ⁶⁰ combinações), esse código é ... não rápido. Você poderia torná-lo muito mais rápido, mas à custa de bytes.

Carvão , 17 bytes

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

Experimente online! Link é a versão detalhada do código. Pressupõe entrada classificada. Explicação:

   θ                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

Japonês -x , 9 bytes

à3 ËÌÑ<Dx

Tente

à3 ®o <Zx

Tente

Wolfram Language (Mathematica) , 37 35 bytes

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

Experimente online!

Ruby , 41 bytes

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

Experimente online!

Pitão , 14 bytes

*1sm>sPded.cQ3

Experimente 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

Alternativa (também 14 bytes):

lfTm>sPded.cQ3

Perl 5 ( -p), 55 52 bytes

usando regex backtracking, -3 bytes graças ao @Cows quack usando em ^vez de (?!)falhar e voltar.

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

ou

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

TIO

Geléia , 9 bytes

œc3+>ƭ/€S

Experimente online!

Um link monádico usando uma lista classificada de números inteiros como argumento e retornando o número de triângulos.

Explicação

œc3       | Combinations of length 3
     ƭ/€  | Reduce each using each of the following in turn:
   +      | - Add
    >     | - Greater than
        S | Sum (counts the 1s)

9s alternativos:

œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S

J , 40 bytes

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

Experimente 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

Experimente online!

Um divertido.

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

Experimente online!

Força bruta $O(n^3)$algoritmo. Recebe a entrada como uma lista separada por nova linha e gera o número de triângulos ou uma linha vazia para 0. Provavelmente, isso é permitido, já que o SNOBOL trata a sequência vazia como 0nos cálculos numéricos.

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

Experimente online!

Guardado 1 graças a @ceilingcat