26
3
Can these rectangles fill a rectangular space?
Given a bunch of rectangles, you are asked whether or not they can be arranged to fill a rectangular space.
Specs
Given a bunch of arbitrary m x n
rectangles; 0 <= m, n <= 1000
, determine whether or not it is possible to arrange them so that they cover exactly a rectangular area without any holes or overlaps. The rectangles cannot be rotated, and each rectangle may only be placed once.
Input
The input for this is very flexible, as long as the input gives some sort of list of 2-space dimensions. For example, both of the following are valid:
Separated by Space, Return
1 2
1 5
4 5
3 6
List of Dimensions
[[1, 2], [1, 5], [4, 5], [3, 6]]
Output
Any sort of true/false values like true/false, 0/1, T/F, True/False, etc. If you are going to use an output method that's not very obvious, please specify in your answer.
Examples
Test Case 1
Input:
1 1
1 5
2 6
Output:
true
(or something similar)
How to arrange it:
XYYYYY
ZZZZZZ
ZZZZZZ
Test Case 2
Input:
1 1
2 2
Output:
false
(or something similar)
Explanation: It becomes obvious that you cannot arrange two squares of different sizes and get their edges to line up.
Test Case 3
Input:
1 1
1 2
1 2
2 1
2 1
Output:
true
(or something similar)
How to arrange it:
AAB
DEB
DCC
As @ETHProductions pointed out, for all of the other test cases, you can keep combining rectangles with a common edge length until you have only one rectangle, so this test case is just to break any code that uses this idea.
Test Case 4
Input:
3 2
4 1
2 1
4 1
2 1
5 2
3 2
1 4
3 2
2 1
2 1
1 1
5 1
Output:
true
(or something similar)
How to arrange it:
AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH
Note: You do not need to state how to arrange it, you only need to determine whether not it can be arranged.
This is code golf, so the shortest answer in bytes wins! I will accept the shortest answer as of January 14th, but feel free to submit answers later than that since I can still give upvotes! :)
Happy golfing!
~ A.L.
P.S. If you know what tag should be applied to this problem, please add it, I have absolutely no idea what to put as a tag other than code-golf.
EDIT: Your program should be able to process up to 25 rectangles, in at most 10 seconds on a decent computer (I'll be quite flexible on this rule).
EDIT: I've extended the submission acceptance deadline to the last day of the year, but I doubt I'll get an answer by then...
EDIT: I've extended the submission acceptance deadline by 2 weeks, so if no more answers come in by then, the current C answer will be accepted! :)
I take it each input rectangle be used only once? – xnor – 2016-10-21T03:00:48.290
7Why is there a deadline? You could say that you'll accept an answer at that time, but challenges should be open indefinitely :) – Nathan Merrill – 2016-10-21T03:01:50.427
Also, you should indicate that "tiling" means placing each rectangle down exactly once. If you allow multiple placements, then any tiling is valid. – Nathan Merrill – 2016-10-21T03:15:10.497
4Can the rectangles be rotated? – xnor – 2016-10-21T05:36:59.097
@NathanMerrill That's what I meant. :) I'll clarify in the question. – HyperNeutrino – 2016-10-21T13:56:42.313
@NathanMerrill That is true. As xnor asked as well, each rectangle can only used once so I will clarify. – HyperNeutrino – 2016-10-21T13:57:10.027
@xnor No, they cannot. I will clarify. – HyperNeutrino – 2016-10-21T13:57:34.733
@PeterTaylor That is true. I will change the wording; see if it's a bit more clear what the question is. – HyperNeutrino – 2016-10-21T13:58:08.717
upvoted because I'm tearing my hair out trying to get any code to work, not just golfed. – Gabriel Benamy – 2016-10-21T20:14:11.837
@GabrielBenamy Yeah, I have no idea even how to do this. :P – HyperNeutrino – 2016-10-22T20:51:59.110
3
Well, your problem is a decidability problem: "can these oriented rectangles be arranged to form another rectangle with 0 waste", which is an NP-complete problem (Korf, 2003: https://pdfs.semanticscholar.org/90a5/de6349bed23e94f23985867f79c87a68e4a6.pdf ). Korf's algorithm is essentially a brute-force with some optimizations to more efficiently eliminate configurations with no solution. I doubt a golf of this would be below 250 characters in most languages.
– Gabriel Benamy – 2016-10-22T21:37:02.613@GabrielBenamy Okay, that makes sense. Thank you for the resource. – HyperNeutrino – 2016-10-24T15:56:02.447
1The easy route would be to determine whether you can repeatedly combine two rectangles of the same width or height until you have 1 rectangle left. This algorithm works for all of the current testcases; however, it fails for
[[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]]
(which can be arrangedABB ACD EED
). You may want to add this simple test case. – ETHproductions – 2016-11-12T01:57:00.873@ETHproductions I was talking to one of the other students in my Grade 9 Science class, and he gave the same idea, and I gave him the exact same counter-example, which is quite coincidental... :P I'll add it. Thanks for pointing that out. – HyperNeutrino – 2016-11-12T01:58:47.990
So, I've made a solution. The problem is that it takes too long, because it's just brute-forcing everything, which is a terrible idea. – HyperNeutrino – 2016-11-12T03:05:53.660