Disposition de rectangles arbitraires pour remplir un espace

26

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

HyperNeutrino
la source
Je suppose que chaque rectangle d'entrée n'est utilisé qu'une seule fois?
2016
7
Pourquoi y a-t-il un délai? Vous pourriez dire que vous accepterez une réponse à ce moment-là, mais les défis devraient être ouverts indéfiniment :)
Nathan Merrill
4
Les rectangles peuvent-ils être tournés?
xnor
3
Eh bien, votre problème est un problème de décidabilité: "ces rectangles orientés peuvent-ils être arrangés pour former un autre rectangle avec 0 déchet", ce qui est un problème NP-complet (Korf, 2003: pdfs.semanticscholar.org/90a5/… ). L'algorithme de Korf est essentiellement une force brute avec quelques optimisations pour éliminer plus efficacement les configurations sans solution. Je doute qu'un golf de ce type soit inférieur à 250 caractères dans la plupart des langues.
Gabriel Benamy
1
L'itinéraire le plus simple serait de déterminer si vous pouvez combiner à plusieurs reprises deux rectangles de même largeur ou hauteur jusqu'à ce qu'il ne vous reste qu'un rectangle. Cet algorithme fonctionne pour toutes les testcases actuelles; cependant, il échoue [[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]](ce qui peut être organisé ABB ACD EED). Vous voudrez peut-être ajouter ce cas de test simple.
ETHproductions

Réponses:

5

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.

Seth
la source
Bon travail! Cela semble fonctionner ... Cependant, pourriez-vous spécifier votre format de sortie? Il semble que cela imprime des trucs si cela fonctionne et se bloque si ce n'est pas le cas, ce que je permettrai puisque c'est la seule réponse de toute façon. En outre, vous pouvez économiser plusieurs octets en imprimant "1" au lieu de "Tout le monde convient!" (parce que c'est autorisé), et aussi pas mal d'octets en n'imprimant pas comment ils sont organisés. C'est bien de l'avoir imprimé, mais il utilise des octets inutiles, et le but est d'économiser sur cela. Sinon, bon travail! Je prolonge la date limite d'un demi-mois, mais pour l'instant, j'ai un vote positif. :)
HyperNeutrino
Merci. J'ai mis à jour pour spécifier le format et corrigé le plantage (ce qui n'était pas intentionnel). J'ai quitté la sortie de la matrice (+ 30 octets) car c'est astucieux et si quelqu'un d'autre publie une solution en langue de golf, il ne me
Seth
-367 octets ... Peut-être le plus grand golf de tous les temps? :-)
HyperNeutrino
:-) Eh bien, il est utile d'avoir un point de départ hack-y.
Seth
Bien sûr! Mon plus grand golf était de 337 caractères en Java sur plusieurs éditions, et j'ai commencé avec des idées assez terribles (oh, le bon vieux temps où je créais 50 millions de variables et n'en avais besoin que de 2 ...). Quoi qu'il en soit, je vais continuer d'attendre des réponses, mais il semble que ce soit la seule qui fonctionne!
HyperNeutrino
6

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.

Anders Kaseorg
la source
Joli! C'est fantastique. Bon travail! :)
HyperNeutrino