8
1
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!
Must the rectangle have a corner at (0,0)? Can the coordinates be negative? – xnor – 2016-11-16T03:33:13.893
Are we guaranteed that each rectangle has
x1 <= x2
andy1 <= y2
? Is an area 0 rectangle withx1 == x2
andy1 <= y2
possible? – xnor – 2016-11-16T03:35:52.087@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. – HyperNeutrino – 2016-11-16T03:49:56.030
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
andy1 > y2
, is this an area-zero rectangle because the coordinates are switched? – xnor – 2016-11-16T04:31:33.4732Someone watched numberphile? – orlp – 2016-11-16T05:58:46.860
Just one comment about NP-hard: When the edge positions are integers in a given range (e.g. 0 to 2^16-1) this problem can be solved in linear time using a monochrome bitmap. However using less than ~100.000 rectangles the exponential-time algorithm will be way faster than the linear time algorithm. – Martin Rosenau – 2016-11-16T06:29:42.173
I fail to see how the first "true" test case is so.
the bounding rectangle has to be (0,0)-(3,2); but it will have a gap (0,1)-(3,1) – Eyal Lev – 2016-11-16T11:50:34.087
@EyalLev My bad, I edited the test case. – HyperNeutrino – 2016-11-16T13:15:18.820