12
\$\begingroup\$

You will need to evaluate the definite integral (bounded by \$a\$ and \$b\$) of a certain polynomial function that takes the form of:

$$\int_a^b \left( k_n x^n + k_{n-1} x^{n-1} + \cdots + k_2x^2 + k_1x + k_0 \: \right) dx$$

Normally, this can be done using the fundamental theorem of calculus and power rules. For example:

$$\int_b^c ax^n dx = a \frac{x^{n+1}} {n+1} \Big|^c_b = a\left[ \frac{c^{n+1}} {n+1} - \frac{b^{n+1}} {n+1} \right]$$

The challenge here is to replicate that process using the shortest amount of code as possible. You will decide the degree your program can solve. Somewhere in your answer, specify how many degrees your program can solve up to. For example:

My program can solve all polynomials up to the 5th degree. (quintic polynomial)

Input

Input will be two arrays consisting of bounds and coefficients. For example:

bounds = [2, 3]
coefficients = [4, 5, 2, 7]

The above input will yield this expression:

$$ \int_2^3 (4x^3 + 5x^2 + 2x + 7) \mathop{dx} $$

Output

The output will be a single decimal number rounded to at least 3 decimal places. So the above expression will yield:
108.666666666667 // correct
108.6667 // correct
109 // wrong

Constraints

$$ -10^9 < k_n, ..., k_1, k_0 < 10^9 $$ $$ 0 < N < 30 $$ Integral bounds \$a, b\$ satisfy no additional constraints.

Rules & Scoring

  • Standard loopholes apply here as it does anywhere else.

  • You may not write a program that only solves a specific integral. Once you pick your degree, that program must work under all constraints up to that degree.

  • Your score will be calculated by this equation: degree of polynomial / num of bytes, and the highest score wins.

  • If your program works for all degrees above 30, set your numerator to be 30, otherwise 29 is the maximum possible numerator.

  • Please post a working version of your code on any website so that it can be tested.

\$\endgroup\$
17
  • \$\begingroup\$ So the max degree we have to handle is 30? \$\endgroup\$ Feb 15 at 22:38
  • 4
    \$\begingroup\$ This is not your typical algorithm contests site, you shouldn't make the IO so strict. \$\endgroup\$
    – xigoi
    Feb 15 at 22:52
  • 3
    \$\begingroup\$ I would recommend, as you are a newer user, that you loosen the I/O formats (allow people to input as arrays for example), and that you post your next question to the Sandbox to get feedback first \$\endgroup\$ Feb 15 at 22:54
  • 2
    \$\begingroup\$ So the maximum numerator in the score equation is 29 or is it 30? \$\endgroup\$
    – Luis Mendo
    Feb 15 at 23:33
  • 2
    \$\begingroup\$ If my language of choice supports rational numbers, can I output the exact fraction, e.g. 108+2/3 or 326/3? \$\endgroup\$
    – Bubbler
    Feb 15 at 23:43

12 Answers 12

7
\$\begingroup\$

Jelly, \$\frac {30} 7 = 4.29\$

÷J$ŻUḅI

Try it online!

Takes the polynomial as a list of coefficients in little-endian format (i.e. the example is 7,2,5,4). This can handle any (positive) degree you want, but I've limited it at 30 as the question states \$0 < N < 30\$

+2 bytes and a score of \$3.33\$ if the polynomial must be taken in big-endian format

How it works

÷J$ŻUḅI - Main link. Takes coeffs on the left and [a, b] on the right
  $     - To the coeffs:
 J      -   Yield [1, 2, 3, ..., N]
÷       -   Divide each coeff by the orders
   Ż    - Prepend 0
    U   - Reverse
     ḅ  - Calculate as polynomials, with x = a and x = b
      I - Reduce by subtraction
\$\endgroup\$
5
\$\begingroup\$

J, \$\frac{30}{12}\approx2.5\$

[:-/[-p..p.[

Try it online!

-1 thanks to Bubbler

  • p.. Integral of a polynomial. Returns a list representing the solution polynomial.
  • p. Evaluate polynomial at given bounds.
  • [- Subtract from constant terms (makes both values negative).
  • -/ And subtract negative ending bound answer from negative starting bound answer.
\$\endgroup\$
1
3
\$\begingroup\$

Factor, \$\frac{30}{56}\approx0.5357\$

[ [ 1 + 3dup nip v^n first2 - swap / * ] map-index sum ]

Try it online!

Takes the bounds and coefficients in reverse, e.g. { 3 2 } { 7 2 5 4 }, and returns a rational number, e.g. 108+2/3.

To take the inputs as given and return a float, add a reverse, a neg, and a >float to get 75 bytes:

Factor, \$\frac{30}{75}=0.4\$

[ reverse [ 1 + 3dup nip v^n first2 - swap / * ] map-index sum neg >float ]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, \$ \frac {30} {20} = 1.5 \$

UMθ∕ι⁻Lθκ⊞θ⁰I⁻↨θζ↨θη

Try it online! Link is to verbose version of code. Explanation:

UMθ∕ι⁻Lθκ

Divide each element of the polynomial by the 1-indexed reverse index.

⊞θ⁰

Append a zero.

I⁻↨θζ↨θη

Calculate the value at each bound and take the difference.

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 30/32=0.9375 \$\frac{30}{31}\approx0.9677\$

c(a=0;c^++a.{-1,1}/a&/@#).#&

Try it online!

Accepts coefficients in ascending (lower to higher exponent) order. Input [{a, b}][coeff].


some 32-byters:

FromDigits[#,]~Integrate~{,##2}&

Try it online! Integrates using Null as the variable.

#2-#&@@Sum[i/++a#2^a,{i,a=0;#}]&

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Using Null as the variable makes me so happy :D \$\endgroup\$ Feb 16 at 9:03
2
\$\begingroup\$

APL (Dyalog Unicode), \$\frac{30}{20}=1.5\$

{-/⌽⊥∘(0,⍨⍵÷⌽⍳≢⍵)¨⍺}

Try it online!

Takes the bounds on the left and the coefficients on the right. This is a great place to use APL's ⊥, which can evaluate polynomials (although appending a zero is necessary because we want to use n+1 and not n).

\$\endgroup\$
2
\$\begingroup\$

05AB1E, \$\frac{30}{8} = 3.75\$

āR/0ªIβÆ

Port of @Neil's Charcoal answer, so make sure to upvote him as well!

First input is the list of coefficients; second is a pair of \$[b,a]\$ bounds.

Try it online.

Explanation:

ā         # Push a list in the range [1, (implicit) coefficients-length]
 R        # Reverse this range to [length,1]
  /       # Divide the coefficients by the ranged list (at the same postitions)
   0ª     # Append a 0 at the end of this list
     Iβ   # Convert this list to base-b and base-a using the second input-pair
       Æ  # And reduce that pair by subtracting
          # (after which the result is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

SageMath, \$\frac{30}{67}\approx 0.44776\$

lambda c,b:RR(integrate(sum(a*x**e for e,a in enumerate(c)),[x]+b))

Try it online!

Inputs the coefficients (from the constant to the highest degree) and bounds as lists.

Can surely work for much higher degrees of a polynomial but got tired waiting for it to finish \$10000\$.
Works quite quickly for degree of \$3000\$.

\$\endgroup\$
0
1
\$\begingroup\$

JavaScript, score: \$\frac{30}{71}\approx 0.42\$

n=>k=>(x=y=>k.reduce((a,b,c)=>a+b*y**(z=k.length-c)/z,0))(n[1])-x(n[0])

Demonstration:

f=n=>k=>(x=y=>k.reduce((a,b,c)=>a+b*y**(z=k.length-c)/z,0))(n[1])-x(n[0]);
// test case
console.log(f([2,3])([4,5,2,7]));
// large polynomial of degree 30
console.log(f([3,5])(new Array(31).fill(1) /*shortcut*/));

How it works

Constructs a function dynamically which calls reduce on the coefficients array. Then invokes it on both bounds and takes the difference.

\$\endgroup\$
1
  • \$\begingroup\$ y=>k.map(b=>a+=b*y**z/z--,a=0,z=k.length)&&a is shorter. \$\endgroup\$
    – Neil
    Feb 16 at 10:38
1
\$\begingroup\$

C (gcc) (-lm), score: \$\frac{30}{90}= 0.\bar3\$

Sums the bounds for each term in descending order. Due to quirks with -O0, I was able to write this function without the usual return or explicit value assignment at the end of the function.

double f(b,t,n,i,j)int*b,*t;{for(double s=i=0;j=n-i;)s+=t[i++]*(pow(b[1],j)-pow(*b,j))/j;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

R, 55 bytes, score: \$\frac{30}{55}=0.\overline{54}\$

function(b,k)diff(outer(b,a<-rev(seq(!k)),"^")%*%(k/a))

Try it online!

If we could take the coefficients in ascending order of degree, this would be 5 bytes shorter and get a score of \$0.6\$ instead, by removing the rev().

\$\endgroup\$
0
\$\begingroup\$

Scala, \$\frac{30}{88}\approx0.3409\$

p=>_.:\(.0)((x,r)=>p.reverse.zipWithIndex.map{case(k,n)=>k*math.pow(x,n+1)/(n+1)}.sum-r)

Try it in Scastie

The question's IO format actually works out quiet well here (although I could save 8 bytes by taking the coefficients in reverse to avoid .reverse).

\$\endgroup\$

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.