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).a + b > c . a + b > c a + c > b b + c > a
- Las tres longitudes laterales deben aparecer en posiciones distintas en la lista, pero no necesariamente tienen que ser distintas por pares.
- El orden de los tres números en la lista de entrada no importa. Si consideramos una lista
a
y los tres númerosa[i], a[j], a[k]
(dondei,j,k
son 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 n
números de Fibonacci ( A000045 ) este es A000004 .
[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?Respuestas:
R ,
62524034 bytesPrué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 aa+b-c>0
. Ela+b-c
es capturado sucintamente por el producto de matriz[1,1,-1] * X
, dondeX
están las 3 combinaciones de la matriz de entrada.Hubo muchas sugerencias de mejoras hechas por 3 personas diferentes en los comentarios:
Robert S. por sugerir
scan
.Robin Ryder por sugerir mejoras a la desigualdad del triángulo y esta extraña que requiere que la entrada esté en orden descendente (lo que demuestra lo importante que es un formato de entrada flexible).
y finalmente Nick Kennedy por lo siguiente:
R , 40 bytes
Pruébalo en línea!
fuente
x[3]<x[1]+x[2]
es equivalente a2*x[3]<sum(x)
: 51 bytes[
alias es ingenioso , realmente limpia el enfoque.Stax ,
87 bytesGracias a recursivo por -1!
¡Ejecútelo y depúrelo en staxlang.xyz!
Desempaquetado (8 bytes) y explicación:
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
o
al principio para 8 bytes.fuente
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.Haskell , 49 bytes
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
Pruébalo en línea!
La misma idea, generar las subsecuencias con
mapM
, mapeando cada valor enl
sí mismo (incluir) o0
(excluir).50 bytes
Pruébalo en línea!
Intenta cada punto de partición para tomar el elemento del medio
b
.51 bytes
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
Pruébalo en línea!
La función auxiliar
q=scanr(:)[]
genera la lista de sufijos.57 bytes
Pruébalo en línea!
fuente
Brachylog , 11 bytes
Pruébalo en línea!
Puede que haya olvidado aprovechar la entrada ordenada en mi solución anterior:
Brachylog ,
181715 bytesPruébalo en línea!
fuente
Perl 6 , 35 bytes
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á.)
fuente
Retina , 55 bytes
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
v
opción de Retina no ayuda aquí, excepto para evitar mirar hacia adelante. Sin embargo, law
opció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.Convierta la entrada a unario.
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.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.
fuente
Python 3 , 73 bytes
Pruébalo en línea!
fuente
Python 2 , 72 bytes
Pruébalo en línea!
73 bytes
Pruébalo en línea!
fuente
05AB1E ,
12109 bytes¡Mi primera vez usando 05AB1E! Gracias a [Grimy] por -1!
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í.
fuente
ì
(invertir cada uno) antes del filtro en lugar delŠ
(intercambio triple) dentro del filtro. Alternativamente, también puede usar enε...}O
lugar 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 innecesarioy
que se puede eliminar. :) Bonita primera respuesta, así que +1 de mi parte.3.ÆʒRÆd_}g
, que es el mismo bytecount.3.Æʒ`α›}g
es 9.JavaScript (ES6), 63 bytes
Pruébalo en línea!
fuente
Octava / MATLAB, 33 bytes
Pruébalo en línea!
fuente
Zsh , 66 bytes
Pruébalo en línea!
Relativamente sencillo, aprovechando la entrada ordenada e incrementando en el
for
encabezado (el incremento ocurre una vez por ciclo principal ).fuente
Excel VBA,
171164152 bytes-26 bytes gracias a TaylorScott
La entrada está en el rango
A:A
de 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.
fuente
()
en la declaración secundaria, el espacioDebug.? r
y puede colocarloNext:Next:Next
enNext k,j,i
. aparte de eso, bueno, sigue haciendo combinaciones de 2 ** 60 pero funcionar=r-(a+b>c)*(b+c>a)*(c+a>b)
Carbón , 17 bytes
Pruébalo en línea! El enlace es a la versión detallada del código. Asume una entrada ordenada. Explicación:
fuente
Japt
-x
, 9 bytesIntentalo
Intentalo
fuente
Wolfram Language (Mathematica) ,
3735 bytesPruébalo en línea!
fuente
Ruby , 41 bytes
Pruébalo en línea!
fuente
Pyth , 14 bytes
Pruébalo en línea!
Alternativa (también 14 bytes):
fuente
Perl 5 (
-p
),5552 bytesusando regex backtracking, -3 bytes gracias a @Cows quack using en
^
lugar de(?!)
fallar y retroceder.o
TIO
fuente
(?!)
ser^
?Jalea , 9 bytes
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
Alternativa 9s:
fuente
J , 40 bytes
Pruébalo en línea!
fuente
Bash , 123 bytes
Pruébalo en línea!
Una divertida
fuente
SNOBOL4 (CSNOBOL4) , 181 bytes
Pruébalo en línea!
0
0
fuente
C (clang) , 83 bytes
Pruébalo en línea!
Guardado 1 gracias a @ceilingcat
fuente