Berechnen Sie die Höhe des Schalenstapels

19

Stapelhöhe der Schüssel

Das Ziel dieses Puzzles ist es, die Höhe eines Schalenstapels zu berechnen.

Ein Stapel Schüsseln

Eine Schüssel ist definiert als eine radialsymmetrische Vorrichtung ohne Dicke. Seine Silhouetteform ist ein gleichmäßiges Polynom. Der Stapel wird durch eine Liste von Radien beschrieben, die jeweils einem geraden Polynom zugeordnet sind und als eine Liste von Koeffizienten eingegeben werden (z. B. 3.1 4.2repräsentiert die Liste das Polynom ).3.1x2+4.2x4

Das Polynom kann einen beliebigen Grad haben. Der Einfachheit halber ist die Höhe des Stapels als die Höhe des Mittelpunkts der obersten Schüssel definiert (siehe Diagramm von Beispiel 3 für eine Illustration).

Testfälle haben das Format radius:coeff1 coeff2 ...: Jede Zeile beginnt mit einer Gleitkommazahl, die den Radius der Schüssel darstellt, gefolgt von einem Doppelpunkt und einer durch Leerzeichen getrennten Liste mit den Koeffizienten für die geraden Potenzen, beginnend mit Potenz 2 (der konstante Nullteil ist impliziert). . Beispielsweise 2.3:3.1 4.2beschreibt die Linie eine Schale mit Radius 2.3und das Formpolynom 3.1 * x^2 + 4.2 * x^4.

Beispiel 1

42:3.141

beschreibt einen Stapel mit einer Höhe von Null, da eine einzelne Schüssel keine Höhe hat.

Beispiel 2

1:1 2
1.2:5
1:3

beschreibt einen Haufen Höhe 2.0(siehe Grafik).

Handlung eines Stapels von drei Schüsseln

Beispiel 3

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

beschreibt einen Stapel mit einer Höhe von 0,8 (siehe grüner Pfeil in der Zeichnung).

Handlung eines Stapels von drei Schüsseln

Dies ist Codegolf, also gewinnt der kürzeste Code.

Ich habe einen Referenzcode .

Bearbeiten:

Die Referenzimplementierung stützt sich auf eine Bibliothek, um die Wurzeln von Polynomen zu berechnen. Sie können das auch tun, müssen es aber nicht. Da es sich bei der Referenzimplementierung nur um eine (recht gute) numerische Näherung handelt, akzeptiere ich jeden Code, der innerhalb der üblichen Gleitkommatoleranzen korrekte Ergebnisse liefert.

Die Idee zählt. Ich interessiere mich nicht , wenn es kleine erros .<ε

Eine andere Variante dieses Puzzles besteht darin, die Höhe zu minimieren, indem die Schalen neu angeordnet werden. Ich bin mir nicht sicher, ob es eine schnelle Lösung gibt (ich denke, es ist NP-schwer). Wenn jemand eine bessere Idee hat (oder die NP-Vollständigkeit nachweisen kann), sag es mir bitte!

pasbi
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Mego
In Ihrem Referenzcode glaube ich, dass der Körper von is_maximumzB sein sollte return evaluate(differentiate(shape_0), root) > 0.0. Derzeit wird die Wurzel mit dd(Ableitung des Unterschieds zwischen Formen) ausgewertet , wobei immer 0 (für Wurzeln) zurückgegeben werden sollte. Aufgrund Punktfehler schwimmen, ist das Ergebnis ein positiver Wert gelegentlich Schließen auf 0, weshalb gibt den Code ein korrektes oder genaueres Ergebnis einige der Zeit. Überprüfen Sie den Eingang, 1:0.2, 1:0.1 0.2der ausgegeben werden soll0.0125
Redundanz
@redundancy ist eigentlich sowieso überflüssig. Der maximale y-Wert ist ausgewählt und 0 ist immer in den Vergleichswerten enthalten.
Nick Kennedy
2
In Beispiel 3 sollte die endgültige Höhe sein 0.801. Die letzten beiden Schalen berühren sich im Radius 0.1.
29.
Ja, ich habe das gleiche Ergebnis erzielt.
Joel

Antworten:

6

Jelly , 54 53 Bytes

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

Probieren Sie es online!

Ein monadischer Link, der die Liste der Schalen im Format von oben nach unten als Argument verwendet [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]und die y-Position des Bodens der oberen Schale zurückgibt.

Behandelt jetzt Schalen richtig, die sich an anderen Stellen als dem minimalen Radius treffen.

Erläuterung

Hilfslink: Nimmt als linkes Argument ldie Koeffizientendifferenzen der Polynome, die die Schalen von 1 aufwärts darstellen, und als rechtes Argument rden minimalen Radius; Gibt den maximalen y-Wert zurück, bei dem sich die beiden Schalen treffen

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

Hauptlink, nimmt einen Schüsselstapel als Argument und gibt den y-Wert der Basis der oberen Schüssel zurück

Œ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

Python-Referenz

Schließlich ist hier eine TIO-Version der Python-Referenz, die @pasbi für das Hauptproblem enthält. Es liest von stdin.

Nick Kennedy
quelle
1
Ich verstehe die Sprache überhaupt nicht. Anhand der Erklärung sieht es so aus, als würdest du nur jedes Schüsselpaar vergleichen (r1, p1)und (r2, p2)auf den Punkt min(r1, r2)? Wenn ja, wäre das eine falsche Lösung, da sich zwei Schalen zwischen 0und berühren können min(r1, r2)). Sie müssen sich finden max(p1(x)-p2(x), 0)das gesamte Spektrum über [0, min(r1, r2)]für x. Aus diesem Grund berechnet die @ pasbi-Referenzlösung Derivate zur Ermittlung des lokalen Maximums.
Joel
@ Joel jetzt behoben. Alle ursprünglichen Testfälle betrafen min(r1, r2). Dies löst nun die zusätzliche Herausforderung von @ attinat
Nick Kennedy,
1
Es wäre schön, eine kommentierte Version des Codes für diejenigen zu sehen, die keine Kenntnisse der Golfsprache haben, wenn Sie Zeit haben.
Joel
@ Joel wird tun, wenn ich Zeit habe
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

Probieren Sie es online!

-8 Bytes dank @xnor

Die Funktion nimmt eine Liste von [radius, polynomial]Paaren als Eingabe und gibt die Stapelhöhe zurück.

Diese Lösung verwendet mehr oder weniger den gleichen Algorithmus wie der Referenzcode, außer dass mit Ableitungen nicht das Maximum berechnet wird. Inzwischen ist es geschrieben Built-in mit numpyund scipyin Python Funktionen. Die ungolfed Version wird im Folgenden gezeigt. Dies dient als alternative Version des Referenzcodes für diejenigen, die eine kürzere Version wünschen, um die Idee schnell zu erfassen.

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

Probieren Sie es online!

Joel
quelle
Um Leerzeichen zu speichern, können Sie die gesamte for-Schleife in die Zeile nach dem Doppelpunkt einfügen und i=0als optionales Argument angeben.
30.
@xnor Ah, danke. Ich habe nicht zu viel Mühe darauf verwendet, Golf zu spielen, da das Speichern von ein paar Bytes in einer Lösung mit mehr als 200 Bytes nicht viel ändern würde. Und es scheint, dass es für diesen Algorithmus keinen besseren gibt, der die Berechnung erheblich vereinfachen könnte.
Joel
Technisch sollte dies im Header als Python3 + numpy + sympy beschrieben werden, da weder Python3 noch Python3 Bestandteil der Basisinstallation sind.
Nick Kennedy
@ NickKennedy Danke. Beschreibung aktualisiert.
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}}&,{},#]&

Probieren Sie es online!

{radius, polynomial}x

Verwenden Sie statt der symbolischen Ausgabe die NMaxValueOption " Dezimal" (oder rufen Sie einfach Ndas Ergebnis auf).

(* 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
quelle
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)}

Probieren Sie es online!

Probieren Sie es online!

Allgemein gesagt, ein R-Port meiner Jelly-Antwort, obwohl die Basis R keine Funktion hat, um die Wurzeln von Polynomen zu finden, wird dies unter Verwendung der in gefundenen Methode implementiert polynom::solve.polynomial.

Eine Funktion, die eine Liste numerischer Vektoren von oben nach unten aufnimmt.

Vielen Dank an @RobinRyder für das Golfen mit 15 Bytes!

Nick Kennedy
quelle
Ich verstehe nicht alles, was hier vor sich geht (Erklärung wäre nett!), Aber hier ist eine 436-Byte-Version .
Robin Ryder