9
\$\begingroup\$

This challenge is based on another similar challenge. Because finding the most efficient packing of rectangles is NP-hard (that is, its solution is easy to check but hard to find), this challenge is a lot easier than this one here

This Challenge

Given a bunch of rectangles, figure out whether or not they fill a rectangular space with no gaps or overlaps.

Input

Input can be in two forms, one of which carries a scoring penalty.

The first: it contains a list of sublists, each with length 4. This list contains 4 integers which are the coordinates of opposite vertexes. Since all rectangles will be horizontal/vertical, there is no ambiguity as to where the rectangle is. Each sublist will contain four integers, which, in order, are the x-coordinate of the first vertex, the y-coordinate of the first vertex, the x-coordinate of the second vertex, and the y-coordinate of the second vertex.

The second: it contains four lists of integers with the same length. The four lists represent the different coordinates. If you imagine input option 1 as a matrix, the input here is just the transpose of the matrix. This input carries a +20% byte penalty.

Output

Simple truthy/falsy output.

Specifications

If there is a rectangle with area 0 (that is, x1 == x2 || y1 == y2), disregard this rectangle (so [0 0 1 1], [2 2 3 2] is valid). This specification is in place to make it harder for people to simply get the min/max x/y values.

x1 <= x2 and y1 <= y2 are not always true. If x1 > x2 || y1 > y2, the rectangle is not a zero-area rectangle; rather, it occupies the rectangular space between (x1, y1) and (x2, y2).
Coordinates can be negative, in which case they still occupy the space between the coordinates.
The top-left-most rectangle is not always at (0, 0); thus, the rectangular space that is filled doesn't necessarily have its top-left corner at (0, 0).
(Thanks to @xnor for pointing out these ambiguities)

Please specify how you want your input and how your output will be represented.

Scoring

Score is the size of the code in bytes, plus a byte penalty if applicable. Lowest score as of December 15th wins.

Test Cases

0 0 1 2
1 0 3 1 ==> true
1 1 3 2

0 0 2 2
0 0 1 1 ==> false
0 0 0 0

0 0 1 1
2 2 2 2 ==> true
0 1 2 1

Good luck, happy golfing!

\$\endgroup\$
8
  • \$\begingroup\$ Must the rectangle have a corner at (0,0)? Can the coordinates be negative? \$\endgroup\$
    – xnor
    Nov 16, 2016 at 3:33
  • \$\begingroup\$ Are we guaranteed that each rectangle has x1 <= x2 and y1 <= y2? Is an area 0 rectangle with x1 == x2 and y1 <= y2 possible? \$\endgroup\$
    – xnor
    Nov 16, 2016 at 3:35
  • \$\begingroup\$ @xnor These are all little things I failed to consider. Thanks for pointing them out, I will clarify in an edit. My answers to those questions are no, yes, no, yes. \$\endgroup\$
    – hyper-neutrino
    Nov 16, 2016 at 3:49
  • \$\begingroup\$ I'd recommend the Sandbox for hammering out details like this is advance. Your test cases should cover as many of these corner cases as possible. I'm still unclear though on "Thus, the list will look like [x1, y1, x2, y2], where (x1, y1) and (x2, y2) represent the top-left and bottom-right vertexes". If x1 > x2 and y1 > y2, is this an area-zero rectangle because the coordinates are switched? \$\endgroup\$
    – xnor
    Nov 16, 2016 at 4:31
  • 2
    \$\begingroup\$ Someone watched numberphile? \$\endgroup\$
    – orlp
    Nov 16, 2016 at 5:58

2 Answers 2

1
\$\begingroup\$

JavaScript (ES6), 249 bytes

with(Math)a=>!(a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]).filter(g=([l,t,r,b])=>(r-l)*(b-t))).reduce((s,b)=>s-g(b),g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))

Note: To use this, either evaluate it as a string and assign the result to a variable, or insert the assignment after the with(Math). Explanation:

with(Math)a=>!( Bring min and max into scope.
a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]) Normalise the coordinates
.filter(g=([l,t,r,b])=>(r-l)*(b-t))) Remove empty rectangles, also defining a function to calculate area
.reduce((s,b)=>s-g(b), Subtract the areas of all the rectangles
g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i]))))) from the area of the bounding box
>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b)) and check that no rectangles overlap.

\$\endgroup\$
5
  • \$\begingroup\$ I'm having trouble testing this. Could you clarify what you mean by "insert the assignment"? (I have no ES6 experience whatsoever). Or if possible, could you provide a link to some test cases? Thanks. \$\endgroup\$
    – hyper-neutrino
    Nov 17, 2016 at 15:19
  • \$\begingroup\$ @AlexL. I mean you need to write e.g. with(Math)f=a=> etc. - putting the f= at the beginning won't work. \$\endgroup\$
    – Neil
    Nov 18, 2016 at 1:25
  • \$\begingroup\$ Okay. I see what you mean, but the online compilers I tried all gave me various errors. Could you provide a compiler that actually works (the other compilers are being weird)? \$\endgroup\$
    – hyper-neutrino
    Nov 18, 2016 at 3:20
  • \$\begingroup\$ @AlexL. Ah, I think I typoed one of my edits; I've double-checked and you should be OK now. \$\endgroup\$
    – Neil
    Nov 18, 2016 at 13:11
  • \$\begingroup\$ I'm marking this as accepted now. I'll trust you with the test results, and I'll keep trying to verify it. \$\endgroup\$
    – hyper-neutrino
    Dec 20, 2016 at 15:45
0
\$\begingroup\$

Mathematica, 194 bytes

(r=Select[#,(#-#3)(#2-#4)&@@#>0&];m={#~Min~#3,#2~Min~#4,#~Max~#3,#2~Max~#4}&@@Transpose@r;b=Boole[(x-#)(x-#3)<0&&(y-#2)(y-#4)<0]&;Integrate[(Plus@@(b@@@r)-b@@m)^2,{x,#,#3}&@@m,{y,#2,#4}&@@m]<1)&

An ungolfed version:

1  (r = Select[#1, (#1 - #3) (#2 - #4) & @@ #1 > 0 &]; 
2   m = {Min[#1, #3], Min[#2, #4], Max[#1, #3], Max[#2, #4]} & @@ Transpose[r]; 
3   b = Boole[(x - #1) (x - #3) < 0 && (y - #2) (y - #4) < 0] &;
4   Integrate[
5     (Plus @@ (b @@@ r) - b @@ m)^2 ,
6     {x, #1, #3} & @@ m ,
7     {y, #2, #4} & @@ m
8   ] < 1
9  ) &

Line 1 defines r to be the set of nontrivial rectangles from the given input. (There's a lot of & @@ going on in this code; that's just so we can use #1,#2,#3,#4 for the four elements of a list instead of #[[1]],#[[2]],#[[3]],#[[4]].) Then line 2 defines m to be the coordinates of the smallest rectangle bounding all of the ones listed in r; so if the input rectangles tile a large rectangle, that large rectangle must be m.

Line 3 defines function b which, when applied to a quadruple representing a rectangle, produces a function of two variables x and y that equals 1 if the point (x,y) is inside the rectangle and 0 if it's not. Line 5 produces many of these functions, one for each rectangle in r (all added together) and one last one for the large rectangle m (subtracted); that complicated two-variable function is then squared.

The key, at this point, is that that two-variable function is identically 0 if the small rectangles tile the large rectangle, but it will have some positive values if two small rectangles overlap, or some negative values (before squaring) if some part of the large rectangle isn't covered. We detect this by literally integrating(!) the two-variable function over the large rectangle (the limits of integration are given in lines 6-7): if we obtain 0, then the tiling was perfect, and if we obtain a positive value, then there was a problem somewhere. Since everything in sight is an integer, we save one final byte by using < 1 instead of == 0 in line 8.

(I think it's pretty fun that we can exploit Mathematica's ability to do calculus to solve this combinatorial problem.)

\$\endgroup\$

Your Answer

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

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