8
\$\begingroup\$

Given a list of coordinate pairs, output the Trapezoidal Riemann Sum of the values given between the first and last x-coordinates.

You will be given a sorted list of coordinate pairs, like this:

[
  [1,2],
  [3,5],
  [5,11]
]

Note that x-coordinates will always be in increasing order, ys may not.

My way to do this is (you might find a different way):

Get pairs of coordinates:

[1,2],[3,5] and [3,5],[5,11]

For each pair (let's start with the first):

  • Take the average of the y-values: (2 + 5) / 2 = 7/2

  • Take the difference of the x-values: 3 - 1 = 2

  • Multiply the two together to get the area of that section, which is 7/2 * 2 = 7.

Do this for all pairs. Let's quickly go through the next, [3,5],[5,11].

Average of y values = (5 + 11) / 2 = 8 Difference of x values = (5 - 3) = 2 Product of the two = 2 * 8 = 16

Now take the sum of all the values, resulting in 16+7 = 23.

Scoring

This is , shortest wins!

Testcases

[ [1,2], [3,5], [5,11] ] => 23
[ [3,4], [4,1], [7,5] ] => 11.5
[ [0,0], [9,9] ] => 40.5
[ [1,1], [2,3], [3,1], [4,3] ] => 6

Note that input will always contain non-negative integers. Tell me if any of the testcases are wrong as I worked them out by hand.

You may take a flat list, or the list with x and y swapped.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ Are you sure the second case is 10.5? 1*2.5 + 3*3 seems to equal 11.5 \$\endgroup\$ – hyper-neutrino Jun 16 at 6:40
  • 1
    \$\begingroup\$ @hyper-neutrino That's why I said to check :p \$\endgroup\$ – A username Jun 16 at 6:44
  • \$\begingroup\$ I assume pairs can be given as [y, x]? \$\endgroup\$ – Unrelated String Jun 16 at 6:48
  • \$\begingroup\$ @dingledooper I assume that positive refers to nonnegative in this context. \$\endgroup\$ – Recursive Co. Jun 16 at 7:11
  • \$\begingroup\$ @dingledooper Sorry for the confusion, I meant non-negative, as you can see from #3. \$\endgroup\$ – A username Jun 16 at 9:30

20 Answers 20

5
\$\begingroup\$

Ruby, 54 49 47 bytes

->l{(r,=l).sum{|a|x,y,z,w=r+r=a;(y+w)/2r*z-=x}}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Husk, 11 bytes

ṁΠTzẊe-o½+T

Try it online!

A rare question where you get to use a list of functions!

Explanation

ṁΠTzẊe-o½+T
          T transpose
   z        zipwith
     e      list of 2 functions:
      -      difference
       o½+   average
    Ẋ       using pairwise reduce
  T         transpose back
ṁ           map to and sum:
 Π           product
\$\endgroup\$
3
\$\begingroup\$

Python 3, 56 bytes

lambda p:sum((b+d)*(c-a)/2for(a,b),(c,d)in zip(p,p[1:]))

Try it online!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You can use (c-a) instead of abs(a-c) because "x-coordinates will always be in increasing order" \$\endgroup\$ – G B Jun 16 at 6:54
  • \$\begingroup\$ @G B Missed that part, thanks! \$\endgroup\$ – dingledooper Jun 16 at 6:58
3
\$\begingroup\$

JavaScript (Node.js), 61 bytes

n=>n.reduce((z,[a,b],i)=>z+=i--&&(b+n[i][1])*(a-n[i][0])/2,0)

Try it online!

Doing it with map is just as long:


JavaScript (Node.js), 61 bytes

n=>n.map(([a,b],i)=>z+=i--&&(b+n[i][1])*(a-n[i][0])/2,z=0)&&z

Try it online!


Thanks EliteDaMyth for saving 1 byte off both answers (was a general tip)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ according to testing, i--&&(...)*(...)/2 is 1 byte shorter than i--?(...)*(...)/2:0 \$\endgroup\$ – EliteDaMyth Jun 16 at 7:03
3
\$\begingroup\$

Jelly, 9 bytes

ạ+ƭ"P¥ƝSH

Try it online!

ạ+ƭ"P¥ƝSH  Main Link
     ¥Ɲ    For each (overlapping) pair
   "       Vectorize; apply to x coordinates then the y coordinates
  ƭ        Tie:
ạ          - for the x coordinates, absolute difference
 +         - for the y coordinates, sum
    P      Product
       S   Sum
        H  Halve
\$\endgroup\$
3
3
\$\begingroup\$

R, 60 52 bytes

function(l)diff(l[1,])%*%(c(l[,-1])+l)[2,-ncol(l)]/2

Try it online!

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

R, 55 45 bytes

function(x,y)diff(x)%*%(y[-sum(x|1)]+y[-1])/2

Try it online!

-6 bytes thanks to @Dominic


For input as matrix:

R, 50 bytes

function(a)diff(a[1,])%*%(a[2,-ncol(a)]+a[2,-1])/2

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ If it's Ok to accept a list of xs & a list of ys, I think you can get even shorter... \$\endgroup\$ – Dominic van Essen Jun 16 at 11:07
  • \$\begingroup\$ Ah, yes, thanks. That lead to further golfing it down. \$\endgroup\$ – pajonk Jun 16 at 11:42
2
\$\begingroup\$

Jelly, 9 bytes

×Ø-+PʋƝSH

Try it online!

Assumes the second test case is in fact meant to be 11.5. Although I did admit to trying this while it was still in the Sandbox like ten minutes ago, this contains absolutely none of the code I tried while it was there :P

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

Python 3, 62 bytes

lambda l:sum((y[0]-x[0])*(x[1]+y[1])/2for x,y in zip(l,l[1:]))

Try it online!

-2 bytes thanks to @NahuelFouilleul

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can unpack each value of the sublists as well, although that would make your answer identical to dingledooper's. \$\endgroup\$ – Recursive Co. Jun 16 at 7:09
2
\$\begingroup\$

JavaScript (ES6), 52 bytes

Given \$n\$ coordinate pairs, this computes \$\sum_{i=0}^{n-2}(y_i+y_{i+1})/2\times(x_{i+1}-x_i)\$ recursively.

f=([[x,y],...a])=>a+a?([[X,Y]]=a,y+Y)/2*(X-x)+f(a):0

Try it online!

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

Two more 9-byte answers:

Jelly, 9 bytes

Ḣ€IḋSƝF$H

Try it online!

and Jelly, 9 bytes

ZIḋSƝ}ɗ/H

Try it online!

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

05AB1E, 9 bytes

I don't think there are as many 9-byters as in Jelly, but here is one:

ø`ü+;s¥*O

Try it online!

          # implicit input                                      [[1,2],[3,5],[5,11]]
ø`        # tranpose and push x and y seperately to the stack   [1,3,5], [2,5,11]
  ü+      # for y coordinates: sum adjacent numbers             [1,3,5], [7,16]
    ;     # halve each value to get means                       [1,3,5], [3.5,8.0]
     s    # swap to x coordinates                               [3.5,8.0], [1,3,5]
      ¥   # get deltas, consecutive differences                 [3.5,8.0], [2,2]
       *  # element-wise multiplication                         [7.0,16.0]
        O # take the sum                                        23.0
\$\endgroup\$
1
\$\begingroup\$

Perl 5 (-p), 56 bytes

s;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{

Try it online!

-M5.01 option and say($\),$\=""if$\; header are needed only to run all tests otherwise the program works for one line.

example: perl -pe 's;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{' <<< '1,2 3,5 5,11'

trick: -p option with }{ at the end so that continue block is not executed on each iteration but at the end, and $_ is empty so only $\ is printed

deparse: perl -MO=Deparse -pe 's;(\d+),(\d+)(?= (\d+),(\d+));$\+=($3-$1)*($2+$4)/2;ge}{'

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

Vyxal s, 11 bytes

ÞT÷2lvṁ$¯ȧ*

Try it Online!

ÞT          # Transpose
  ÷         # Push each to stack (y is on top
   2l       # Groups of 2
     vṁ     # Averaged
       $    # Swap to get x coords
        ¯ȧ  # Deltas
          * # Multiply the two
            # Sum that. 

There's probably a better way :p

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

Retina, 63 bytes

\d+
*
|""L$vm`^(_*),(_*)¶\1(_+),(_*)
$.3*$($2$4
^(__)*
$#1
_
.5

Try it online! Takes newline-separated pairs but link is to test suite that splits on semicolons for convenience. Explanation:

\d+
*

Convert to unary.

|""L$vm`^(_*),(_*)¶\1(_+),(_*)

Match overlapping sets of four values from two lines.

$.3*$($2$4

Multiply the difference between the first and third value by the sum of the second and fourth value.

^(__)*
$#1
_
.5

Divide by 2 and convert to decimal.

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

Octave / MATLAB, 6 bytes

@trapz

Try it online!

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

Japt, 16 bytes

ÕÌä+ í*UÕÎäa)x÷2

Try it

ÕÌä+ í*UÕÎäa)x÷2     :Implicit input of array U
Õ                    :Transpose
 Ì                   :Last element
  ä+                 :Consecutive pairs, reduced by addition
     í*              :Interleave with, reducing each pair by multiplication
       UÕÎ           :  Last element of transposed U
          äa         :  Consecutive pairs, reduced by absolute difference
            )        :End interleave
             x       :Reduce by addition
              ÷2     :Divide by 2
\$\endgroup\$
0
\$\begingroup\$

dc, 70 bytes

1k[sysxdly+2/syrdlxr-sxrlxly*lad1+sa:az4!>L]dsLxc[la1-ddsa;ar0<L+]dsLx

Try it online!

One decimal place of precision (1k) is sufficient because the longest fractional part we can have is 0.5. There could be better ways of twiddling the bits around.

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

Charcoal, 24 bytes

I⊘ΣEΦθκ×⁺§ι¹⊟§θκ⁻§ι⁰⊟§θκ

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

     θ                      Input array
    Φ                       Filtered on
      κ                     Current index
   E                        Map over tail
         §ι¹                Current Y-coordinate
        ⁺                   Plus
            ⊟§θκ            Previous Y-coordinate
       ×                    Multiplied by
                 §ι⁰        Current X-coordinate
                ⁻           Minus
                    ⊟§θκ    Previous X-coordinate
  Σ                         Take the sum
 ⊘                          Divide by 2
I                           Cast to string
                            Implicitly print
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 74 72 bytes

-2 thanks to @ceilingcat

a;r(int*x){for(a=0;~x[2];)a+=(x[2]-*x)*(*++x+x++[2]);printf("%f",a/2.);}

Takes input as a flat list terminated with -1 (e.g. {x1, y1, x2, y2, ..., -1})

Try it online!


C (gcc), 78 75 bytes

-3 (indirectly) thanks to @ceilingcat

a;r(int*x,int*y){for(a=0;~*++x;)a+=(*x-x[-1])*(*y+++*y);printf("%f",a/2.);}

Try it online! Takes input as a list of xs and a list of ys, terminated with -1.

\$\endgroup\$
0

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.