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:

rectangles

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

split-one split-two

You'll also need to handle the following:

All test cases

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!

• Martin Ender: Related.
• tsh: can we assume that the given input {(x1, y1), (x2, y2)} holds x1 < x2 and y1 < y2?
• Nathan Merrill: Yep. The rectangle will have an area of 1, and you can order the coordinates in any order you like.
• Евгений Новиков: Is edge thick? When rectangle defined is edge included?
• Nathan Merrill: The edge has 0 thickness.

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

• notjagan: -15 bytes by making various golfing improvements, or -18 bytes using strings in Python 3.
• musicman523: You can snip off two more bytes by doing p=product and replacing product(product with p(p

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

• Chas Brown: This is a promising approach; but it currently fails sometimes, e.g., when the Mask rectangle has no overlap with the Source rectangle; e.g. f([0, 30, 10, 40])([5, 1, 6, 2]) should return [[0, 30, 10, 40]] but instead returns [[0,30,5,40],[6,30,10,40]]
• tsh: @NathanMerrill ok, edited.
• Nathan Merrill: @tsh looks good!

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.