Tinggi Tumpukan Mangkuk

Tujuan dari teka-teki ini adalah untuk menghitung ketinggian setumpuk mangkuk.

Mangkuk didefinisikan sebagai perangkat simetris radial tanpa ketebalan. Bentuk siluetnya bahkan polinomial. Tumpukan dijelaskan oleh daftar jari-jari, masing-masing terkait dengan polinomial genap, diberikan sebagai input sebagai daftar koefisien (mis. Daftar tersebut 3.1 4.2merepresentasikan polinomial $3.1x^2+4.2x^4$ ).

Polinomial mungkin memiliki tingkat arbitrer. Untuk kesederhanaan, ketinggian tumpukan didefinisikan sebagai ketinggian tengah mangkuk paling atas (lihat plot Contoh 3 untuk ilustrasi).

Kasus uji dalam format radius:coeff1 coeff2 ...: setiap baris dimulai dengan angka float yang mewakili jari-jari mangkuk, diikuti oleh titik dua dan daftar yang dipisahkan ruang yang berisi koefisien untuk kekuatan genap, dimulai dengan daya 2 (nol bagian konstan tersirat) . Misalnya, garis 2.3:3.1 4.2menggambarkan semangkuk jari-jari 2.3dan bentuk-polinomial3.1 * x^2 + 4.2 * x^4 .

Contoh 1

42:3.141

menggambarkan tumpukan tinggi nol karena mangkuk tunggal tidak memiliki ketinggian.

Contoh 2

1:1 2
1.2:5
1:3

menggambarkan tumpukan tinggi 2.0(lihat plot).

Contoh 3

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

menjelaskan tumpukan tinggi 0,8 (lihat panah hijau di plot).

Ini kode golf, jadi kode terpendek menang.

Saya punya kode referensi .

Edit:

Implementasi referensi bergantung pada perpustakaan untuk menghitung akar polinomial. Anda dapat melakukannya juga tetapi Anda tidak perlu melakukannya. Karena implementasi referensi hanya merupakan pendekatan numerik (cukup baik), saya akan menerima kode apa pun yang menghasilkan hasil yang benar dalam toleransi floating-point umum.

$<\varepsilon$ .

^{Varian lain dari teka-teki ini adalah meminimalkan ketinggian dengan menata ulang mangkuk. Saya tidak yakin apakah ada solusi cepat (saya kira ini NP-hard). Jika ada yang punya ide yang lebih baik (atau bisa membuktikan kelengkapan NP), tolong katakan padaku!}

Jelly , 54 53 byte

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

Cobalah online!

Tautan monadik yang mengambil argumennya daftar mangkuk dari atas ke bawah dalam format [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]] dan mengembalikan posisi y dari bagian bawah mangkuk atas.

Sekarang dengan benar menangani mangkuk yang bertemu di tempat-tempat selain radius minimal.

Penjelasan

Helper link: mengambil sebagai argumen kiri lperbedaan koefisien dari polinomial yang mewakili mangkuk dari 1 ke atas, dan argumen kanan rjari-jari minimum; mengembalikan nilai y maksimum tempat kedua mangkuk bertemu

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

Tautan utama, mengambil tumpukan mangkuk sebagai argumennya dan mengembalikan nilai dasar mangkuk atas

Œ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

Referensi Python

Akhirnya, inilah versi TIO dari referensi Python yang disertakan @pasbi untuk masalah utama. Bunyinya dari stdin.

Python 3 + numpy + scipy, 248 240 byte

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

Cobalah online!

-8 byte terima kasih kepada @xnor

Fungsi mengambil daftar [radius, polynomial]pasangan sebagai input dan mengembalikan ketinggian tiang.

Solusi ini menggunakan kurang lebih algoritma yang sama dengan kode referensi kecuali bahwa itu tidak menghitung maksimum menggunakan derivatif. Sementara itu, ditulis menggunakan built-in numpydan scipyfungsi dengan Python. Versi ungolfed ditampilkan sebagai berikut. Ini berfungsi sebagai versi alternatif dari kode referensi bagi mereka yang menginginkan versi yang lebih pendek untuk menangkap ide dengan cepat.

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 104 93 byte

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

Cobalah online!

{radius, polynomial}$x$

Untuk desimal alih-alih keluaran simbolis, gunakan NMaxValuesebagai gantinya (atau panggil saja Nhasilnya).

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

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

Cobalah online!

Cobalah online!

Secara garis besar port R dari jawaban Jelly saya, meskipun karena basis R tidak memiliki fungsi untuk menemukan akar polinomial ini diimplementasikan menggunakan metode yang ditemukan dalam polynom::solve.polynomial .

Fungsi mengambil daftar vektor numerik dari atas ke bawah tumpukan.

Terima kasih kepada @RobinRyder untuk bermain golf 15 byte!