19
\$\begingroup\$

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

2 Overlapping rectangles

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 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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ "You may assume that the corners given will always be the bottom left and top right or bottom right and top left if you please." – does this include assuming the order of the corners, or do programs have to be able to handle both orders? \$\endgroup\$
    – m90
    Commented Oct 4, 2021 at 11:53
  • 1
    \$\begingroup\$ Can we input the coordinates in any order and not necessarily as corners, for example (left, right, bottom, top)? \$\endgroup\$
    – Noodle9
    Commented Oct 5, 2021 at 13:55
  • \$\begingroup\$ @Noodle9 Yes, that's what's meant by "You may assume a particular pair of corners in a certain order will be given if you please." \$\endgroup\$
    – Wheat Wizard
    Commented Oct 5, 2021 at 13:59

14 Answers 14

6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ 74 bytes with (left, right, bottom, top) \$\endgroup\$
    – att
    Commented Oct 4, 2021 at 21:23
  • 1
    \$\begingroup\$ -1 byte with ... for*a,b,c in ... \$\endgroup\$
    – Jitse
    Commented Oct 6, 2021 at 12:22
4
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

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

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

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!

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

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

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

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)
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Julia 1.0, 55 52 bytes

!t=length(∪([a:~-c.=>(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

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

Charcoal, 42 40 bytes

IΣE⌈Eθ⌈ιΣE⌈Eθ⌈λ⊙θ∧››§ν²ι›§ν⁰ι››§ν³λ›§ν¹λ

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:

    Eθ                                      Map over input list
      ⌈ι                                    Get maximum co-ordinate
   ⌈                                        Take the maximum
  E                                         Map over implicit range
           Eθ                               Map over input list
             ⌈λ                             Get maximum co-ordinate
          ⌈                                 Take the maximum
         E                                  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
I                                           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).

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

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can remove one of the [*]s: Try it online! \$\endgroup\$
    – pxeger
    Commented Oct 4, 2021 at 15:54
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 77 bytes

x=>x.map(([i,b,c,d])=>{for(;i++<c;)for(j=b;j++<d;)x[y=[i,j]]=s+=!x[y]},s=0)|s

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.