Ces rectangles peuvent-ils remplir un espace rectangulaire?

Étant donné un tas de rectangles, on vous demande s'ils peuvent être disposés ou non pour remplir un espace rectangulaire.

Spécifications

Étant donné un tas de m x nrectangles arbitraires ; 0 <= m, n <= 1000, déterminez s'il est possible ou non de les disposer de manière à couvrir exactement une zone rectangulaire sans trous ni chevauchements. Les rectangles ne peuvent pas être tournés et chaque rectangle ne peut être placé qu'une seule fois.

Contribution

L'entrée pour cela est très flexible, tant que l'entrée donne une sorte de liste de dimensions à 2 espaces. Par exemple, les deux éléments suivants sont valides:

Séparé par l'espace, retour

1 2
1 5
4 5
3 6

Liste des dimensions

[[1, 2], [1, 5], [4, 5], [3, 6]]

Sortie

Toutes sortes de valeurs vraies / fausses comme true / false, 0/1, T / F, True / False, etc. Si vous allez utiliser une méthode de sortie qui n'est pas très évidente, veuillez préciser dans votre réponse.

Exemples

Cas de test 1

Contribution:

1 1
1 5
2 6

Sortie: true(ou quelque chose de similaire)
Comment l'organiser:

XYYYYY
ZZZZZZ
ZZZZZZ

Cas de test 2

Contribution:

1 1
2 2

Sortie: false(ou quelque chose de similaire)
Explication: Il devient évident que vous ne pouvez pas disposer deux carrés de tailles différentes et aligner leurs bords.

Cas de test 3

Contribution:

1 1
1 2
1 2
2 1
2 1

Sortie: true(ou quelque chose de similaire) Comment l'organiser:

AAB
DEB
DCC

Comme l'a souligné @ETHProductions, pour tous les autres cas de test, vous pouvez continuer à combiner des rectangles avec une longueur de bord commune jusqu'à ce que vous n'ayez qu'un seul rectangle, donc ce cas de test est juste pour casser tout code qui utilise cette idée.

Cas de test 4

Contribution:

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

Sortie: true(ou quelque chose de similaire)
Comment l'organiser:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Remarque : Vous n'avez pas besoin d'indiquer comment l'organiser, il vous suffit de déterminer s'il ne peut pas être organisé.

C'est le golf de code, donc la réponse la plus courte en octets gagne! J'accepterai la réponse la plus courte à partir du 14 janvier, mais n'hésitez pas à soumettre des réponses plus tard car je peux encore donner des votes! :)

Bon golf!

~ AL

PS Si vous savez quelle balise doit être appliquée à ce problème, veuillez l'ajouter, je n'ai absolument aucune idée de ce qu'il faut mettre comme balise autre que code-golf.

EDIT : Votre programme devrait être capable de traiter jusqu'à 25 rectangles, en au plus 10 secondes sur un ordinateur décent (je serai assez flexible sur cette règle).

EDIT : J'ai prolongé la date limite d'acceptation des soumissions jusqu'au dernier jour de l'année, mais je doute que j'obtienne une réponse d'ici là ...

EDIT : J'ai prolongé le délai d'acceptation des soumissions de 2 semaines, donc si aucune autre réponse n'arrive d'ici là, la réponse C actuelle sera acceptée! :)

C, 1135 1158 1231 1598 octets

Eh bien, c'est passé la date limite indiquée, mais vu qu'il n'y a pas encore de réponse, en voici une (un peu longue) en C.

Résultats:

• 0 (zéro) en cas d'échec (ne correspond pas)
• Matrice complète sur le succès

Mise à jour:

Le code d'origine peut rester bloqué sur certaines matrices, ce qui prend beaucoup plus de temps que les 10 autorisées. La révision actuelle devrait compléter toutes les matrices en moins de 1s. Pour ce faire, 1) triez les rectangles d'entrée et 2) sautez les tailles répétées lors de l'ajustement.

Golfé:

#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);}

Non golfé:

#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);
}

Explication: Nous avons 6 fonctions: main, O, Q, F, Let T. T t ests pour voir s'il y a de la place pour le rectangle à un endroit donné. Lfil l s un rectangle dans le tampon de sortie ou, supprime alternativement un en le remplaçant. Oet Qaccumuler les parois gauche et en haut, respectivement , et F f maux du reste du rectangle par recherche itérative.

Bien que la recherche de base soit itérative, nous éliminons la grande majorité des vecteurs de recherche possibles, tout d'abord en créant les combinaisons autorisées de largeur et de hauteur pour le rectangle maître, puis en éliminant les configurations impossibles. Une vitesse supplémentaire pourrait être gagnée dans les grands rectangles en déterminant les parois inférieure et droite avant de remplir le centre, mais elle n'est pas requise pour une vitesse décente lors de la limitation à 25 rectangles intérieurs.

Haskell, 226 octets

((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[]

Essayez-le sur Ideone

Comment ça marche

Cela recherche récursivement tous les pavages partiels dont la forme est un diagramme de Young , en ajoutant un rectangle à la fois, et vérifie si l'un des résultats finaux sont des rectangles.

Pour voir que n'importe quel pavage d'un rectangle peut être construit de cette façon: dans tout pavage d'un diagramme Young non vide, soit R l'ensemble des rectangles du pavage dont le coin sud-ouest ne touche aucun autre rectangle. Étant donné que chaque sommet concave du diagramme d'Young est adjacent à un bord (et non simplement un coin adjacent) à au plus un rectangle dans R, et le nombre de ces sommets concaves est inférieur de un au nombre de rectangles dans R, il doit y avoir au moins un rectangle dans R qui n'est adjacent à aucun de ces sommets concaves. Le supprimer donne un autre diagramme de Young, nous pouvons donc procéder par induction.