Вычислить высоту чаши

19

Высота ворса чаши

Цель этой головоломки - вычислить высоту стопки мисок.

Стопка мисок

Чаша определяется как радиально-симметричное устройство без толщины. Его форма силуэта является ровным полиномом. Стек описывается списком радиусов, каждый из которых связан с четным полиномом, заданным в качестве входных данных в виде списка коэффициентов (например, список 3.1 4.2представляет полином 3,1Икс2+4,2Икс4 ).

Полином может иметь произвольную степень. Для простоты высота кучи определяется как высота центра самой верхней чаши (см. Иллюстрацию в примере 3).

Контрольные примеры имеют формат radius:coeff1 coeff2 ...: каждая строка начинается с числа с плавающей точкой, представляющего радиус чаши, за которым следует двоеточие и разделенный пробелами список, содержащий коэффициенты для четных степеней, начиная с степени 2 (подразумевается нулевая константа) , Например, линия 2.3:3.1 4.2описывает чашу радиуса 2.3и форму-полином 3.1 * x^2 + 4.2 * x^4.

Пример 1

42:3.141

описывает кучу нулевой высоты, так как одна чаша не имеет высоты.

Пример 2

1:1 2
1.2:5
1:3

описывает кучу высоты 2.0(см. график).

Участок стека из трех чаш

Пример 3

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

описывает кучу высотой 0,8 (см. зеленую стрелку на графике).

Участок стека из трех чаш

Это код гольф, поэтому выигрывает самый короткий код.

У меня есть код ссылки .

Редактировать:

Эталонная реализация опирается на библиотеку для вычисления корней полиномов. Вы можете сделать это, но вам не нужно. Поскольку эталонная реализация является лишь (довольно хорошим) числовым приближением, я приму любой код, который дает правильные результаты в пределах общих допусков с плавающей точкой.

Идея имеет значение. Мне все равно, если есть небольшие ошибки .<ε

Другой вариант этой загадки - минимизировать высоту, изменяя порядок мисок. Я не уверен, есть ли быстрое решение (я думаю, это NP-сложный). Если у кого-то есть идея получше (или она может доказать NP-полноту), пожалуйста, скажите мне!

pasbi
источник
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Мего
В вашем коде ссылки, я считаю, что тело is_maximumдолжно быть, например return evaluate(differentiate(shape_0), root) > 0.0. В настоящее время он вычисляет корень, используя dd(производная от разницы между формами), который всегда должен возвращать 0 (для корней). В связи с плавающей точкой ошибки, то результат будет иногда положительное значение близко к 0, поэтому код выводит правильный или более точный результат некоторые из времени. Проверьте вход, 1:0.2, 1:0.1 0.2который должен выводить0.0125
избыточность
@ redundancy это на самом деле избыточно в любом случае. Максимальное значение y выбрано, и 0 всегда будет в сравниваемых значениях.
Ник Кеннеди
2
В примере 3 конечная высота должна быть 0.801. Последние две чаши соприкасаются в радиусе 0.1.
attinat
Да, я получил тот же результат.
Джоэл

Ответы:

6

Желе , 54 53 байта

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

Попробуйте онлайн!

Монадическая ссылка, которая принимает в качестве аргумента список чаш сверху вниз в формате [[b1_radius, b1_coef1, ...], [b2_radius, b2_coef1, ...]]и возвращает позицию y нижней части верхней чаши.

Теперь правильно обрабатывает чаши, которые встречаются в местах, отличных от минимального радиуса.

объяснение

Вспомогательная ссылка: принимает в качестве левого аргумента lразличия в коэффициентах полиномов, представляющих чаши от 1 вверх, а в качестве правого аргумента r- минимальный радиус; возвращает максимальное значение у, где встречаются две чаши

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

Основная ссылка, принимает в качестве аргумента кучу чаши и возвращает значение у основания верхней чаши

Œ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 ссылка

Наконец, вот TIO-версия ссылки на Python, которую @pasbi включил для основной проблемы. Это читает со стандартного ввода.

Ник Кеннеди
источник
1
Я вообще не понимаю язык. Исходя из объяснения, похоже, что вы сравниваете только каждую пару чаш (r1, p1)и (r2, p2)по существу min(r1, r2)? Если это так, это было бы неправильным решением, потому что две чаши могут касаться между 0и min(r1, r2)). Вам нужно найти max(p1(x)-p2(x), 0)во всем диапазоне [0, min(r1, r2)]для x. Вот почему эталонное решение @ pasbi вычисляет производные для нахождения локального максимума.
Джоэл
@ Джоэл сейчас исправлен. Все оригинальные тестовые случаи затронуты в min(r1, r2). Это теперь решает дополнительную проблему @ attinat
Ник Кеннеди
1
Было бы неплохо увидеть закомментированную версию кода для тех, кто не знает языка игры в гольф, если у вас есть время.
Джоэл
@Joel сделает, когда у меня будет время
Ник Кеннеди
2

Python 3 + Numpy + Scipy, 248 240 байт

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

Попробуйте онлайн!

-8 байт благодаря @xnor

Функция принимает список [radius, polynomial]пар в качестве входных данных и возвращает высоту стопки.

Это решение использует более или менее тот же алгоритм, что и ссылочный код, за исключением того, что оно не вычисляет максимум с использованием производных. Между тем, он написан с использованием встроенных numpyи scipyфункций в Python. Развернутая версия показана ниже. Это служит альтернативной версией ссылочного кода для тех, кто хочет, чтобы более короткая версия быстро уловила идею.

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

Попробуйте онлайн!

Joel
источник
Чтобы сэкономить на пустом месте, вы можете поместить весь цикл for в строку после двоеточия и указать i=0в качестве необязательного аргумента.
xnor
@xnor Ах, спасибо. Я не прилагал слишком много усилий для игры в гольф, потому что сохранение пары байтов в 200 + байтовом решении не сильно изменило бы это. И кажется, что нет лучшего алгоритма для этого, который мог бы значительно упростить вычисления.
Джоэл
Технически это должно быть описано в заголовке как Python3 + numpy + sympy, поскольку ни одна из них не является частью базовой установки Python3.
Ник Кеннеди
@NickKennedy Спасибо. Описание обновлено.
Джоэл
1

Wolfram Language (Mathematica) , 104 93 байта

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

Попробуйте онлайн!

{radius, polynomial}Икс

Вместо десятичного вместо символьного вывода используйте NMaxValueвместо него (или просто вызовите Nрезультат).

(* 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
источник
1

R , 451 436 байт

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

Попробуйте онлайн!

Попробуйте онлайн!

Говоря в общем, R-порт моего Jelly ответа, хотя, поскольку база R не имеет функции для поиска корней полиномов, это реализовано с использованием метода, описанного в polynom::solve.polynomial.

Функция, принимающая список числовых векторов сверху вниз.

Спасибо @RobinRyder за добавление в игру 15 байтов!

Ник Кеннеди
источник
Я не понимаю всего, что здесь происходит (объяснение было бы неплохо!), Но вот 436-байтовая версия .
Робин Райдер