Stapelhöhe der Schüssel
Das Ziel dieses Puzzles ist es, die Höhe eines Schalenstapels zu berechnen.
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.2
repräsentiert die Liste das Polynom ).
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.2
beschreibt die Linie eine Schale mit Radius 2.3
und 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).
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).
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!
quelle
is_maximum
zB sein solltereturn evaluate(differentiate(shape_0), root) > 0.0
. Derzeit wird die Wurzel mitdd
(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.2
der ausgegeben werden soll0.0125
0.801
. Die letzten beiden Schalen berühren sich im Radius0.1
.Antworten:
Jelly ,
5453 BytesProbieren 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
l
die Koeffizientendifferenzen der Polynome, die die Schalen von 1 aufwärts darstellen, und als rechtes Argumentr
den minimalen Radius; Gibt den maximalen y-Wert zurück, bei dem sich die beiden Schalen treffenHauptlink, nimmt einen Schüsselstapel als Argument und gibt den y-Wert der Basis der oberen Schüssel zurück
Python-Referenz
Schließlich ist hier eine TIO-Version der Python-Referenz, die @pasbi für das Hauptproblem enthält. Es liest von stdin.
quelle
(r1, p1)
und(r2, p2)
auf den Punktmin(r1, r2)
? Wenn ja, wäre das eine falsche Lösung, da sich zwei Schalen zwischen0
und berühren könnenmin(r1, r2))
. Sie müssen sich findenmax(p1(x)-p2(x), 0)
das gesamte Spektrum über[0, min(r1, r2)]
fürx
. Aus diesem Grund berechnet die @ pasbi-Referenzlösung Derivate zur Ermittlung des lokalen Maximums.min(r1, r2)
. Dies löst nun die zusätzliche Herausforderung von @ attinatPython 3 + numpy + scipy,
248240 BytesProbieren 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
numpy
undscipy
in 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.Probieren Sie es online!
quelle
i=0
als optionales Argument angeben.Wolfram Language (Mathematica) ,
10493 BytesProbieren Sie es online!
{radius, polynomial}
Verwenden Sie statt der symbolischen Ausgabe die
NMaxValue
Option " Dezimal" (oder rufen Sie einfachN
das Ergebnis auf).quelle
R ,
451436 BytesProbieren 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!
quelle