Können diese Rechtecke einen rechteckigen Raum ausfüllen?

Bei einer Reihe von Rechtecken werden Sie gefragt, ob sie so angeordnet werden können, dass sie einen rechteckigen Raum ausfüllen.

Technische Daten

Angesichts einer Reihe von willkürlichen m x nRechtecken; 0 <= m, n <= 1000Bestimmen Sie, ob es möglich ist, sie so anzuordnen, dass sie genau einen rechteckigen Bereich ohne Löcher oder Überlappungen abdecken. Die Rechtecke können nicht gedreht werden und jedes Rechteck darf nur einmal platziert werden.

Eingang

Die Eingabe hierfür ist sehr flexibel, solange die Eingabe eine Liste von Dimensionen mit zwei Räumen enthält. Zum Beispiel sind beide der folgenden Bedingungen gültig:

Durch Leerzeichen getrennt, Rückkehr

1 2
1 5
4 5
3 6

Liste der Abmessungen

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

Ausgabe

Jede Art von wahr / falsch-Werten wie wahr / falsch, 0/1, T / F, wahr / falsch usw. Wenn Sie eine Ausgabemethode verwenden möchten, die nicht sehr offensichtlich ist, geben Sie dies bitte in Ihrer Antwort an.

Beispiele

Testfall 1

Eingang:

1 1
1 5
2 6

Ausgabe: true(oder ähnliches)
So arrangieren Sie es:

XYYYYY
ZZZZZZ
ZZZZZZ

Testfall 2

Eingang:

1 1
2 2

Ausgabe: false(oder ähnliches)
Erläuterung: Es wird offensichtlich, dass Sie nicht zwei Quadrate unterschiedlicher Größe anordnen und ihre Kanten in eine Linie bringen können.

Testfall 3

Eingang:

1 1
1 2
1 2
2 1
2 1

Ausgabe: true(oder ähnliches) So arrangieren Sie es:

AAB
DEB
DCC

Wie @ETHProductions hervorhob, können Sie für alle anderen Testfälle weiterhin Rechtecke mit einer gemeinsamen Kantenlänge kombinieren, bis Sie nur noch ein Rechteck haben. In diesem Testfall wird also nur der Code gebrochen, der diese Idee verwendet.

Testfall 4

Eingang:

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

Ausgabe: true(oder ähnliches)
So arrangieren Sie es:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Hinweis : Sie müssen nicht angeben, wie es angeordnet werden soll. Sie müssen nur bestimmen, ob es nicht angeordnet werden kann.

Das ist Codegolf, also gewinnt die kürzeste Antwort in Bytes! Ich akzeptiere die kürzeste Antwort ab dem 14. Januar, kann sie aber auch später einreichen, da ich immer noch upvotes geben kann! :)

Viel Spaß beim Golfen!

~ AL

PS Wenn Sie wissen, welches Tag auf dieses Problem angewendet werden soll, fügen Sie es bitte hinzu. Ich habe absolut keine Ahnung, was ich als anderes Tag als Code-Golf einsetzen soll.

BEARBEITEN : Ihr Programm sollte in der Lage sein, bis zu 25 Rechtecke in höchstens 10 Sekunden auf einem anständigen Computer zu verarbeiten (ich werde in dieser Regel recht flexibel sein).

EDIT : Ich habe die Einreichungsfrist bis zum letzten Tag des Jahres verlängert, aber ich bezweifle, dass ich bis dahin eine Antwort bekomme ...

EDIT : Ich habe die Einreichungsfrist um 2 Wochen verlängert. Wenn bis dahin keine weiteren Antworten eingehen, wird die aktuelle C-Antwort akzeptiert! :)

C 1135, 1158, 1231, 1598 Bytes

Nun, es ist nach der angegebenen Frist, aber da es noch keine Antworten gibt, ist hier eine (etwas lange) in C.

Kehrt zurück:

• 0 (null) bei Fehlschlag (passt nicht)
• Volle Matrix für den Erfolg

Aktualisieren:

Der ursprüngliche Code könnte auf einigen Matrizen hängen bleiben und viel länger als die zulässigen 10s dauern. Die aktuelle Revision sollte alle Matrizen in unter 1s vervollständigen. Dies wird erreicht durch 1) Sortieren der Eingaberechtecke und 2) Überspringen wiederholter Größen beim Anpassen.

Golf gespielt:

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

Erläuterung: Wir haben 6 Funktionen: main, O, Q, F, Lund T. T Es wird geprüft, ob an einer bestimmten Stelle Platz für das Rechteck ist. Lfil l s ein Rechteck in die Ausgangspuffer oder entfernt abwechselnd durch Überschreiben. Ound QAufbau die linke und die obere Wand nach oben, jeweils und F f Übel des Restes des Rechtecks , das durch iterative Suche.

Obwohl die grundlegende Suche iterativ ist, eliminieren wir die große Mehrheit der möglichen Suchvektoren, indem wir zuerst die zulässigen Kombinationen von Breite und Höhe für das Master-Rechteck aufbauen und dann unmögliche Konfigurationen eliminieren. Bei größeren Rechtecken könnte zusätzliche Geschwindigkeit erzielt werden, indem die untere und die rechte Wand vor dem Füllen der Mitte bestimmt werden. Bei einer Beschränkung auf 25 innere Rechtecke ist dies jedoch nicht erforderlich, um eine angemessene Geschwindigkeit zu erzielen.

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

Probieren Sie es auf Ideone

Wie es funktioniert

Dadurch wird rekursiv nach allen Teilkacheln gesucht, deren Form ein Young-Diagramm ist , wobei jeweils ein Rechteck hinzugefügt wird, und es wird geprüft, ob eines der Endergebnisse Rechtecke sind.

Um zu sehen, dass jede Kachelung eines Rechtecks ​​auf diese Weise erstellt werden kann: Bei jeder Kachelung eines nicht leeren Young-Diagramms sei R die Menge der Rechtecke in der Kachelung, deren südwestliche Ecke kein anderes Rechteck berührt. Da jeder konkave Scheitelpunkt des Young-Diagramms an höchstens ein Rechteck in R an einer Kante angrenzt (nicht nur an einer Ecke angrenzt) und die Anzahl dieser konkaven Scheitelpunkte um eins geringer ist als die Anzahl der Rechtecke in R, muss mindestens eine vorhanden sein ein Rechteck in R, das kantenbenachbart zu keinem dieser konkaven Scheitelpunkte ist. Wenn Sie es entfernen, erhalten Sie ein weiteres Young-Diagramm, sodass wir durch Induktion fortfahren können.