Calcular la altura de la pila del tazón

19

Altura de pila de tazón

El objetivo de este rompecabezas es calcular la altura de una pila de cuencos.

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.2representa el polinomio 3.1x2+4.2x4 ).

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.2describe un tazón de radio 2.3y 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).

Parcela de una pila de tres cuencos

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).

Parcela de una pila de tres cuencos

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!

pasbi
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Mego
En su código de referencia, creo que el cuerpo de is_maximumdebería ser, por ejemplo return evaluate(differentiate(shape_0), root) > 0.0. Actualmente, evalúa la raíz utilizando dd(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 entrada 1:0.2, 1:0.1 0.2que debería salir0.0125
redundancia
@redundancy es en realidad redundante de todos modos. Se elige el valor máximo y y 0 siempre estará en los valores de comparación.
Nick Kennedy el
2
En el ejemplo 3, la altura final debería ser 0.801. Los dos tazones finales se tocan en radio 0.1.
attinat
Sí, obtuve el mismo resultado.
Joel

Respuestas:

6

Gelatina , 54 53 bytes

J×$ÆrAƑƇ«⁹;⁹*€J{ḋ⁸ŻṀ
Œcz€0ḢṂç@I0;ⱮFƲƲ€ṚṁL’R€Ɗ;+Ṁ¥¥ƒ0Ṁ

Prué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 llas diferencias en los coeficientes de los polinomios que representan los cuencos desde 1 hacia arriba, y su argumento derecho rel radio mínimo; devuelve el valor y máximo donde se encuentran los dos tazones

  $                   | Following as a monad:
J                     | - Sequence from 1..<len(l)>
 ×                    | - Multiply (by l)
   Ær                 | Roots of polynomial
     AƑƇ              | Keep only those invariant when passed through absolute function (excludes negative, imaginary and complex numbers)
        «⁹            | Min of these filtered roots and r
          ;⁹          | Concatenate r to the list
            *€        | Each root/radius to the power of:
              J{      | - Sequence from 1..<len(l)>
                ḋ⁸    | Dot product with l
                  Ż   | Prepend zero
                   Ṁ  | Maximum

Enlace principal, toma un montón de bol como argumento y devuelve el valor y de la base del bol superior

Œc                               | Combinations length 2
  z€0                            | Transpose each using 0 as a filler
               Ʋ€                | For each one, do the following as a monad:
     Ḣ                           | - Take the head (the radii)     
      Ṃ                          | - Minimum
       ç@     Ʋ                  | - Call the helper link with this (min radius) as right argument and the following as left argument:
         I                       |   - Increments (difference between second and first polynomial for each coefficient)
          0;Ɱ                    |   - Prepend each with a zero (odd coefficients are all zero)
             F                   |   - Flatten
                 Ṛ               | Reverse
                  ṁ    Ɗ         | Mould to the following as a monad:
                   L             | Length
                    ’            | Decrease by 1
                     R€          | Range of each (e.g. [1],[1,2],[1,2,3],[1,2,3,4]
                            ¥ƒ0  | Reduce using the following as a dyad and starting with 0
                        ;  ¥     | - Concatenate the following as a dyad
                         +       |   - Add
                          Ṁ      |   - Take the maximum
                               Ṁ | Finally take the overall maximum

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.

Nick Kennedy
fuente
1
No entiendo el idioma en absoluto. Según la explicación, parece que solo compara cada par de tazones (r1, p1)y (r2, p2)en el punto min(r1, r2). Si es así, esa sería una solución incorrecta porque dos tazones pueden tocar entre 0y min(r1, r2)). Necesita encontrar max(p1(x)-p2(x), 0)en toda la gama [0, min(r1, r2)]para x. Es por eso que la solución de referencia de @ pasbi calcula derivados para encontrar el máximo local.
Joel
@Joel arreglado ahora. Todos los casos de prueba originales se tocaron en min(r1, r2). Esto ahora resuelve el desafío adicional de @ attinat
Nick Kennedy el
1
Sería bueno ver una versión comentada del código para aquellos que no tienen conocimiento del idioma del golf, si tiene tiempo.
Joel
@Joel lo hará cuando tenga tiempo
Nick Kennedy
2

Python 3 + numpy + scipy, 248 240 bytes

from scipy.optimize import*
from numpy import*
def f(b,i=0):
 for r,c in b:p=zeros(2*len(c)+1);p[-3::-2]=c;p[-1]=h=max([0,*(-fminbound(lambda x:polyval(polysub(p,d),x),0,min(s,r),full_output=1)[1]for s,d in b[:i])]);b[i][1]=p;i+=1
 return h

Prué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 numpyy scipyfunciones 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.

from scipy.optimize import fminbound
import numpy as np

def compute_pile_height(bowl_data):
    for i, (r, curve) in enumerate(bowl_data):
        distances = [0]  # Initialize the distances array with 0 as the lower bound for max
        # Construct a complete polynominal coefficient array
        curve_poly = np.zeros(2 * len(curve) + 1)
        curve_poly[-3::-2] = curve
        
        # Iterate over all bowls under the current bowl
        for j in range(i):
            b_r, b_curve_poly = bowl_data[j]

            # Calculate the difference polynominal between the current bowl and bowl j
            diff = np.polysub(curve_poly, b_curve_poly)

            # Find the maximum height difference between bowl j and the current bowl in the range [0, min(b_r, r)]
            max_height_diff = -fminbound(lambda x:np.polyval(diff, x), 0, min(b_r, r), full_output=True)[1]
            distances.append(max_height_diff)

        # Compute the maximum distance as the height for the current bowl, 
        # update the polynominal using the height as the constant coefficient
        curve_poly[-1] = height = max(distances)

        # Update stored data for the current bowl
        bowl_data[i][1] = curve_poly
    return height

Pruébalo en línea!

Joel
fuente
Para ahorrar en espacios en blanco, puede poner el ciclo for completo en su línea después de los dos puntos, y ponerlo i=0como argumento opcional.
xnor
@xnor Ah, gracias. No puse demasiado esfuerzo para jugar golf porque guardar un par de bytes en una solución de más de 200 bytes no lo cambiaría demasiado. Y parece que no hay un mejor algoritmo para este que pueda simplificar significativamente el cálculo.
Joel
Técnicamente, esto debería describirse en el encabezado como Python3 + numpy + sympy ya que ninguno de los dos es parte de la instalación base de Python3.
Nick Kennedy
@NickKennedy Gracias. Descripción actualizada.
Joel
1

Wolfram Language (Mathematica) , 104 93 bytes

FoldPair[{(R=#;F=#2)&@@#2;H=Max[0,{#2-F,0<x<#~Min~R}~MaxValue~x&@@@#],#~Join~{R|H+F}}&,{},#]&

Pruébalo en línea!

{radius, polynomial}x

Para la salida decimal en lugar de simbólica, use NMaxValueen su lugar (o simplemente invoque Nel resultado).

(* Step through a list of bowls: *)
(* At each step, calls a function taking {previous-bowls-list},current-bowl *)
(*  which returns {height,{bowls-list}} *)
(* and returns the final height *)
FoldPair[
  (R=#;F=#2)&@@#2;          (*  extract Radius and Function*)
  {
    H=Max[0,                (*  Height - at least zero; the greatest of *)
      MaxValue[{#2-F,       (*   the required heights *)
          0<x<#~Min~R},x]   (*     within the relevant domain *)
      &@@@#]                (*   given all previous bowls *)
  ,
    #~Join~{R|H+F}          (*   append to list of bowls *)
  }&,
  {},                       (* initial list of bowls (empty) *)
  #                         (* list of bowls *)
]&
attinat
fuente
1

R , 451 436 bytes

function(x){x=c(x[1],x);a=rev(pmax(0,c(combn(x,2,function(y,z=sapply(y,"length<-",max(lengths(y)))){z[is.na(z)]=0
b=rep(0,2*(n=nrow(z)-1))
b[2*1:n]=e=z[-1,2]-z[-1,1]
b=b*1:(2*n)
while(!c(b,1)[1])b=b[-1]
b=rev(b)
s=`if`(length(b)>1,eigen(rbind(-(b/b[1])[-1],cbind(diag(length(b)-2),0)))$va,0)
max(outer(c(pmin(abs(s[s==abs(s)]),r<-min(z[1,])),r),2*1:n,`^`)%*%e)}))))
o={}
for(i in seq(a=x[-1])){o=c(o,max(c(0,o)+a[1:i+F]));F=F+i}
max(o)}

Prué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!

Nick Kennedy
fuente
No entiendo todo lo que está sucediendo aquí (¡la explicación sería buena!), Pero aquí hay una versión de 436 bytes .
Robin Ryder