26
\$\begingroup\$

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! :)

\$\endgroup\$
  • \$\begingroup\$ I take it each input rectangle be used only once? \$\endgroup\$ – xnor Oct 21 '16 at 3:00
  • 7
    \$\begingroup\$ Why is there a deadline? You could say that you'll accept an answer at that time, but challenges should be open indefinitely :) \$\endgroup\$ – Nathan Merrill Oct 21 '16 at 3:01
  • 4
    \$\begingroup\$ Can the rectangles be rotated? \$\endgroup\$ – xnor Oct 21 '16 at 5:36
  • 3
    \$\begingroup\$ 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: pdfs.semanticscholar.org/90a5/… ). 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. \$\endgroup\$ – Gabriel Benamy Oct 22 '16 at 21:37
  • 1
    \$\begingroup\$ The 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 arranged ABB ACD EED). You may want to add this simple test case. \$\endgroup\$ – ETHproductions Nov 12 '16 at 1:57
5
\$\begingroup\$

C, 1135 1158 1231 1598 bytes

Well, it's past the stated deadline, but seeing as how there are no answers yet, here's one (a bit long) in C.

Returns:

  • 0 (zero) on failure (don't fit)
  • Full fitting matrix on success

Update:

Original code could get stuck on some matrices, taking much longer than the allowed 10s. Current revision should complete all matrices in under 1s. This is accomplished by 1) Sorting the input rectangles and 2) skipping repeated sizes when fitting.

Golfed:

#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct{int x,y,u,p;}r[25],*S;int A,M,N,U,V,X,Y;char *P;T(x,y,w,h){_(I,x+w,x)_(J,y+h,y)if(I/U|J/V|P[J*U+I])Z 0;Z 1;}L(x,y,w,h,c){_(I,x+w,x)_(J,y+h,y)P[J*U+I]=c;}F(){int x=0,y;while(++x<A)if(!P[x])break;if(x/A){_(i,V,0)printf("%*.*s\n",U,U,P+i*U);exit(0);}y=x/U;x-=y*U;_(i,N,0)if(!R.u&T(x,y,R.x,R.y))R.u=1,L(x,y,R.x,R.y,'A'+i),F(),R.u=0,L(x,y,R.x,R.y,0);}O(i,y){if(!R.u){if(!T(0,y,R.x,R.y))Z;R.u=1;R.p=0;L(0,y,R.x,R.y,'A'+i);y+=R.y;}if(y-V||F())_(j,N,0)if(j-i&!r[j].u){O(j,y);while(r[j].x-r[j+1].x|r[j].y-r[j+1].y)j++;}R.u=0;L(R.p,(y-=R.y),R.x,R.y,0);}Q(i,x){if(!R.u){if(R.x>U-x)Z;R.u=1;R.p=x;L(x,0,R.x,R.y,'A'+i);x+=R.x;}if(x-U||O(i,1))_(j,N,0)if(j-i&!r[j].u)Q(j,x);L(x-=R.x,0,R.x,R.y,0);R.u=0;}C(int*a,int*b){Z*a-*b?*a-*b:a[1]-b[1];}main(){_(i,25,0)if(++N&scanf("%d%d\n",&R.x,&R.y)-2)break;_(i,N,0){A+=R.x*R.y;if(R.x>X)X=R.x;if(R.y>Y)Y=R.y;}_(i,A+1,1)if(!(A%i)){if(i<Y|A/i<X)continue;M++;S=realloc(S,M*16);S[M-1].y=i;S[M-1].x=A/i;}qsort(S,M,16,C);P=calloc(A+1,1);_(j,M,0){U=S[j].x;V=S[j].y;_(i,N,0)R.u=1,L(0,0,R.x,R.y,'A'+i),Q(i,R.x),R.u=0;}printf("0\n");exit(1);}

UnGolfed:

#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct {
    int x,y,u,p;
} r[25],*S;
int A,M,N,U,V,X,Y;
char *P;

test_space(x,y,w,h) {
    _(I,x+w,x)
        _(J,y+h,y)
            if (    I >= U |
                    J >= V |
                    P[J*U+I]) Z 0;
    Z 1;
}
place_rect(x,y,w,h,c){
    _(I,x+w,x)
        _(J,y+h,y)P[J*U+I] = c;
}

fill_rest() {
    int x=0,y;
    while(++x<A) if (!P[x])break;
    if (x>=A) {
        _(i,V,0) printf("%*.*s\n", U,U, P+i*U);
        exit(0);
    }
    y = x / U; x -= y*U;

    _(i,N,0)
        if (!R.u & test_space(x, y, R.x, R.y))
                R.u = 1,
                place_rect(x, y, R.x, R.y, 'A'+i),
                fill_rest(),
                R.u = 0,
                place_rect(x, y, R.x, R.y, 0);

}

fill_y(i,y) {
    if (!R.u) {
        if (!test_space(0, y, R.x, R.y)) Z;
        R.u = 1;
        R.p = 0;
        place_rect(0, y, R.x, R.y, 'A'+i);
        y += R.y;
    }
    if (y == V) fill_rest();
    else _(j,N,0)
        if (j!=i && !r[j].u){ fill_y(j, y);
        while (r[j].x^r[j+1].x||r[j].y^r[j+1].y)j++;
        }
    R.u = 0;
    place_rect(R.p, (y -= R.y), R.x, R.y, 0);
}

fill_x(i,x) {
    if (!R.u) {
        if (R.x > U - x) Z;
        R.u = 1;
        R.p = x;
        place_rect(x, 0, R.x, R.y, 'A'+i);
        x += R.x;
    }
    if (x == U) fill_y(i, 1);
    else
        _(j,N,0)
            if (j!=i && !r[j].u) fill_x(j, x);
    place_rect((x -= R.x), 0, R.x, R.y, 0);
    R.u = 0;
}
C(int*a,int*b) {
    Z *a^*b?*a-*b:a[1]-b[1];
}


main() {
    _(i,25,0)
        if (++N&&scanf("%d %d\n", &R.x, &R.y)!=2) break;
    _(i,N,0){
        A+=R.x*R.y;
        if(R.x>X)X=R.x;
        if(R.y>Y)Y=R.y;
    }
    _(i,A+1,1)
        if (!(A%i)) {
            if (i < Y | A/i < X) continue;
            M++;
            S = realloc(S,M*16);
            S[M-1].y=i;
            S[M-1].x=A/i;
        }
    qsort(S, M, 16,C);
    P = calloc(A + 1,1);
    _(j,M,0){
        U = S[j].x; V = S[j].y;
        _(i,N,0)
            R.u = 1,
            place_rect(0, 0, R.x, R.y, 'A'+i),
            fill_x(i, R.x),
            R.u = 0;
    }
    printf("0\n");
    exit(1);
}

Explanation: We have 6 functions: main, O, Q, F, L and T. T tests to see if there is space for the rectangle at a given spot. L fills a rectangle into the output buffer or, alternately removes one by overwriting it. O and Q build up the left and top walls, respectively and F fills the remainder of the rectangle by iterative search.

Although the basic search is iterative, we eliminate the vast majority of possible search vectors, first by building up the allowed combinations of width and height for the master rectangle and then eliminating impossible configurations. Additional speed could be gained in larger rectangles by determining bottom and right walls prior to filling the center but it is not required for decent speed when limiting to 25 interior rectangles.

\$\endgroup\$
  • \$\begingroup\$ Nice job! It appears to be working... However, could you specify your output format? It appears that it's printing stuff if it works and crashing if it doesn't, which I'll permit since this is the only answer anyway. Also, you can save quite a few bytes by printing "1" instead of "Everybody fits!" (because that's allowed), and also quite a few bytes by not printing how they're arranged. It's nice to have that printed, but it uses unnecessary bytes, and the purpose is to save on that. Otherwise, good job! I'm extending the deadline by half a month, but for now, have an upvote. :) \$\endgroup\$ – HyperNeutrino Jan 3 '17 at 16:06
  • \$\begingroup\$ Thanks. I updated to specify the format and fixed the crash (that was unintentional). I left the matrix output (+30bytes) because it's nifty and if someone else posts a golf-language solution, they won't just be beating me by 30 :) \$\endgroup\$ – Seth Jan 3 '17 at 19:59
  • \$\begingroup\$ -367 bytes... Possibly the largest golf ever? :-) \$\endgroup\$ – HyperNeutrino Jan 3 '17 at 22:33
  • \$\begingroup\$ :-) Well, it helps to have a hack-y starting point. \$\endgroup\$ – Seth Jan 4 '17 at 0:40
  • \$\begingroup\$ Sure does! My largest golf was 337 characters in Java over several edits, and I started out with some pretty terrible ideas (oh, the good old days when I would create 50 million variables and only need 2...). Anyway, I'll keep waiting for answers, but it looks like this may be the only working one! \$\endgroup\$ – HyperNeutrino Jan 4 '17 at 21:45
6
+100
\$\begingroup\$

Haskell, 226 bytes

((y,z):l)&(w,x)|x*y<1=(w+y,x+z):l
(q:l)&p=p:q:l
(p@(u,v):r@(y,z):l)%q@(w,x)=[((y-w,z):l)&q&(u,v-x)|w<=y,x<=v]++[p:m|m<-(r:l)%q]
_%_=[]
g m(p:n)l=any(g[]$m++n)(l%p)||g(p:m)n l
g[]_[_,_,_]=0<1
g _[]_=0<0
($[(0,9^9),(9^9,0)]).g[]

Try it on Ideone

How it works

This recursively searches for all partial tilings whose shape is a Young diagram, adding one rectangle at a time, and checks whether any of the final results are rectangles.

To see that any tiling of a rectangle can be built this way: in any tiling of a nonempty Young diagram, let R be the set of rectangles in the tiling whose southwest corner does not touch any other rectangle. Since each concave vertex of the Young diagram is edge-adjacent (not merely corner-adjacent) to at most one rectangle in R, and the number of these concave vertices is one less than the number of rectangles in R, there must be at least one rectangle in R that is edge-adjacent to none of these concave vertices. Removing it yields another Young diagram, so we can proceed by induction.

\$\endgroup\$
  • \$\begingroup\$ Nice one! This is fantastic. Good job! :) \$\endgroup\$ – HyperNeutrino Jun 8 '17 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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