Wysokość stosu miski
Celem tej układanki jest obliczenie wysokości stosu misek.
Miska jest zdefiniowana jako promieniowo symetryczne urządzenie bez grubości. Jego sylwetka ma równomierny wielomian. Stos jest opisany przez listę promieni, z których każdy związany jest z parzystym wielomianem, podany jako dane wejściowe jako lista współczynników (np. Lista 3.1 4.2
reprezentuje wielomian ).
Wielomian może mieć dowolny stopień. Dla uproszczenia wysokość stosu definiuje się jako wysokość środka najwyżej położonej misy (ilustrację przedstawiono na wykresie w przykładzie 3).
Przypadki testowe mają format radius:coeff1 coeff2 ...
: każda linia zaczyna się od liczby zmiennoprzecinkowej reprezentującej promień misy, po której następuje dwukropek i lista oddzielona spacjami zawierająca współczynniki dla mocy parzystych, zaczynając od mocy 2 (implikowana jest zerowa część stała) . Na przykład linia 2.3:3.1 4.2
opisuje miskę o promieniu 2.3
i wielomian kształtu 3.1 * x^2 + 4.2 * x^4
.
Przykład 1
42:3.141
opisuje stos o zerowej wysokości, ponieważ pojedyncza miska nie ma wysokości.
Przykład 2
1:1 2
1.2:5
1:3
opisuje stos wysokości 2.0
(patrz działka).
Przykład 3
1:1.0
0.6:0.2
0.6:0.4
1.4:0.2
0.4:0 10
opisuje stos wysokości 0,8 (patrz zielona strzałka na wykresie).
To jest kod golfowy, więc wygrywa najkrótszy kod.
Mam kod referencyjny .
Edytować:
Implementacja referencyjna polega na bibliotece do obliczania pierwiastków wielomianów. Możesz to zrobić, ale nie musisz. Ponieważ implementacja referencyjna jest tylko (całkiem dobrym) przybliżeniem liczbowym, zaakceptuję każdy kod, który daje prawidłowe wyniki w ramach wspólnych tolerancji zmiennoprzecinkowych.
Innym wariantem tej układanki jest zminimalizowanie wysokości poprzez zmianę kolejności misek. Nie jestem pewien, czy istnieje szybkie rozwiązanie (myślę, że jest to trudne NP). Jeśli ktoś ma lepszy pomysł (lub może udowodnić kompletność NP), proszę mi powiedzieć!
źródło
is_maximum
powinno być npreturn evaluate(differentiate(shape_0), root) > 0.0
. Obecnie ocenia pierwiastek za pomocądd
(pochodna różnicy między kształtami), która zawsze powinna zwracać 0 (dla pierwiastków). Ze względu na unoszące się błędy punkt, wynik jest czasami dodatnia wartość blisko 0, dlatego kod generuje poprawny lub bardziej dokładny wynik jakiś czas. Sprawdź dane wejściowe,1:0.2, 1:0.1 0.2
które powinny zostać wyświetlone0.0125
0.801
. Dwie ostatnie miski dotykają się w promieniu0.1
.Odpowiedzi:
Galaretka ,
5453 bajtówWypróbuj online!
Monadyczny link, który przyjmuje jako argument listę misek od góry do dołu w formacie
[[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]
i zwraca pozycję y dna górnej miski.Teraz poprawnie obsługuje miski, które spotykają się w miejscach innych niż minimalny promień.
Wyjaśnienie
Łącznik pomocniczy: przyjmuje jako lewy argument
l
różnice we współczynnikach wielomianów reprezentujących miski od 1 w górę, a jego prawy argumentr
minimalny promień; zwraca maksymalną wartość y na styku dwóch misekGłówny link, bierze stos miski jako argument i zwraca wartość y podstawy górnej miski
Odwołanie do Pythona
Na koniec, oto wersja TIO referencji Pythona, którą @pasbi zawarło dla głównego problemu. Czyta ze standardowego.
źródło
(r1, p1)
i(r2, p2)
na tym etapiemin(r1, r2)
? Jeśli tak, byłoby to niewłaściwe rozwiązanie, ponieważ dwie miski mogą dotykać między0
amin(r1, r2))
. Musisz znaleźćmax(p1(x)-p2(x), 0)
w całym zakresie[0, min(r1, r2)]
dlax
. Dlatego rozwiązanie referencyjne @ pasbi oblicza pochodne w celu znalezienia lokalnego maksimum.min(r1, r2)
. To rozwiązuje teraz dodatkowe wyzwanie @ attinatPython 3 + numpy + scipy,
248240 bajtówWypróbuj online!
-8 bajtów dzięki @xnor
Funkcja pobiera listę
[radius, polynomial]
par jako dane wejściowe i zwraca wysokość stosu.To rozwiązanie wykorzystuje mniej więcej ten sam algorytm co kod odniesienia, z tym wyjątkiem, że nie oblicza maksimum przy użyciu pochodnych. Tymczasem jest napisany przy użyciu wbudowanego
numpy
iscipy
funkcji w Pythonie. Wersja bez golfa jest pokazana poniżej. Służy to jako alternatywna wersja kodu referencyjnego dla tych, którzy chcą, aby krótsza wersja szybko uchwyciła pomysł.Wypróbuj online!
źródło
i=0
jako opcjonalny argument.Wolfram Language (Mathematica) ,
10493 bajtyWypróbuj online!
{radius, polynomial}
W przypadku liczb dziesiętnych zamiast symbolicznych użyj
NMaxValue
zamiast tego (lub po prostu wywołajN
wynik).źródło
R ,
451436 bajtówWypróbuj online!
Wypróbuj online!
Ogólnie mówiąc, port R mojej odpowiedzi Jelly, jednak ponieważ podstawa R nie ma funkcji znajdowania pierwiastków wielomianów, jest to realizowane za pomocą metody znalezionej w
polynom::solve.polynomial
.Funkcja przyjmująca listę wektorów numerycznych od góry do dołu stosu.
Dzięki @RobinRyder za grę w golfa z 15 bajtów!
źródło