Calculate the sum of numbers in a rectangle

Question

Aim

Consider this infinite array of numbers:

 | 0 1 2 3 4 5 6 7
−+−−−−−−−−−−−−−−−−−−−−−−−
0| 0 2 5 9 14 20 27 35
1| 1 4 8 13 19 26 34
2| 3 7 12 18 25 33
3| 6 11 17 24 32
4|10 16 23 31
5|15 22 30
6|21 29
7|28

(The numbers from 0-7 at the left are row numbers; The numbers from 0-7 at the top are column numbers

Input: 4 non-negative integers specifying the size of the box (row number of top, column number of left, row number of bottom, column number of right)

Output: Sum of all integers in the box

Test cases:

a,b,c,d -> sum
0,0,1,2 -> 20 #0+2+5+1+4+8
2,0,6,1 -> 140 #3+7+6+11+10+16+15+22+21+29
1,2,2,3 -> 51 #8+13+12+18
0,0,0,0 -> 0 #0

You can assume a≤c and b≤d.

Other options:

• The four integers can be taken in any order
• You can take the coordinates of one specified corner as well as the width and height. In that case, you can assume width and height are positive integers.
• Coordinates can be 0-indexed or 1-indexed
• Ranges can be inclusive at both ends, exclusive at both ends or inclusive at one end and exclusive at the other. In that case, you can assume the rectangle has at least 1 row and at least 1 column.

These choices must be specified in the answer.

Shortest code wins.

• nyxbird: can we take the width and height of the box instead of its second coordinate?
• Lucenaposition: Changed my mind: that is allowed.

Answer 1

Python, (削除) 61 (削除ここまで) 59 bytes

f=lambda a,b,c,d:c<d and((c+b)**3-b)/6+b*c-f(b,a,c+(b<a),d)

Attempt This Online!

Takes top incl, bottom excl, left incl, right excl.

How?

Just seeing that @Jonathan Allan scooped me on this insight.

Based on the observation that the first column are just triangle numbers. Its partial sums are tetrahedral numbers and we can compute the sum of the first column as \$(\begin{smallmatrix}{\rm bottom}\3円\end{smallmatrix})-(\begin{smallmatrix}{\rm top}\3円\end{smallmatrix})\$. As for other columns, they are just shifted up and have a constant offset added, for example, the second column is the same as the first, except each value is shifted upwards one grid unit and incremented by one.

• Lucenaposition: Seems like your code also gives the correct output in Python 2, even though the / is floor division instead of normal division. However, in Python 2, you don't have the floating point imprecision issues.
• Albert.Lang: @Lucenaposition yes, roundoff errors introduced by floor division are expected to cancel exactly.

Answer 2

Python 3.8 (pre-release), (削除) 99 (削除ここまで) (削除) 79 (削除ここまで) (削除) 74 (削除ここまで) (削除) 73 (削除ここまで) (削除) 70 (削除ここまで) (削除) 68 (削除ここまで) 67 bytes

-20 bytes by removing the auxiliary t lambda, since it was only used once.
-5 bytes thanks to Lucenaposition.
-1 byte thanks to Arnauld.
-3 bytes thanks to l4m2.
-2 bytes by using the splat operator again.
-1 byte thanks to Lucenaposition.

lambda*a,c,d:sum(x-y*~y/2for x in range(*a)for y in range(c+x,d+x))

Takes input like f(inclusiveTopY, exclusiveBottomY, inclusiveLeftX=..., exclusiveRightX=...).
Try it online!

• Arnauld: You can do x-(s:=x+y)*~s/2.
• l4m2: 70
• squareroot12621: @Lucenaposition: I thought that didn't work... Here, have an upvote.

Answer 3

Python 3, 75 bytes

Just wanted to see how far a closed formula can go. Uses the same inclusive bounds as in the question, in slightly different order.

lambda a,b,c,d:(a+~b)*(c+~d)*((a+b)*(b+3*(c+d)/2+5)+d*(2+d+c)-c*~c+a*~-a)/6

Try it online!

Started with this formula generated by WolframAlpha:

$$ \sum_{x=a}^b \sum_{y=c}^d{x + \frac{\left(x + y\right) (x + y + 1)}2} = \\ \frac{1}{12} (a - b - 1) (c - d - 1) (2 a^2 + a (2 b + 3 c + 3 d + 8) + 2 b^2 + b (3 c + 3 d + 10) + 2 (c^2 + c d + c + d^2 + 2 d)) $$

Answer 4

JavaScript (Node.js), 55 bytes

f=(x,y,X,Y)=>X?x<X&&f(y,x,Y)+f(x+1,y,X,Y):x-(y+=x)*~y/2

Try it online!

• Neil: (x-X&&f(x+1,y,X)) saves a byte.

Answer 5

Python 3, 73 bytes

lambda a,b,c,d:(e:=c-a)*(f:=d-b)*(e*e+f*f+3*(~a-b-c-d)**2-12*(a+c)-17)/24

Try it online!

I tried golfing a closed formula (independently of ovs) that I first found using sympy, even though this code is longer than squareroot12621's solution which uses list comprehensions.

Inputs are inclusiveTopY, inclusiveLeftX, exclusiveBottomY, exclusiveRightX. This means (a,b,c,d) corresponds to the rectangle range(a,c) x range(b,d).

These half-open ranges have the advantage that c-a and d-b are factors, since the rectangles have dimensions of zero when a==c and b==d, without need for an off-by-1 correction. The differences c-a and d-b appear again later in the formula, so the code aliases them to e and f using walruses.

The formula is a bit nicer to see in a more symmetrical form:

$$ f(a,b,c,d) = \frac{1}{24}(c-a)(d-b) \cdot \\ \left(3(a+b+c+d)^2 + (c-a)^2 + (d-b)^2 + 6(d-c+b-a) - 14 \right)$$

79 bytes

lambda a,b,c,d:(c-a)*(d-b)*(3*(a+b+c+d)**2+(c-a)**2+(d-b)**2+6*(d-c+b-a)-14)/24

Try it online!

• Albert.Lang: Just in case you missed it: OP has changed their mind and now allows width and height as arguments.

Answer 6

Desmos, 49 bytes

f(a,b,c,d)=∑_{x=a}^b∑_{y=c}^d((x+y)^2+3x+y)/2

Order: inclusiveLeftX, inclusiveRightX, inclusiveTopY, inclusiveBottomY

Try it online

• Aiden Chow: The header link should be just a link to the language website (in this case, https://www.desmos.com/calculator). The link to your code should be separate from the header link and should be placed in the body of your answer. You also can replace \sum with ∑ to save 2 bytes. A bit of algebraic manipulation gives a further two bytes save. Here is a link that shows the resulting golfs: Try It On Desmos!
• Aiden Chow: You can see an example of how I format my answers in this Desmos answer of mine: codegolf.stackexchange.com/a/272766/96039
• Aiden Chow: This is 49 bytes, not 45. The ∑ character counts as 3 bytes.
• Aiden Chow: You can use a byte counter tool like this one to find the byte count of your answer.

Answer 7

Haskell, (削除) 53 (削除ここまで) (削除) 48 (削除ここまで) 47 bytes

• -5 bytes thanks to xnor
• -1 byte thanks to Wheat Wizard ♦

f a b c d=sum$do i<-[a..c];j<-[b..d];j:[1..i+j]

Try it online!

The code above is equivalent to:

f a b c d = sum[h i j | i<-[a..c], j<-[b..d]]
h r c = sum[0..r+c] + c

• the helper function h computes the value for row r and column c
  • The value in the first column is equal to the number of elements in the upper triangle, i.e. the (anti-)diagonals above. Each diagonal has one more element than the preceding: $$h(r,0) =0+1+2+3+4+...+r=\sum_{i=0}^ri$$
  • To compute a general element we can compute the leftmost value of its (anti)diagonal (i.e. h(r+c,0)) and then go up by c steps (i.e. sum c): $$h(r,c)=h(r+c,0)+c$$
• [h i j | i<-[a..c], j<-[b..d]] applies h to all pairs (a,b), (a,b+1), ..., (a,d), (a+1,b), (a+1, b+1,), ..., (c,d)

• xnor: Though I like the <$> <*>, it looks like just writing out the comprehension is shorter here: Try it online!
• Wheat Wizard: 47 bytes by using do notation.

Answer 8

Jelly, (削除) 11 (削除ここまで) 9 bytes

-2 thanks to Unrelated String (use of the table hyper, þ, to avoid separately taking the Cartesian product with Œp).

r+R;ɗþ/FS

A dyadic Link that accepts the top-left coordinate on the left ([row, column]) and the bottom-right coordinate on the right ([row, column]) and yields the sum.

Try it online! Or see the test-suite.

How?

The value at a given coordinate is the triangle number of the sum of the row and column (the minimum value on its running diagonal) plus its column (the number of steps taken along that diagonal).

r+R;ɗþ/FS - Link: [Top, Left], [Bottom, Right]
r - {[Top, Left]} inclusive range {[Bottom, Right]} (vectorises)
 -> [[Top..Bottom], [Left..Right]]
 / - reduce by - f([Top..Bottom], [Left..Right]):
 þ - table of:
 ɗ - last three links as a dyad - f(R, C):
 + - {R} add {C} -> R+C
 R - range -> [1..R+C]
 ; - concatenate {C} -> [1,2,...,R+C,C]
 F - flatten 
 S - sum

• Jonathan Allan: rŒp+R;ɗ/€SS, sometimes I wish there was a "total" monad.
• Unrelated String: I just posted this as a separate answer before deleting when I noticed you already got most of the way there, but rŒp+R;ɗ/€SS is 9 as r+R;ɗþ/FS.
• Jonathan Allan: Great golfing as always! Thanks :)

Answer 9

05AB1E, 15 bytes

ŸŠŸâεηO`D±;*-}O

Port of @l4m2's comment on @squareroot12621's Python answer, so make sure to upvote that answer, as well as @l4m2's Javascript answer!

Takes four inputs in the order \$b,d,a,c\$, all four inclusive.

Try it online or verify all test cases.

Explanation:

Ÿ # Create a [b,d]-ranged list of the first two (implicit) inputs
 Š # Triple-swap to push the next two (implicit) inputs to the stack
 Ÿ # Create an [a,c]-ranged list of those two inputs as well
 â # Cartesian product to create all pairs of these two lists
 ε # Map over each pair [x,y]:
 ηO # Cumulative sum it:
 η # Get the prefixes of this pair: [[x],[x,y]]
 O # Sum each inner list: [x,x+y]
 ` # Pop and push those two values to the stack
 D # Duplicate the top one
 ± # Bitwise-NOT: -(x+y)-1
 ; # Halve: (-(x+y)-1)/2
 * # Multiply the top two: (x+y)*((-(x+y)-1)/2)
 - # Subtract the top two: x-(x+y)*((-(x+y)-1)/2)
 }O # After the map: sum this list
 # (after which the result is output implicitly)

Answer 10

Charcoal, (削除) 26 (削除ここまで) 23 bytes

≔...NNθIΣE...NNΣEθ+λΣ...·0+ιλ

Try it online! Link is to verbose version of code. Takes inputs in the order exclusive column range, exclusive row range e.g. the test case 2, 0, 6, 1 becomes 0 2 2 7. Explanation:

≔...NNθ

Read in the exclusive column range.

IΣE...NNΣEθ+λΣ...·0+ιλ

Map over the exclusive row range, calculating the value of each cell, then double sum over the results.

Answer 11

C (gcc), 60 bytes

f(x,y,X,Y){x=X?x<X?f(y,x,Y,0)+f(x+1,y,X,Y):0:x-(y+=x)*~y/2;}

Try it online!

Simple port of l4m2's answer.

Answer 12

Pyth, 37 bytes

JEKE=GE=TEVrJKVr+GN+TN aY+/*H+1H2N;sY

Port of squareroot12621's answer. Had to work around the binary NOT.

Try it here

JEKE=GE=TE Assign variables J, K, G, T
VrJK For N in range(J, K)
 Vr+GN+TN For H in range(G+N, T+N)
 aY+/*H+1H2N Y.append(N + (H * (H + 1) / 2))
;sY Print sum(Y)

Answer 13

APL+WIN, 36 bytes

Prompts for the 3rd and 4th inter as specified in the examples followed by the 1st and 2nd. Index origin = 0

+/+/⎕↓n↑(⍳m)⊖⊃(+\⍳m)+⍳ ×ばつ↑n←1+⎕

Try it online! Thanks to Dyalog Classic