Cuenta la cantidad de triángulos

22

Dada una lista de enteros positivos, encuentre el número de triángulos que podemos formar de modo que sus longitudes laterales estén representadas por tres entradas distintas de la lista de entrada.

(La inspiración viene de CR .)

Detalles

  • Se puede formar un triángulo si todas las permutaciones de las tres longitudes laterales satisfacen la estricta desigualdad del triángulo(Esto significa que , y deben mantenerse).una,si,doa + b > c . a + b > c a + c > b b + c > a
    una+si>do.
    una+si>douna+do>sisi+do>una
  • Las tres longitudes laterales deben aparecer en posiciones distintas en la lista, pero no necesariamente tienen que ser distintas por pares.una,si,do
  • El orden de los tres números en la lista de entrada no importa. Si consideramos una lista ay los tres números a[i], a[j], a[k](donde i,j,kson diferentes por pares), entonces (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])todos se consideran como el mismo triángulo.
  • Se puede suponer que la lista de entrada contiene al menos 3 entradas.
  • Puede suponer que la lista de entrada está ordenada en orden ascendente.

Ejemplos

Puede encontrar un pequeño programa de prueba aquí en ¡ Pruébelo en línea!

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 la entrada de [1,2,3,...,n-1,n]esto es A002623 .

Para la entrada de [1,1,...,1](longitud n) este es A000292 .

Para la entrada de los primeros nnúmeros de Fibonacci ( A000045 ) este es A000004 .

falla
fuente
44
Creo que el desafío podría ser más claro sobre lo que cuenta como un triángulo distinto. Desde el enlace A000292 , supongo que se pueden elegir [1,1,1,1]4 triángulos "diferentes", todos [1,1,1], utilizando cualquiera de los tres. Pero, ¿no es 24 porque los tres 1 se eligen sin orden, es decir, es un subconjunto de tres índices en lugar de una lista ordenada?
xnor
2
@xnor Gracias por señalar esto, todo parece correcto: acabo de agregar un punto en los detalles. Espero que eso lo aclare ahora.
error

Respuestas:

10

R , 62 52 40 34 bytes

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

Pruébalo en línea!

Solución de octava del puerto de Luis Mendo

Como a<=b<=c, la condición del triángulo es equivalente a a+b-c>0. El a+b-ces capturado sucintamente por el producto de matriz [1,1,-1] * X, donde Xestán las 3 combinaciones de la matriz de entrada.

Hubo muchas sugerencias de mejoras hechas por 3 personas diferentes en los comentarios:

R , 40 bytes

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

Pruébalo en línea!

Giuseppe
fuente
3
x[3]<x[1]+x[2]es equivalente a 2*x[3]<sum(x): 51 bytes
Robin Ryder
44
En realidad, haz que 45 bytes . Perdón por los múltiples comentarios!
Robin Ryder
1
@RobinRyder Ese [alias es ingenioso , realmente limpia el enfoque.
CriminallyVulgar
2
40
Nick Kennedy
9

Stax , 8 7 bytes

Gracias a recursivo por -1!

é═rê÷┐↨

¡Ejecútelo y depúrelo en staxlang.xyz!

Desempaquetado (8 bytes) y explicación:

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

Ese es un buen truco. Si tiene una secuencia de instrucciones que siempre dará como resultado 0 o 1 y necesita contar los elementos de una matriz que produce el resultado verdadero al final de su programa, F..+es un byte más corto que {..f%.

Asume que la lista inicial está ordenada ascendente. Sin este supuesto, pegue un oal principio para 8 bytes.

Khuldraeseth na'Barya
fuente
1
r3SFE+<+paquetes a 7. Utiliza un bucle foreach para agregar los resultados del filtro. La adición es una de las operaciones que no funciona cuando solo hay un elemento presente.
recursivo el
6

Haskell , 49 bytes

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

Pruébalo en línea!

Recursivamente genera todas las subsecuencias de l(invertidas) y verifica cuáles de longitud 3 forman triángulos.

50 bytes

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

Pruébalo en línea!

La misma idea, generar las subsecuencias con mapM, mapeando cada valor en lsí mismo (incluir) o 0(excluir).

50 bytes

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

Pruébalo en línea!

Intenta cada punto de partición para tomar el elemento del medio b.

51 bytes

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

Pruébalo en línea!

La función q=scanr(:)[]genera la lista de sufijos. Muchos problemas provienen de la necesidad de considerar la inclusión de elementos iguales la cantidad correcta de veces.

52 bytes

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

Pruébalo en línea!

La función auxiliar q=scanr(:)[]genera la lista de sufijos.

57 bytes

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

Pruébalo en línea!

xnor
fuente
4

Brachylog , 11 bytes

{⊇Ṫ.k+>~t}ᶜ

Pruébalo en línea!

Puede que haya olvidado aprovechar la entrada ordenada en mi solución anterior:

Brachylog , 18 17 15 bytes

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

Pruébalo en línea!

{            }ᶜ    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.
Cadena no relacionada
fuente
4

Perl 6 , 35 bytes

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

Pruébalo en línea!

Explicación

Es un código Cualquiera, es decir, una notación concisa para funciones lambda (que funciona solo en casos muy simples). Cada uno *es un marcador de posición para un argumento. Por lo tanto, tomamos la lista de longitudes (que aparece al principio *), hacemos todas las combinaciones de 3 elementos (siempre salen en el mismo orden que en la lista original, lo que significa que las combinaciones también se ordenan), aplanar la lista, y luego tome la lista 3 por 3, y filtre ( grep) solo aquellos tripletes que satisfagan *+*>*, es decir, que la suma de los dos primeros argumentos es mayor que el tercero. Eso da todos los trillizos, y finalmente los contamos forzando el contexto numérico con a +.

(Por supuesto, necesitamos probarlo solo para el caso de "suma de dos más pequeños> el más grande". Si esto se cumple, el otro se mantiene trivialmente, si esto no es así, el triplete no indica las longitudes correctas de los triángulos y no lo hacemos Necesito mirar más allá.)

Ramillies
fuente
4

Retina , 55 bytes

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

Pruébalo en línea! Link incluye casos de prueba, pero con los valores en el quinto caso reducidos para permitir que termine hoy. Asume una entrada ordenada. Explicación: a las expresiones regulares no les gusta hacer coincidir más de una cosa. Una expresión regular normal sería capaz de encontrar todos los valores que podrían ser el tramo más corto de un triángulo. La vopción de Retina no ayuda aquí, excepto para evitar mirar hacia adelante. Sin embargo, la wopción de Retina es un poco más útil, ya que sería capaz de encontrar la pierna más corta y la más larga al mismo tiempo. Sin embargo, eso no es suficiente para este desafío, ya que puede haber múltiples piernas medias.

\d+
*

Convierta la entrada a unario.

L$`_+

Para cada número de entrada ...

$<'

... crea una línea que es la matriz original truncada para comenzar en ese número. $'normalmente significa la cadena después de la coincidencia, pero la <modifica para que signifique la cadena después del separador anterior, evitando desperdiciar 2 bytes $&. Por lo tanto, cada línea representa todas las posibles soluciones utilizando ese número como el tramo más corto.

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

Para cada una de esas líneas, encuentre todas las patas intermedias y más largas posibles, pero asegurándose de que la diferencia sea menor que la primera pata. Salida a _para cada combinación de patas correspondiente.

_

Cuenta el número total de triángulos encontrados.

Neil
fuente
3

Python 3 , 73 bytes

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

Pruébalo en línea!

(una,si,do)una+si>do

Joel
fuente
3

05AB1E , 12 10 9 bytes

¡Mi primera vez usando 05AB1E! Gracias a [Grimy] por -1!

3.Æʒ`α›}g

Pruébalo en línea! o suite de prueba

Un puerto directo de mi respuesta Stax. Obtenga todas las combinaciones de tres entradas y cuente las que posiblemente podrían formar triángulos. Es esa parte de contar lo que realmente me atrapó. Me paso una carga de bytes allí. Atado a ser un error de novato allí.

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?
Khuldraeseth na'Barya
fuente
2
Estoy seguro de que a Grimy se le ocurrirá algo más corto, ya que generalmente lo hace con mis respuestas. ;) Pero tu respuesta se parece bastante a lo que tenía en mente. La única diferencia es que he usado ì(invertir cada uno) antes del filtro en lugar del Š(intercambio triple) dentro del filtro. Alternativamente, también puede usar en ε...}Olugar de ʒ...}g, pero el recuento de bytes sigue siendo el mismo. PD: Su número de bytes de 10 y TIO son correctos, pero su respuesta real todavía tiene un explícito innecesario yque se puede eliminar. :) Bonita primera respuesta, así que +1 de mi parte.
Kevin Cruijssen
Lamento decepcionar a @KevinCruijssen, todo lo que tengo es 3.ÆʒRÆd_}g, que es el mismo bytecount.
Grimmy
2
@KevinCruijssen Oh, supongo que 3.Æʒ`α›}ges 9.
Grimmy
@Grimy Jaja, lo sabía. xD Golf bastante sencillo ahora que lo veo ... Pero, por lo general, es mejor que se te ocurra ese tipo de golf (o golf en general ...), como mencioné en mi primer comentario. ; p
Kevin Cruijssen
2

JavaScript (ES6), 63 bytes

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

Pruébalo en línea!

Arnauld
fuente
2

Zsh , 66 bytes

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

Pruébalo en línea!

Relativamente sencillo, aprovechando la entrada ordenada e incrementando en el forencabezado (el incremento ocurre una vez por ciclo principal ).

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))
  }
}
Función Gamma
fuente
2

Excel VBA, 171 164 152 bytes

-26 bytes gracias 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

La entrada está en el rango A:Ade la hoja activa. La salida es a la ventana inmediata.

Dado que esto examina cada combinación de cada celda en una columna que tiene 2 20 celdas de alto (que es casi 2 60 combinaciones), este código no es ... rápido. Podrías hacerlo mucho más rápido pero a expensas de los bytes.

Tostadas de ingeniero
fuente
Puede colocar el ()en la declaración secundaria, el espacio Debug.? ry puede colocarlo Next:Next:Nexten Next k,j,i. aparte de eso, bueno, sigue haciendo combinaciones de 2 ** 60 pero funciona
Taylor Scott,
Ah, oye, puedes abandonar un poco más reemplazando la línea if conr=r-(a+b>c)*(b+c>a)*(c+a>b)
Taylor Scott,
1

Carbón , 17 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Asume una entrada ordenada. Explicación:

   θ                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
Neil
fuente
1

Pyth , 14 bytes

*1sm>sPded.cQ3

Pruébalo en línea!

          .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 (también 14 bytes):

lfTm>sPded.cQ3
ar4093
fuente
1

Perl 5 ( -p), 55 52 bytes

usando regex backtracking, -3 bytes gracias a @Cows quack using en ^lugar de (?!)fallar y retroceder.

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

o

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

TIO

Nahuel Fouilleul
fuente
Puede (?!)ser ^?
Kritixi Lithos
gracias falla / retrocede bien
Nahuel Fouilleul
1

Jalea , 9 bytes

œc3+>ƭ/€S

Pruébalo en línea!

Un enlace monádico que toma una lista ordenada de enteros como argumento y devuelve el número de triángulos.

Explicación

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

Alternativa 9s:

œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S
Nick Kennedy
fuente
0

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

Pruébalo en línea!

Una divertida

golpear
fuente
0

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

Pruébalo en línea!

O(norte3)00

Giuseppe
fuente
0

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

Pruébalo en línea!

Guardado 1 gracias a @ceilingcat

AZTECCO
fuente