The Area of Rectangles

Question

Getting the area covered by a rectangle is really easy; just multiply its height by its width. However in this challenge we will be getting the area covered by multiple rectangles. This is equally easy ... so long as the rectangles don't overlap.

If the rectangles don't overlap the total area covered is the sum of the areas of each individual rectangle. However if they do overlap this method will double count the area they intersect.

For example, in the following picture we have 2 rectangles: A rectangle with opposite corners at \$(3,7)\$ and \$(9,3)\$ and a rectangle with opposite corners at \$(8,10)\$ and \$(14,4)\$. On their own they cover \$24\$ and \$36\$ square units respectively. However they have an overlap area of 3 units so the total area covered by the both of them is \$24 + 36 - 3 = 57\$

Task

Your task is to take a list of positive integer rectangles as input and output the total area covered by those rectangles.

You may take a rectangle as a pair of pairs representing opposite corners, or as a flattened 4-tuple. You may assume a particular pair of corners in a certain order will be given if you please.

This is code-golf so answers will be scored in bytes with fewer bytes being the goal.

Test cases

[((3,7),(9,3))] -> 24
[((8,10),(14,4))] -> 36
[((3,7),(9,3)),((8,10),(14,4))] -> 57
[((8,10),(14,4)),((3,7),(9,3)),((5,8),(10,3))] -> 61
[((1,1),(8,8)),((2,3),(3,5))] -> 49

Answer 1

Ruby, 60 59 bytes

->r,*w{r.map{|a,b,c,d|w|=[*a...c].product [*d...b]};w.size}

Try it online!

Input: array of array of coordinates: [left, top, right, bottom]

Convert every rectangle to a set of cells, and calculate the size of the union of the sets.

Answer 2

Jelly, 10 bytes

r/Ḋ€p/)ẎQL

A monadic Link that accepts a list of rectangles each composed of a list of opposing corner coordinates as specified.

Try it online!

How?

Constructs the coordinates of a corner of each unit square of each rectangle, and counts the unique values found in the resulting collection.

r/Ḋ€p/)ẎQL - Link: integer rectagle corner coordinates, R
      )    - for each rectangle, r in R:
 /         -   reduce by:
r          -     inclusive range
  Ḋ€       -   dequeue each (we exclude one edge, consistently, from each dimension, as we
                             want "fences", rather than "fence-posts")
     /     -   reduce by:
    p      -     Cartesian product -> all the coordinates we want for the rectangle
       Ẏ   - tighten -> all coordinates used by all rectangles
        Q  - deduplicate
         L - length

Answer 3

Wolfram Language (Mathematica), 30 bytes

Area[RegionUnion@@Cuboid@@@#]&

Try it online!

Input a list of {bottom left, top right} pairs.

Answer 4

K (ngn/k), 22 bytes

#?,/{+a+!(|/x)-a:&/x}'

Try it online!

Or, if we can take corners as (lower-left, upper-right) pairs:

K (ngn/k), 18 15 bytes

#?,/{+x+!y-x}/'

Try it online!

Answer 5

JavaScript (ES6), 96 bytes

A very basic solution that tests whether each cell in the grid belongs to at least one rectangle.

Expects a list of flattened 4-tuples.

a=>eval(`for(t=0,x=q=Math.max(${a});x--;)for(y=q;y--;)t+=a.some(([a,b,c,d])=>x<a^x<c&&y<b^y<d)`)

Try it online!

How?

When coerced to a string, an array is always turned into a flattened list of values separated with commas. For instance, [[3,7,9,3],[8,10,14,4]] is turned into the string "3,7,9,3,8,10,14,4".

As a consequence, eval(`q = Math.max(${a})`) loads in q the highest value that can be found in a[], no matter the encapsulation depth of any sub-arrays in there.

For each position \$(x,y),\:0\le x<q,\:0\le y<q\$ and each rectangle tuple \$(a,b,c,d)\$, we increment the final result if:

$$((x < a)\operatorname{XOR}(x < c)) \operatorname{AND} ((y < b)\operatorname{XOR}(y < d))$$

Note that \$((x < a)\operatorname{XOR}(x < c))\$ is true iff we have either \$x\in[a,c[\$ or \$x\in[c,a[\$ (ditto for \$y\$, \$b\$ and \$d\$). This means that the corners can be passed in any order, as suggested by the test cases (it turns out that it's actually not a strict requirement).

Answer 6

Python 3, ^{76 74} 73 bytes

lambda l:len({(x,y)for*a,b,c in l for x in range(*a)for y in range(b,c)})

Try it online!

Saved 2 bytes thanks to att!!!
Saved a byte thanks to Jitse!!!

Inputs a list of rectangles as flattened 4-tuples - (left, right, bottom, top).
Returns the area.

Answer 7

05AB1E, 13 bytes

εøεŸ¨}`â}€`Ùg

Try it online or verify all test cases.

Explanation:

ε      # Map over each pair of coordinates in the (implicit) input-list:
 ø     #  Zip/transpose; swapping rows/columns
       #  (so we'll have a list [[Xa,Xb],[Ya,Yb]]
  ε    #  Map both to:
   Ÿ   #   Pop the pair, and push a list in this range
    ¨  #   Remove the last item, so the range is [a,b)
  }`   #  After the inner map: pop and push both lists separated to the stack
    â  #  Get the cartesian product of these two lists
}€`    # After the outer map: flatten this list of list of pairs one level down
   Ù   # Uniquify this list of cell-coordinates
    g  # And pop and push its length
       # (after which the result is output implicitly)

Answer 8

Husk, 11 bytes

Luṁ(ΠmhṁẊ…T

Try it online!

Lu              # length of uniqe elements from
  ṁ(            # mapping over input:
    Π           #  cartesian product of:
       ṁ        #   for each coordinate pair
          T     #    transpose
        Ẋ…      #    and get the range,
     mh         #    (removing the last element)

Answer 9

Charcoal, 42 40 bytes

ＩΣＥ⌈Ｅθ⌈ιΣＥ⌈Ｅθ⌈λ⊙θ∧››§ν²ι›§ν⁰ι››§ν³λ›§ν¹λ

Try it online! Link is to verbose version of code. Takes input as a list of 4-tuples (bottom, left, top, right). Edit: Saved 2 bytes after reading @Arnauld's answer. Explanation:

    Ｅθ                                      Map over input list
      ⌈ι                                    Get maximum co-ordinate
   ⌈                                        Take the maximum
  Ｅ                                         Map over implicit range
           Ｅθ                               Map over input list
             ⌈λ                             Get maximum co-ordinate
          ⌈                                 Take the maximum
         Ｅ                                  Map over implicit range
                θ                           Input list
               ⊙                            Does any rectangle match
                       ι    ι               Current y value
                  ››§ν² ›§ν⁰                Inside rectangle bounds
                                  λ    λ    Current x value
                             ››§ν³ ›§ν¹     Inside rectangle bounds
                 ∧                          Logical And
        Σ                                   Take the sum
 Σ                                          Take the sum
Ｉ                                           Cast to string
                                            Implicitly print

A coordinate x is within a half-open range [a, b) if it is less than b but not less than a. In normal logic, this is written (b>x)&&!(a>x), however the &&! operator works out as equivalent to the > operator so the result is simply (b>x)>(a>x).

Answer 10

Julia 1.0, 55 bytes

!t=length(∪([(a:c-1).=>(b:d-1)' for (a,b,c,d)=t]...))

Try it online!

• input is an array of flattened 4-tuples in the order (left,bottom,right,top)

• for each rectangle, we create all their points in the form x=>y with (a:c-1).=>(b:d-1)'

  example with (1,2),(4,6):

  julia> (1:4-1).=>(2:6-1)'
  3×4 Matrix{Pair{Int64, Int64}}:
  1=>2  1=>3  1=>4  1=>5
  2=>2  2=>3  2=>4  2=>5
  3=>2  3=>3  3=>4  3=>5
  

• then ∪ (union) removes duplicates

• length is self-explanatory I think

Answer 11

Scala, 72 bytes

_.map{(?,<,c,d)=>Set(?to c-1*)flatMap(d+1 to<map _.->)}.reduce(_|_).size

Try it in Scastie!

Does it the simple, stupid way: by making sets of all the points each rectangle contains and then finding the size of their union. Input is a list of flattened 4-tuples, with the top left corner first and the bottom right corner second.

Answer 12

Python 3, 83 bytes

lambda a:len({*chain(*[product(*map(range,*x))for x in a])})
from itertools import*

Try it online!

-3 thanks to pxeger.

Answer 13

Gaia, 11 bytes

N†⊢×⊢
↑¦|⊢l

Try it online!

N†⊢×⊢  -- helper function to convert rectangle corners to coordinate list
N†⊢    -- reduce rows by vectorized half-inclusive range
   ×⊢  -- reduce the two ranges by cartesian product

↑¦     -- map the helper function over each rectangle
  |⊢   -- reduce by set union
    l  -- take the length