Hauteur de la pile du bol

Le but de ce puzzle est de calculer la hauteur d'une pile de bols.

Un bol est défini comme étant un dispositif radialement symétrique sans épaisseur. Sa forme silhouette est un polynôme uniforme. L'empilement est décrit par une liste de rayons, chacun associé à un polynôme pair, donné en entrée sous forme de liste de coefficients (par exemple, la liste 3.1 4.2représente le polynôme $3.1x^2+4.2x^4$ ).

Le polynôme peut avoir un degré arbitraire. Par souci de simplicité, la hauteur du tas est définie comme l'altitude du centre du bol le plus haut (voir le graphique de l'exemple 3 pour une illustration).

Les cas de test sont au format radius:coeff1 coeff2 ...: chaque ligne commence par un nombre flottant représentant le rayon du bol, suivi par deux points et une liste séparée par des espaces contenant les coefficients pour les puissances paires, en commençant par la puissance 2 (zéro partie constante est impliquée) . Par exemple, la ligne 2.3:3.1 4.2décrit un bol de rayon 2.3et le polynôme de forme 3.1 * x^2 + 4.2 * x^4.

Exemple 1

42:3.141

décrit un tas de hauteur nulle puisqu'un seul bol n'a pas de hauteur.

Exemple 2

1:1 2
1.2:5
1:3

décrit un tas de hauteur 2.0(voir graphique).

Exemple 3

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

décrit un tas de hauteur 0,8 (voir flèche verte dans l'intrigue).

C'est le golf de code, donc le code le plus court gagne.

J'ai un code de référence .

Éditer:

L'implémentation de référence s'appuie sur une bibliothèque pour calculer les racines des polynômes. Vous pouvez également le faire, mais vous n'en avez pas besoin. Étant donné que l'implémentation de référence n'est qu'une (assez bonne) approximation numérique, j'accepterai tout code qui produit des résultats corrects dans les tolérances à virgule flottante courantes.

$<\varepsilon$

^{Une autre variante de ce puzzle est de minimiser la hauteur en réorganisant les bols. Je ne sais pas s'il y a une solution rapide (je suppose que c'est NP-difficile). Si quelqu'un a une meilleure idée (ou peut prouver l'exhaustivité de NP), dites-le moi!}

Gelée , 54 53 octets

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

Essayez-le en ligne!

Un lien monadique qui prend comme argument la liste des bols de haut en bas au format [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]et renvoie la position y du bas du bol supérieur.

Gère maintenant correctement les bols qui se rencontrent à des endroits autres que le rayon minimal.

Explication

Lien d'aide: prend comme argument de gauche lles différences de coefficients des polynômes représentant les bols de 1 vers le haut, et son argument de droite rle rayon minimum; renvoie la valeur y maximale où les deux bols se rencontrent

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

Lien principal, prend une pile de bol comme argument et renvoie la valeur y de la base du bol supérieur

Œ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

Référence Python

Enfin, voici une version TIO de la référence Python incluse @pasbi pour le problème principal. Il lit à partir de stdin.

Python 3 + numpy + scipy, 248 240 octets

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

Essayez-le en ligne!

-8 octets grâce à @xnor

La fonction prend une liste de [radius, polynomial]paires en entrée et renvoie la hauteur de la pile.

Cette solution utilise plus ou moins le même algorithme que le code de référence sauf qu'elle ne calcule pas le maximum à l'aide de dérivées. Pendant ce temps, il est écrit en utilisant les fonctions intégrées numpyet scipyen Python. La version non golfée est illustrée ci-dessous. Cela sert de version alternative du code de référence pour ceux qui veulent une version plus courte pour capturer rapidement l'idée.

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

Essayez-le en ligne!

Langue Wolfram (Mathematica) , 104 93 octets

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

Essayez-le en ligne!

Prend l'entrée sous forme de liste de {radius, polynomial}paires représentant des bols, avec des polynômes en termes de$x$.

Pour une sortie décimale au lieu d'une sortie symbolique, utilisez NMaxValueplutôt (ou appelez simplement Nle résultat).

(* 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 octets

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

Essayez-le en ligne!

Essayez-le en ligne!

D'une manière générale, un port R de ma réponse Jelly, bien que puisque la base R n'a pas de fonction pour trouver les racines des polynômes, cela est implémenté en utilisant la méthode trouvée dans polynom::solve.polynomial .

Une fonction prenant une liste de vecteurs numériques de haut en bas de pile.

Merci à @RobinRyder d'avoir joué au golf sur 15 octets!