Altura da pilha da tigela

O objetivo deste quebra-cabeça é calcular a altura de uma pilha de tigelas.

Uma tigela é definida como um dispositivo radialmente simétrico sem espessura. Seu formato de silhueta é um polinômio uniforme. A pilha é descrita por uma lista de raios, cada um associado a um polinômio par, dado como entrada como uma lista de coeficientes (por exemplo, a lista 3.1 4.2representa o polinômio $3.1x^2+4.2x^4$ ).

O polinômio pode ter grau arbitrário. Por uma questão de simplicidade, a altura da pilha é definida como a altitude do centro da tigela superior (consulte a ilustração do Exemplo 3 para uma ilustração).

Os casos de teste estão no formato radius:coeff1 coeff2 ...: cada linha começa com um número flutuante que representa o raio da tigela, seguido por dois pontos e uma lista separada por espaços contendo os coeficientes das potências pares, começando com a potência 2 (parte constante zero está implícita) . Por exemplo, a linha 2.3:3.1 4.2descreve uma tigela de raio 2.3e o polinômio de forma 3.1 * x^2 + 4.2 * x^4.

Exemplo 1

42:3.141

descreve uma pilha de altura zero, pois uma única tigela não tem altura.

Exemplo 2

1:1 2
1.2:5
1:3

descreve uma pilha de altura 2.0(ver gráfico).

Exemplo 3

1:1.0
0.6:0.2
0.6:0.4
1.4:0.2
0.4:0 10

descreve uma pilha de altura 0,8 (veja a seta verde no gráfico).

Isso é código de golfe, então o código mais curto vence.

Eu tenho código de referência .

Editar:

A implementação de referência depende de uma biblioteca para calcular as raízes dos polinômios. Você pode fazer isso também, mas não precisa. Como a implementação de referência é apenas uma aproximação numérica (muito boa), aceitarei qualquer código que produza resultados corretos dentro de tolerâncias comuns de ponto flutuante.

$<\varepsilon$

^{Outra variante desse quebra-cabeça é minimizar a altura reordenando as taças. Não tenho certeza se existe uma solução rápida (acho que é NP-difícil). Se alguém tiver uma ideia melhor (ou puder provar a completude do NP), diga-me!}

Geléia , 54 53 bytes

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

Experimente online!

Um link monádico que usa como argumento a lista de tigelas de cima para baixo no formato [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]e retorna a posição y da parte inferior da tigela superior.

Agora lida corretamente com tigelas que se encontram em locais diferentes do raio mínimo.

Explicação

Elo auxiliar: toma como argumento là esquerda as diferenças nos coeficientes dos polinômios que representam as tigelas de 1 para cima, e seu argumento rà direita no raio mínimo; retorna o valor máximo de y onde as duas tigelas se encontram

  $                   | 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

Link principal, pega uma pilha de tigela como argumento e retorna o valor y da base da tigela 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

Referência do Python

Finalmente, aqui está uma versão TIO da referência do Python que o @pasbi incluiu para o problema principal. Lê de stdin.

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

Experimente online!

-8 bytes graças a @xnor

A função pega uma lista de [radius, polynomial]pares como entrada e retorna a altura da pilha.

Esta solução usa mais ou menos o mesmo algoritmo que o código de referência, exceto que ele não calcula o máximo usando derivadas. Enquanto isso, ele é escrito usando funções internas numpye scipyem Python. A versão ungolfed é mostrada a seguir. Isso serve como uma versão alternativa do código de referência para quem deseja uma versão mais curta para capturar a ideia rapidamente.

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

Experimente online!

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}}&,{},#]&

Experimente online!

{radius, polynomial}$x$

Para saída decimal em vez de simbólica, use em NMaxValuevez (ou apenas chame No 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 *)
]&

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

Experimente online!

Experimente online!

Em termos gerais, uma porta R da minha resposta Jelly, embora como a base R não tenha função para encontrar as raízes dos polinômios, isso é implementado usando o método encontrado em polynom::solve.polynomial .

Uma função que obtém uma lista de vetores numéricos de cima para baixo da pilha.

Graças a @RobinRyder por jogar fora 15 bytes!