Organizar rectángulos arbitrarios para llenar un espacio

26

¿Pueden estos rectángulos llenar un espacio rectangular?

Dado un montón de rectángulos, se le pregunta si se pueden organizar o no para llenar un espacio rectangular.

Especificaciones

Dado un montón de m x nrectángulos arbitrarios ; 0 <= m, n <= 1000, determine si es posible o no organizarlos de modo que cubran exactamente un área rectangular sin agujeros ni superposiciones. Los rectángulos no se pueden girar, y cada rectángulo solo se puede colocar una vez.

Entrada

La entrada para esto es muy flexible, siempre que la entrada proporcione algún tipo de lista de dimensiones de 2 espacios. Por ejemplo, los dos siguientes son válidos:

Separado por espacio, retorno

1 2
1 5
4 5
3 6

Lista de dimensiones

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

Salida

Cualquier tipo de valores verdadero / falso como verdadero / falso, 0/1, T / F, Verdadero / Falso, etc. Si va a utilizar un método de salida que no sea muy obvio, especifique en su respuesta.

Ejemplos

Caso de prueba 1

Entrada:

1 1
1 5
2 6

Salida: true(o algo similar)
Cómo organizarlo:

XYYYYY
ZZZZZZ
ZZZZZZ

Caso de prueba 2

Entrada:

1 1
2 2

Salida: false(o algo similar)
Explicación: Resulta obvio que no puede organizar dos cuadrados de diferentes tamaños y alinear sus bordes.

Caso de prueba 3

Entrada:

1 1
1 2
1 2
2 1
2 1

Salida: true(o algo similar) Cómo organizarlo:

AAB
DEB
DCC

Como señaló @ETHProductions, para todos los demás casos de prueba, puede seguir combinando rectángulos con una longitud de borde común hasta que tenga solo un rectángulo, por lo que este caso de prueba es solo para romper cualquier código que use esta idea.

Caso de prueba 4

Entrada:

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

Salida: true(o algo similar)
Cómo organizarlo:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Nota : No necesita indicar cómo organizarlo, solo necesita determinar si no se puede organizar.

Este es el código de golf, por lo que gana la respuesta más corta en bytes. Aceptaré la respuesta más corta a partir del 14 de enero, ¡pero siéntase libre de enviar respuestas más tarde ya que todavía puedo dar votos a favor! :)

¡Feliz golf!

~ AL

PD: Si sabe qué etiqueta debe aplicarse a este problema, agréguela, no tengo absolutamente ninguna idea de qué poner como etiqueta, aparte de code-golf.

EDITAR : Su programa debería poder procesar hasta 25 rectángulos, en un máximo de 10 segundos en una computadora decente (seré bastante flexible en esta regla).

EDITAR : he extendido el plazo de aceptación de envío hasta el último día del año, pero dudo que obtenga una respuesta para entonces ...

EDITAR : he extendido el plazo de aceptación de envío en 2 semanas, por lo que si no hay más respuestas para entonces, ¡se aceptará la respuesta C actual! :)

Hiperneutrino
fuente
¿Supongo que cada rectángulo de entrada se usará solo una vez?
xnor
77
¿Por qué hay una fecha límite? Se podría decir que aceptará una respuesta en ese momento, pero los desafíos deben abrirse indefinidamente :)
Nathan Merrill
44
¿Se pueden girar los rectángulos?
xnor
3
Bueno, su problema es un problema de capacidad de decisión: "¿se pueden organizar estos rectángulos orientados para formar otro rectángulo con 0 residuos", que es un problema de NP completo (Korf, 2003: pdfs.semanticscholar.org/90a5/… ). El algoritmo de Korf es esencialmente una fuerza bruta con algunas optimizaciones para eliminar configuraciones de manera más eficiente sin solución. Dudo que un golf de este sea inferior a 250 caracteres en la mayoría de los idiomas.
Gabriel Benamy
1
La ruta fácil sería determinar si puede combinar repetidamente dos rectángulos del mismo ancho o alto hasta que le quede 1 rectángulo. Este algoritmo funciona para todos los casos de prueba actuales; sin embargo, falla [[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]](que se puede arreglar ABB ACD EED). Es posible que desee agregar este caso de prueba simple.
ETHproductions

Respuestas:

5

C, 1135 1158 1231 1598 bytes

Bueno, ya pasó la fecha límite establecida, pero viendo que todavía no hay respuestas, aquí hay una (un poco larga) en C.

Devoluciones:

  • 0 (cero) en caso de falla (no encaja)
  • Matriz de ajuste completo en el éxito

Actualizar:

El código original podría atascarse en algunas matrices, tomando mucho más tiempo que los 10 permitidos. La revisión actual debe completar todas las matrices en menos de 1s. Esto se logra al 1) Ordenar los rectángulos de entrada y 2) omitir los tamaños repetidos al ajustar.

Golfizado:

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

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

Explicación: Tenemos 6 funciones: main, O, Q, F, Ly T. T t EST para ver si hay espacio para el rectángulo en un punto dado. Lfil l es un rectángulo en el búfer de salida o, alternativamente elimina uno, sobreescribiendo. Oy Qconstruir las paredes izquierda y superior, respectivamente, y F f Males el resto del rectángulo de búsqueda iterativa.

Aunque la búsqueda básica es iterativa, eliminamos la gran mayoría de los posibles vectores de búsqueda, primero mediante la construcción de las combinaciones permitidas de ancho y alto para el rectángulo maestro y luego eliminando las configuraciones imposibles. Se podría ganar velocidad adicional en rectángulos más grandes determinando las paredes inferiores y derechas antes de llenar el centro, pero no se requiere una velocidad decente cuando se limita a 25 rectángulos interiores.

Seth
fuente
¡Buen trabajo! Parece estar funcionando ... Sin embargo, ¿podría especificar su formato de salida? Parece que está imprimiendo cosas si funciona y se bloquea si no funciona, lo que permitiré ya que esta es la única respuesta de todos modos. Además, puede guardar bastantes bytes imprimiendo "1" en lugar de "¡Todos caben!" (porque está permitido), y también unos pocos bytes al no imprimir cómo están organizados. Es bueno tener eso impreso, pero usa bytes innecesarios, y el propósito es ahorrar en eso. De lo contrario, buen trabajo! Estoy extendiendo la fecha límite por medio mes, pero por ahora, tenga un voto a favor. :)
HyperNeutrino
Gracias. Actualicé para especificar el formato y solucioné el bloqueo (que no fue intencional). Dejé la salida de la matriz (+ 30bytes) porque es ingeniosa y si alguien más publica una solución de lenguaje de golf, no me golpearán a los 30 :)
Seth
-367 bytes ... ¿Posiblemente el golf más grande de la historia? :-)
HyperNeutrino
:-) Bueno, ayuda tener un punto de partida para hackear.
Seth
¡Seguro que lo hace! Mi mayor campo de golf era 337 caracteres en Java en varias ediciones, y comencé con algunas ideas bastante terribles (oh, los viejos tiempos en los que creaba 50 millones de variables y solo necesitaba 2 ...) De todos modos, seguiré esperando respuestas, ¡pero parece que esta puede ser la única que funciona!
HyperNeutrino
6

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

Pruébalo en Ideone

Cómo funciona

Esto busca recursivamente todas las inclinaciones parciales cuya forma es un diagrama de Young , agregando un rectángulo a la vez, y verifica si alguno de los resultados finales son rectángulos.

Para ver que cualquier mosaico de un rectángulo se puede construir de esta manera: en cualquier mosaico de un diagrama de Young no vacío, sea R el conjunto de rectángulos en el mosaico cuya esquina suroeste no toca ningún otro rectángulo. Dado que cada vértice cóncavo del diagrama de Young es adyacente al borde (no simplemente adyacente a la esquina) como máximo a un rectángulo en R, y el número de estos vértices cóncavos es uno menos que el número de rectángulos en R, debe haber al menos un rectángulo en R que está adyacente al borde de ninguno de estos vértices cóncavos. Eliminarlo produce otro diagrama de Young, por lo que podemos proceder por inducción.

Anders Kaseorg
fuente
¡Buena esa! Esto es fantástico. ¡Buen trabajo! :)
HyperNeutrino