Altura de pila de tazón
El objetivo de este rompecabezas es calcular la altura de una pila de cuencos.
Un cuenco se define como un dispositivo radialmente simétrico sin espesor. Su forma de silueta es un polinomio uniforme. La pila se describe mediante una lista de radios, cada uno asociado con un polinomio par, dado como entrada como una lista de coeficientes (por ejemplo, la lista 3.1 4.2
representa el polinomio ).
El polinomio puede tener un grado arbitrario. Para simplificar, la altura de la pila se define como la altitud del centro del tazón más alto (vea el diagrama del Ejemplo 3 para una ilustración).
Los casos de prueba están en el formato radius:coeff1 coeff2 ...
: cada línea comienza con un número flotante que representa el radio del tazón, seguido de dos puntos y una lista separada por espacios que contiene los coeficientes para las potencias pares, comenzando con la potencia 2 (implica una parte constante de cero) . Por ejemplo, la línea 2.3:3.1 4.2
describe un tazón de radio 2.3
y el polinomio de forma 3.1 * x^2 + 4.2 * x^4
.
Ejemplo 1
42:3.141
describe un montón de altura cero ya que un solo tazón no tiene altura.
Ejemplo 2
1:1 2
1.2:5
1:3
describe un montón de altura 2.0
(ver diagrama).
Ejemplo 3
1:1.0
0.6:0.2
0.6:0.4
1.4:0.2
0.4:0 10
describe un montón de altura 0.8 (ver flecha verde en la gráfica).
Este es el código de golf, por lo que gana el código más corto.
Tengo codigo de referencia .
Editar:
La implementación de referencia se basa en una biblioteca para calcular las raíces de los polinomios. Puede hacer eso también, pero no es necesario. Dado que la implementación de referencia es solo una aproximación numérica (bastante buena), aceptaré cualquier código que produzca resultados correctos dentro de las tolerancias de punto flotante comunes.
Otra variante de este rompecabezas es minimizar la altura reordenando los tazones. No estoy seguro de si hay una solución rápida (supongo que es NP-hard). Si alguien tiene una mejor idea (o puede probar que NP está completa), ¡dígamelo!
fuente
is_maximum
debería ser, por ejemploreturn evaluate(differentiate(shape_0), root) > 0.0
. Actualmente, evalúa la raíz utilizandodd
(derivada de la diferencia entre formas), que siempre debe devolver 0 (para raíces). Debido a errores de coma flotante, el resultado es ocasionalmente un valor positivo cercano a 0, razón por la cual el código genera un resultado correcto o más preciso en algunas ocasiones. Verifique la entrada1:0.2, 1:0.1 0.2
que debería salir0.0125
0.801
. Los dos tazones finales se tocan en radio0.1
.Respuestas:
Gelatina ,
5453 bytesPruébalo en línea!
Un enlace monádico que toma como argumento la lista de cuencos de arriba a abajo en el formato
[[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]
y devuelve la posición y del fondo del cuenco superior.Ahora maneja correctamente los tazones que se encuentran en lugares distintos del radio mínimo.
Explicación
Enlace auxiliar: toma como argumento izquierdo
l
las diferencias en los coeficientes de los polinomios que representan los cuencos desde 1 hacia arriba, y su argumento derechor
el radio mínimo; devuelve el valor y máximo donde se encuentran los dos tazonesEnlace principal, toma un montón de bol como argumento y devuelve el valor y de la base del bol superior
Referencia de Python
Finalmente, aquí hay una versión TIO de la referencia de Python que @pasbi incluyó para el problema principal. Se lee de stdin.
fuente
(r1, p1)
y(r2, p2)
en el puntomin(r1, r2)
. Si es así, esa sería una solución incorrecta porque dos tazones pueden tocar entre0
ymin(r1, r2))
. Necesita encontrarmax(p1(x)-p2(x), 0)
en toda la gama[0, min(r1, r2)]
parax
. Es por eso que la solución de referencia de @ pasbi calcula derivados para encontrar el máximo local.min(r1, r2)
. Esto ahora resuelve el desafío adicional de @ attinatPython 3 + numpy + scipy,
248240 bytesPruébalo en línea!
-8 bytes gracias a @xnor
La función toma una lista de
[radius, polynomial]
pares como entrada y devuelve la altura de la pila.Esta solución utiliza más o menos el mismo algoritmo que el código de referencia, excepto que no calcula el máximo utilizando derivados. Mientras tanto, está escrito usando funciones
numpy
yscipy
funciones integradas en Python. La versión sin golf se muestra a continuación. Esto sirve como una versión alternativa del código de referencia para aquellos que desean una versión más corta para capturar la idea rápidamente.Pruébalo en línea!
fuente
i=0
como argumento opcional.Wolfram Language (Mathematica) ,
10493 bytesPruébalo en línea!
{radius, polynomial}
Para la salida decimal en lugar de simbólica, use
NMaxValue
en su lugar (o simplemente invoqueN
el resultado).fuente
R ,
451436 bytesPruébalo en línea!
Pruébalo en línea!
En términos generales, un puerto R de mi respuesta Jelly, aunque como la base R no tiene ninguna función para encontrar las raíces de los polinomios, esto se implementa utilizando el método que se encuentra en
polynom::solve.polynomial
.Una función que toma una lista de vectores numéricos de arriba a abajo de la pila.
¡Gracias a @RobinRyder por jugar golf en 15 bytes!
fuente