Układanie dowolnych prostokątów w celu wypełnienia przestrzeni

26

Czy te prostokąty mogą wypełnić prostokątną przestrzeń?

Biorąc pod uwagę wiele prostokątów, pytamy Cię, czy można je ustawić tak, aby wypełniały prostokątną przestrzeń.

Okular

Biorąc pod uwagę garść dowolnych m x nprostokątów; 0 <= m, n <= 1000, określ, czy można je ułożyć tak, aby pokrywały dokładnie prostokątny obszar bez żadnych otworów lub zakładek. Prostokąty nie mogą być obracane, a każdy prostokąt może być umieszczony tylko raz.

Wkład

Dane wejściowe w tym celu są bardzo elastyczne, o ile dane wejściowe dają jakąś listę wymiarów 2-przestrzeni. Na przykład oba poniższe są poprawne:

Rozdzielone spacją, Return

1 2
1 5
4 5
3 6

Lista wymiarów

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

Wydajność

Wszelkie wartości prawda / fałsz, takie jak prawda / fałsz, 0/1, T / F, prawda / fałsz itp. Jeśli zamierzasz użyć metody wyjściowej, która nie jest zbyt oczywista, proszę podać w swojej odpowiedzi.

Przykłady

Przypadek testowy 1

Wkład:

1 1
1 5
2 6

Wyjście: true(lub coś podobnego)
Jak to zorganizować:

XYYYYY
ZZZZZZ
ZZZZZZ

Przypadek testowy 2

Wkład:

1 1
2 2

Wyjście: false(lub coś podobnego)
Objaśnienie: Staje się oczywiste, że nie można ustawić dwóch kwadratów o różnych rozmiarach i ustawić ich krawędzi w jednej linii.

Przypadek testowy 3

Wkład:

1 1
1 2
1 2
2 1
2 1

Wyjście: true(lub coś podobnego) Jak to zorganizować:

AAB
DEB
DCC

Jak wskazano @ETHProductions, dla wszystkich pozostałych przypadków testowych możesz nadal łączyć prostokąty o wspólnej długości krawędzi, dopóki nie będziesz mieć tylko jednego prostokąta, więc ten przypadek testowy służy tylko do złamania kodu używającego tego pomysłu.

Przypadek testowy 4

Wkład:

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

Wyjście: true(lub coś podobnego)
Jak to zorganizować:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Uwaga : Nie musisz określać, jak to zaaranżować, musisz jedynie ustalić, czy nie można tego zaaranżować.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach! Przyjmę najkrótszą odpowiedź od 14 stycznia, ale nie krępuj się przesyłać odpowiedzi później, ponieważ wciąż mogę wyrazić opinię! :)

Miłej gry w golfa!

~ AL

PS Jeśli wiesz, jaki tag należy zastosować do tego problemu, proszę go dodać, absolutnie nie mam pojęcia, co umieścić jako tag inny niż kod-golf.

EDYCJA : Twój program powinien być w stanie przetworzyć do 25 prostokątów, najwyżej 10 sekund na przyzwoitym komputerze (będę dość elastyczny na tej zasadzie).

EDYCJA : Przedłużyłem termin przyjmowania zgłoszeń do ostatniego dnia roku, ale wątpię, czy do tego czasu otrzymam odpowiedź ...

EDYCJA : Przedłużyłem termin przyjmowania zgłoszeń o 2 tygodnie, więc jeśli do tego czasu nie otrzymają więcej odpowiedzi, aktualna odpowiedź C zostanie zaakceptowana! :)

HyperNeutrino
źródło
Rozumiem, że każdy prostokąt wejściowy może być użyty tylko raz?
xnor
7
Dlaczego jest termin? Można powiedzieć, że akceptujesz odpowiedź w tym czasie, ale wyzwania powinny być otwarte na czas nieokreślony :)
Nathan Merrill
4
Czy prostokąty można obracać?
xnor
3
Twój problem jest rozstrzygalny: „czy te zorientowane prostokąty można ułożyć w inny prostokąt bez 0 odpadów”, co stanowi problem NP-zupełny (Korf, 2003: pdfs.semanticscholar.org/90a5/… ). Algorytm Korfa jest w zasadzie brutalną siłą z pewnymi optymalizacjami, aby bardziej efektywnie eliminować konfiguracje bez rozwiązania. Wątpię, czy golf tego miałby mniej niż 250 znaków w większości języków.
Gabriel Benamy,
1
Łatwą drogą byłoby ustalenie, czy można wielokrotnie łączyć dwa prostokąty o tej samej szerokości lub wysokości, aż pozostanie 1 prostokąt. Ten algorytm działa dla wszystkich bieżących przypadków testowych; jednak się nie udaje [[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]](co można ustawić ABB ACD EED). Możesz dodać ten prosty przypadek testowy.
ETHprodukcje

Odpowiedzi:

5

C, 1135 1158 1231 1598 bajtów

Cóż, minął wyznaczony termin, ale widząc, jak nie ma jeszcze odpowiedzi, oto jedna (nieco długa) w C.

Zwroty:

  • 0 (zero) w przypadku awarii (nie pasuje)
  • Pełna matryca sukcesu

Aktualizacja:

Oryginalny kod może utknąć na niektórych matrycach, co zajmuje znacznie dłużej niż dozwolone 10s. Obecna wersja powinna uzupełnić wszystkie macierze poniżej 1s. Odbywa się to poprzez 1) sortowanie prostokątów wejściowych i 2) pomijanie powtarzających się rozmiarów podczas dopasowywania.

Gra w golfa:

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

Objaśnienie: Mamy 6 funkcji: main, O, Q, F, Li T. T t EST aby sprawdzić, czy nie ma miejsca dla prostokąta w danym miejscu. Lfil l s prostokąta w buforze wyjściowym, lub alternatywnie usunięcie jednego przez nadpisanie. Oi Qtworzyć na lewo i do góry ścian, odpowiednio, i F f bolączki resztę prostokąt iteracyjnego.

Chociaż podstawowe wyszukiwanie jest iteracyjne, eliminujemy zdecydowaną większość możliwych wektorów wyszukiwania, najpierw poprzez utworzenie dozwolonych kombinacji szerokości i wysokości dla głównego prostokąta, a następnie wyeliminowanie niemożliwych konfiguracji. Dodatkową prędkość można uzyskać w większych prostokątach, określając dolne i prawe ściany przed wypełnieniem środka, ale nie jest to wymagane do przyzwoitej prędkości przy ograniczeniu do 25 wewnętrznych prostokątów.

Seth
źródło
Dobra robota! Wygląda na to, że działa ... Czy możesz jednak określić format wyjściowy? Wygląda na to, że drukuje rzeczy, jeśli działa, a awarie, jeśli nie, na co pozwolę, ponieważ i tak jest to jedyna odpowiedź. Możesz także zaoszczędzić sporo bajtów, drukując „1” zamiast „Wszyscy pasują!” (ponieważ jest to dozwolone), a także sporo bajtów, nie drukując ich rozmieszczenia. Miło jest mieć to wydrukowane, ale zużywa niepotrzebne bajty, a celem jest zaoszczędzenie na tym. W przeciwnym razie dobra robota! Przedłużyłem termin o pół miesiąca, ale na razie mam opinię. :)
HyperNeutrino,
Dzięki. Zaktualizowałem, aby określić format i naprawiłem awarię (było to niezamierzone). Zostawiłem wynik macierzy (+ 30 bajtów), ponieważ jest fajny i jeśli ktoś inny opublikuje rozwiązanie w języku golfowym, nie pobije mnie tylko o 30 :)
Seth
-367 bajtów ... Prawdopodobnie największy golf w historii? :-)
HyperNeutrino
:-) Cóż, pomaga mieć punkt wyjścia hack-y.
Seth
Jasne, że tak! Mój największy golf miał 337 znaków w Javie w kilku edycjach i zacząłem od całkiem okropnych pomysłów (och, stare dobre czasy, kiedy tworzyłem 50 milionów zmiennych i potrzebowałem tylko 2 ...). W każdym razie będę czekał na odpowiedzi, ale wygląda na to, że to może być jedyna działająca!
HyperNeutrino
6

Haskell, 226 bajtów

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

Wypróbuj na Ideone

Jak to działa

Rekurencyjnie wyszukuje wszystkie częściowe nachylenia, których kształt jest diagramem Younga , dodając jeden prostokąt na raz i sprawdza, czy którykolwiek z końcowych wyników jest prostokątami.

Aby zobaczyć, że dowolne kafelki prostokąta można zbudować w ten sposób: na dowolnym kafelku niepustego diagramu Younga niech R będzie zbiorem prostokątów w kafelku, którego południowy zachód nie dotyka żadnego innego prostokąta. Ponieważ każdy wklęsły wierzchołek diagramu Younga przylega do krawędzi (nie tylko do rogu) do co najwyżej jednego prostokąta w R, a liczba tych wklęsłych wierzchołków jest o jeden mniejsza niż liczba prostokątów w R, musi być co najmniej jeden prostokąt w R, który przylega do krawędzi do żadnego z tych wklęsłych wierzchołków. Usunięcie go daje kolejny schemat Younga, więc możemy przejść przez indukcję.

Anders Kaseorg
źródło
Niezłe! To jest fantastyczne. Dobra robota! :)
HyperNeutrino