Rectangular difference

Question

In this challenge, you are given two overlapping rectangles, and you need to calculate the rectangles created by removing one from the other.

For example, if you remove the red rectangle from the black one:

You end up with one of the following two rectangle sets:

You'll also need to handle the following:

To be more explicit:

• You will input the coordinates of two rectangles, A and B.
• You need to output the fewest non-overlapping rectangles that cover all of the area of A without B. Any possible covering is allowed
• Rectangular coordinates are passed as 4 integers. You can pass them in two pairs (representing the two corner points), or as a tuple/list of 4 integers. Your inputs and outputs need to be consistent.
• A and B will not necessarily overlap or touch, and each will have an area of at least 1

Test cases:

[(0 0) (5 5)] [(3 4) (8 7)]   -> [(0 0) (5 4)] [(0 4) (3 5)] # or [(0 0) (3 5)] [(3 0) (5 4)]
[(2 4) (10 11)] [(5 5) (6 6)]  -> [(2 4) (10 5)] [(2 5) (5 6)] [(6 5) (10 6)] [(2 6) (10 11)]    #Other sets of 4 rectangles are possible
[(3 3) (8 8)] [(0 1) (10 8)]   ->    #No rectangles should be output
[(0 0) (5 5)] [(1 1) (10 2)]   -> [(0 0) (1 5)] [(1 0) (2 1)] [(2 0) (5 5)]  #Other sets of 3 rectangles are possible
[(1 5) (7 8)] [(0 0) (1 10)]   -> [(1 5) (7 8)]  #Only possible output
[(4 1) (10 9)] [(2 5) (20 7)]   -> [(4 1) (10 5)] [(4 7) (10 9)]  #Only possible output
[(1 1) (8 8)] [(0 6) (9 9)]     -> [(1 1) (8 6)]   #Only possible output

This is a code-golf, so make your code as short as possible!

Answer 1

Python 2, 375 360 345 343 bytes

from itertools import*;P=product
def f(S,M):(l,t),(r,b)=S;(L,T),(R,B)=M;u,v,x,y=(L>=r)+(l<L),(T>=b)+(t<T),(R>=r)+(l<R),(B>=b)+(t<B);return[S]if v==y!=1or u==x!=1else[list(p(p(*zip(*(S+M))),repeat=2))[[43,197,6,199,9,231,142,229,53,189,134,181][int(i,36)]]for i in '38,491,258,2058,8,4B,28,208,7,41,27,461,,4,2,4A'.split(',')[u+2*v+4*x+8*y-12]]

Try it online!

EDITS: -15 from suggestions from @notjagan; another -15 by re-encoding the array of solution rectangles to int36 format and a short lookup table; another -2 by replacing product with p as per @musicman.

A function that takes two rectangles, each rect being a tuple of ((left,top), (right,bottom)); returns a list of the resulting rectangles.

The basic strategy:

     |     |
 0,0 | 1,0 | 2,0
-----A-----+-----
     |     |
 0,1 | 1,1 | 2,1
-----+-----B-----
     |     |
 0,2 | 1,2 | 2,2
     |     |

In the above diagram, the points A and B are the upper left and lower right, respectively, of the 'Source' rectangle (the first rect).

We find the placement of each of the the upper left (u,v) and lower right (x,y) of the 'Mask' rectangle in that grid.

If both these points are in the first or last column; or first or last row; then there is no overlap; and we can return just the Source rect.

Otherwise, there are 16 cases remaining; for example, the OP's first example is the case we can label (1,1),(2,2). Each case can be mapped to a set of resulting rectangles whose corners are always coordinates with horizontal values in either Source rectangles left,right, or the Mask rectangles left,right; and similarly for the vertical values, the Source's top,bottom or the masks.

For example, for the (1,1),(2,2) case, the rectangles would be ((l,t),(T,r)) and ((l,T),(R,b)), where l,t,r,b and L,T,R,B are the left, top, right and bottom of the Source and Mask rectangles, respectively.

So we can create a lookup table that maps the coordinates to the set of all such possible combinations (which is what the product(product(*zip(*))) bit is about) to a set of rectangles that should be provided for each of the cases (which, after some golfy-decompression, is what the rest of the list stuff is about).

Answer 2

JavaScript, 115 bytes

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=a[i]=n,p)).filter(x=>x)

overlapping version:

f=a=>b=>b.some((n,i)=>(a[i^2]<n)^i/2)?[a]:b.map((n,i)=>a[i&1]<n&&n<a[i|2]&&(p=[...a],p[i^2]=n,p)).filter(x=>x)

Input in following format: f([1,1,8,8])([0,6,9,9])

---

Denote input as ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4))

If any one of following conditions is met, return first rectangle as is:

• x3 > x2
• x4 < x1
• y3 > y2
• y4 < y1

otherwise

• If x1 < x3 < x2 then we generate a rectangle ((x1, y1), (x3, y2)); and set x1 := x3
• If x1 < x4 < x2 then we generate a rectangle ((x4, y1), (x2, y2)); and set x2 := x4
• If y1 < y3 < y2 then we generate a rectangle ((x1, y1), (x2, y3)); and set y1 := y3
• If y1 < y4 < y2 then we generate a rectangle ((x1, y4), (x2, y2)); and set y2 := y4

Answer 3

Java, 268 bytes

class W{public static void main(String[]z) {int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};for(i=0;i<4;i+=1){for(j=0;j<4;j+=1){a[j]=Integer.parseInt(z[y[i*4+j]]);}if(a[0]<a[2] && a[1]<a[3]){for(j=0;j<4;j+=1){System.out.println(String.valueOf(a[j]));}}}}}

Ungolfed

class W{
    public static void main(String[]z) {
        int a[]={0,0,0,0},i,j,y[]={0,1,4,3,6,1,2,3,4,1,6,5,4,7,6,3};

        for(i=0;i<4;i+=1){
            for(j=0;j<4;j+=1){
                a[j]=Integer.parseInt(z[y[i*4+j]]);
            }
            if(a[0]<a[2] && a[1]<a[3]){
                for(j=0;j<4;j+=1){
                    System.out.println(String.valueOf(a[j]));
                }
            }
        }
    }
}

Pass input as arguments. Example

java -jar W.jar 0 0 5 5 3 4 8 7

Answer 4

Python 2, 272 bytes

lambda((a,b),(c,d)),((e,f),(g,h)):[([([[(a,b),(e,min(h,d))]]+[[(g,max(b,f)),(c,d)]]*2+[[(max(a,e),b),(c,f)]]*4+[[(a,h),(min(c,g),d)]])[m-1]for m in M&{1,2,4,8}]if M&{0}else[(a,b),(c,d)])for M in[{(x<e)*1+(x>g)*2+(y<f)*4+(y>h)*8 for x in range(a,c)for y in range(b,d)}]][0]

Try it online!

This works by testing every cell inside the first rectangle for leftness=1,aboveness=4,rightness=2,and belowness=8 w/r to the other, and ORing the result. If the other does not intersect=0 with the first, then the original is returned, otherwise some combination of a left slice, right slice, upper slice and lower slice is returned, with accomodation for overlap.