19
\$\begingroup\$

Bowl Pile Height

The goal of this puzzle is to compute the height of a stack of bowls.

A stack of bowls

A bowl is defined to be a radially symmetric device without thickness. Its silhouette shape is an even polynomial. The stack is described by a list of radii, each associated with an even polynomial, given as input as a list of coefficients (e.g. the list 3.1 4.2 represents the polynomial \$3.1x^2+4.2x^4\$).

The polynomial may have arbitrary degree. For simplicity, the height of the pile is defined as the altitude of the center of the top-most bowl (see plot of Example 3 for an illustration).

Test cases are in the format radius:coeff1 coeff2 ...: each line starts with a float number representing the radius of the bowl, followed by a colon and a space-separated list containing the coefficients for the even powers, starting with power 2 (zero constant part is implied). For example, the line 2.3:3.1 4.2 describes a bowl of radius 2.3 and the shape-polynomial 3.1 * x^2 + 4.2 * x^4.

Example 1

42:3.141

describes a pile of zero height since a single bowl has no height.

Example 2

1:1 2
1.2:5
1:3

describes a pile of height 2.0 (see plot).

Plot of a stack of three bowls

Example 3

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

describes a pile of height 0.8 (see green arrow in the plot).

Plot of a stack of three bowls

This is code golf, so the shortest code wins.

I have reference code.

Edit:

The reference implementation relies on a library to compute the roots of polynomials. You may do that as well but you don't need to. Since the reference implementation is only a (quite good) numerical approximation, I will accept any code which produces correct results within common floating-point tolerances.

The idea counts. I don't care if there are small erros \$<\varepsilon\$.

Another variant of this puzzle is to minimize the height by reordering the bowls. I'm not sure if there's a fast solution (I guess it's NP-hard). If anyone has a better idea (or can prove NP-completeness), please tell me!

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mego Aug 29 at 16:03
  • \$\begingroup\$ In your reference code, I believe the body of is_maximum should be e.g. return evaluate(differentiate(shape_0), root) > 0.0. Currently, it evaluates the root using dd (derivative of the difference between shapes), which should always return 0 (for roots). Due to floating point errors, the result is occasionally a positive value close to 0, which is why the code outputs a correct or more accurate result some of the time. Check the input 1:0.2, 1:0.1 0.2 which should output 0.0125 \$\endgroup\$ – redundancy Aug 29 at 20:51
  • \$\begingroup\$ @redundancy it’s actually redundant anyway. The max y value is chosen and 0 will always be in the compares values. \$\endgroup\$ – Nick Kennedy Aug 29 at 21:18
  • 2
    \$\begingroup\$ In example 3, the final height should be 0.801. The final two bowls touch at radius 0.1. \$\endgroup\$ – attinat Aug 29 at 23:19
  • \$\begingroup\$ Yes, I got the same result. \$\endgroup\$ – Joel Aug 29 at 23:39
6
\$\begingroup\$

Jelly, 54 53 bytes

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

Try it online!

A monadic link that takes as its argument the list of bowls from top to bottom in the format [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]] and returns the y position of the bottom of the top bowl.

Now correctly handles bowls which meet at places other than the minimal radius.

Explanation

Helper link: takes as left argument l the differences in coefficients of the polynomials representing the bowls from 1 upwards, and its right argument r the minimum radius; returns the maximum y value where the two bowls meet

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

Main link, takes a bowl pile as its argument and returns y value of base of top bowl

Œ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 reference

Finally, here’s a TIO version of the Python reference that @pasbi included for the main problem. It reads from stdin.

\$\endgroup\$
  • 1
    \$\begingroup\$ I do not understand the language at all. Based on the explanation, it looks like you only compare each bowl pair (r1, p1) and (r2, p2) at the point min(r1, r2)? If so, that would be a wrong solution because two bowls can touch between 0 and min(r1, r2)). You need to find max(p1(x)-p2(x), 0) over the entire range [0, min(r1, r2)] for x. That is why @pasbi's reference solution computes derivatives for finding the local maximum. \$\endgroup\$ – Joel Aug 28 at 23:49
  • \$\begingroup\$ @Joel fixed now. All of the original test cases touched at min(r1, r2). This now solves @attinat’s additional challenge \$\endgroup\$ – Nick Kennedy Aug 29 at 15:03
  • 1
    \$\begingroup\$ It would be nice to see a commented version of the code for those who have no knowledge of the golfing language, if you have time. \$\endgroup\$ – Joel Aug 29 at 21:26
  • \$\begingroup\$ @Joel will do when I get time \$\endgroup\$ – Nick Kennedy Aug 30 at 0:00
2
\$\begingroup\$

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

Try it online!

-8 bytes thanks to @xnor

The function takes a list of [radius, polynomial] pairs as input and returns the pile height.

This solution uses more or less the same algorithm as the reference code except that it does not compute the maximum using derivatives. Meanwhile, it is written using built-in numpy and scipy functions in Python. The ungolfed version is shown in the following. This serves as an alternative version of the reference code for those who wants a shorter version to capture the idea quickly.

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ To save on whitespace, you can put the whole for loop on its line after the colon, and put i=0 as an optional argument. \$\endgroup\$ – xnor Aug 30 at 2:06
  • \$\begingroup\$ @xnor Ah, thanks. I did not put too much effort to golf this because saving a couple of bytes in a 200+byte solution would not change it much. And it seems that there is no better algorithm for this one that can significantly simplify the computation. \$\endgroup\$ – Joel Aug 30 at 2:17
  • \$\begingroup\$ Technically this should be described in the header as Python3 + numpy + sympy since neither are part of the base Python3 install. \$\endgroup\$ – Nick Kennedy Aug 30 at 6:50
  • \$\begingroup\$ @NickKennedy Thanks. Description updated. \$\endgroup\$ – Joel Aug 30 at 9:59
1
\$\begingroup\$

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}}&,{},#]&

Try it online!

Takes input as a List of {radius, polynomial} pairs representing bowls, with polynomials in terms of \$x\$.

For decimal instead of symbolic output, use NMaxValue instead (or just call N on the result).

(* 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 *)
]&
\$\endgroup\$
1
\$\begingroup\$

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

Try it online!

Try it online!

Broadly speaking an R port of my Jelly answer, though since base R has no function to find the roots of polynomials this is implemented using the method found in polynom::solve.polynomial.

A function taking a list of numeric vectors from top to bottom of pile.

Thanks to @RobinRyder for golfing off 15 bytes!

\$\endgroup\$
  • \$\begingroup\$ I don't understand everything that is going on here (explanation would be nice!), but here is a 436 byte version. \$\endgroup\$ – Robin Ryder Aug 30 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.