Arranging arbitrary rectangles to fill a space

Question

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

Answer 1

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.

Answer 2

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.