Oblicz wysokość stosu misy

19

Wysokość stosu miski

Celem tej układanki jest obliczenie wysokości stosu misek.

Stos 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.2reprezentuje wielomian 3.1x2)+4.2x4 ).

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.2opisuje miskę o promieniu 2.3i 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).

Wykres stosu trzech misek

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

Wykres stosu trzech misek

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ć!

pasbi
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Mego
W twoim kodzie referencyjnym uważam, że ciało is_maximumpowinno być np return 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.2które powinny zostać wyświetlone0.0125
redundancja
@redundancy i tak jest zbędne. Wybrano maksymalną wartość y, a 0 zawsze będzie w wartościach porównawczych.
Nick Kennedy
2
W przykładzie 3 ostateczna wysokość powinna wynosić 0.801. Dwie ostatnie miski dotykają się w promieniu 0.1.
attinat
Tak, mam ten sam wynik.
Joel

Odpowiedzi:

6

Galaretka , 54 53 bajtów

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

Wypró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 lróżnice we współczynnikach wielomianów reprezentujących miski od 1 w górę, a jego prawy argument rminimalny promień; zwraca maksymalną wartość y na styku dwóch misek

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

Główny link, bierze stos miski jako argument i zwraca wartość y podstawy górnej miski

Œ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

Odwołanie do Pythona

Na koniec, oto wersja TIO referencji Pythona, którą @pasbi zawarło dla głównego problemu. Czyta ze standardowego.

Nick Kennedy
źródło
1
W ogóle nie rozumiem tego języka. Na podstawie wyjaśnienia wygląda na to, że porównujesz tylko każdą parę misek (r1, p1)i (r2, p2)na tym etapie min(r1, r2)? Jeśli tak, byłoby to niewłaściwe rozwiązanie, ponieważ dwie miski mogą dotykać między 0a min(r1, r2)). Musisz znaleźć max(p1(x)-p2(x), 0)w całym zakresie [0, min(r1, r2)]dla x. Dlatego rozwiązanie referencyjne @ pasbi oblicza pochodne w celu znalezienia lokalnego maksimum.
Joel
@Joel naprawiony teraz. Dotknięte zostały wszystkie oryginalne przypadki testowe min(r1, r2). To rozwiązuje teraz dodatkowe wyzwanie @ attinat
Nick Kennedy
1
Byłoby miło zobaczyć skomentowaną wersję kodu dla tych, którzy nie znają języka golfa, jeśli masz czas.
Joel
@Joel zrobi, kiedy będę miał czas
Nick Kennedy
2

Python 3 + numpy + scipy, 248 240 bajtów

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

Wypró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 numpyi scipyfunkcji 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ł.

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

Wypróbuj online!

Joel
źródło
Aby zaoszczędzić na spacji, możesz umieścić całą pętlę for na jej linii po dwukropku i umieścić i=0jako opcjonalny argument.
xnor
@xnor Ah, dzięki. Nie włożyłem zbyt wiele wysiłku w golfa, ponieważ zaoszczędzenie kilku bajtów w 200-bajtowym rozwiązaniu niewiele by to zmieniło. I wydaje się, że nie ma lepszego algorytmu dla tego, który mógłby znacznie uprościć obliczenia.
Joel
Technicznie należy to opisać w nagłówku jako Python3 + numpy + sympy, ponieważ żadne z nich nie jest częścią podstawowej instalacji Python3.
Nick Kennedy
@NickKennedy Thanks. Opis zaktualizowany.
Joel
1

Wolfram Language (Mathematica) , 104 93 bajty

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

Wypróbuj online!

{radius, polynomial}x

W przypadku liczb dziesiętnych zamiast symbolicznych użyj NMaxValuezamiast tego (lub po prostu wywołaj Nwynik).

(* 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
źródło
1

R , 451 436 bajtów

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

Wypró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!

Nick Kennedy
źródło
Nie rozumiem wszystkiego, co się tutaj dzieje (wyjaśnienie byłoby fajne!), Ale tutaj jest wersja 436 bajtów .
Robin Ryder