Mengatur persegi panjang sewenang-wenang untuk mengisi ruang

26

Bisakah persegi panjang ini mengisi ruang persegi panjang?

Diberikan banyak persegi panjang, Anda ditanya apakah mereka dapat diatur untuk mengisi ruang persegi panjang atau tidak.

Spesifikasi

Diberikan sekelompok m x npersegi panjang sewenang-wenang ; 0 <= m, n <= 1000, tentukan apakah mungkin untuk mengaturnya sehingga mereka menutupi area persegi persis tanpa lubang atau tumpang tindih. Persegi panjang tidak dapat diputar, dan masing-masing persegi panjang hanya dapat ditempatkan satu kali.

Memasukkan

Input untuk ini sangat fleksibel, selama input memberikan semacam daftar dimensi 2-ruang. Misalnya, kedua hal berikut ini valid:

Dipisahkan oleh Space, Return

1 2
1 5
4 5
3 6

Daftar Dimensi

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

Keluaran

Semacam nilai true / false seperti true / false, 0/1, T / F, True / False, dll. Jika Anda akan menggunakan metode output yang tidak terlalu jelas, harap sebutkan dalam jawaban Anda.

Contohnya

Test Case 1

Memasukkan:

1 1
1 5
2 6

Output: true(atau yang serupa)
Bagaimana mengaturnya:

XYYYYY
ZZZZZZ
ZZZZZZ

Test Case 2

Memasukkan:

1 1
2 2

Keluaran: false(atau yang serupa)
Penjelasan: Menjadi jelas bahwa Anda tidak dapat mengatur dua kotak dengan ukuran yang berbeda dan membuat tepinya sejajar.

Test Case 3

Memasukkan:

1 1
1 2
1 2
2 1
2 1

Output: true(atau yang serupa) Bagaimana mengaturnya:

AAB
DEB
DCC

Seperti yang ditunjukkan oleh @ETHProductions, untuk semua kasus uji lainnya, Anda dapat terus menggabungkan persegi panjang dengan panjang tepi umum hingga Anda hanya memiliki satu persegi panjang, jadi kotak uji ini hanya untuk memecahkan kode yang menggunakan ide ini.

Test Case 4

Memasukkan:

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

Output: true(atau yang serupa)
Bagaimana mengaturnya:

AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

Catatan : Anda tidak perlu menyatakan bagaimana mengaturnya, Anda hanya perlu menentukan apakah tidak dapat diatur.

Ini adalah kode golf, jadi jawaban tersingkat dalam byte menang! Saya akan menerima jawaban terpendek pada 14 Januari, tetapi jangan ragu untuk mengirimkan jawaban lebih lambat dari itu karena saya masih bisa memberikan suara! :)

Selamat bermain golf!

~ AL

PS Jika Anda tahu tag apa yang harus diterapkan untuk masalah ini, silakan tambahkan, saya sama sekali tidak tahu apa yang harus dimasukkan sebagai tag selain kode-golf.

EDIT : Program Anda harus dapat memproses hingga 25 persegi panjang, dalam waktu paling lama 10 detik pada komputer yang layak (saya akan cukup fleksibel pada aturan ini).

EDIT : Saya telah memperpanjang batas waktu penerimaan pengiriman hingga hari terakhir tahun ini, tetapi saya ragu saya akan mendapatkan jawaban saat itu ...

EDIT : Saya telah memperpanjang batas waktu penerimaan pengiriman 2 minggu, jadi jika tidak ada lagi jawaban yang masuk saat itu, jawaban C saat ini akan diterima! :)

HyperNeutrino
sumber
Saya bawa setiap input persegi panjang hanya digunakan sekali?
xnor
7
Mengapa ada tenggat waktu? Anda dapat mengatakan bahwa Anda akan menerima jawaban pada saat itu, tetapi tantangan harus terbuka tanpa batas waktu :)
Nathan Merrill
4
Bisakah persegi panjang diputar?
xnor
3
Nah, masalah Anda adalah masalah decidability: "bisakah persegi berorientasi ini diatur untuk membentuk persegi panjang lain dengan 0 waste", yang merupakan masalah NP-complete (Korf, 2003: pdfs.semanticscholar.org/90a5/… ). Algoritma Korf pada dasarnya adalah brute-force dengan beberapa optimasi untuk lebih efisien menghilangkan konfigurasi tanpa solusi. Saya ragu golf ini akan di bawah 250 karakter dalam kebanyakan bahasa.
Gabriel Benamy
1
Rute yang mudah adalah menentukan apakah Anda dapat berulang kali menggabungkan dua persegi panjang dengan lebar atau tinggi yang sama hingga Anda memiliki 1 persegi panjang tersisa. Algoritma ini berfungsi untuk semua testcases saat ini; Namun, gagal untuk [[1, 2], [2, 1], [1, 1], [1, 2], [2, 1]](yang dapat diatur ABB ACD EED). Anda mungkin ingin menambahkan test case sederhana ini.
ETHproduksi

Jawaban:

5

C, 1135 1158 1231 1598 byte

Yah, ini sudah melewati batas waktu yang ditentukan, tetapi melihat bagaimana belum ada jawaban, inilah satu (agak panjang) di C.

Pengembalian:

  • 0 (nol) saat gagal (tidak cocok)
  • Matriks pemasangan penuh untuk kesuksesan

Memperbarui:

Kode asli bisa macet pada beberapa matriks, membutuhkan waktu lebih lama dari 10s yang diizinkan. Revisi saat ini harus menyelesaikan semua matriks di bawah 1s. Ini dilakukan dengan 1) Menyortir persegi panjang input dan 2) melewatkan ukuran berulang saat pemasangan.

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

Tidak Disatukan:

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

Penjelasan: Kami memiliki 6 fungsi: main, O, Q, F, Ldan T. T t EST untuk melihat apakah ada ruang untuk persegi panjang di tempat tertentu. Lfil l s persegi panjang ke output buffer atau, secara bergantian menghilangkan satu dengan Timpa. Odan Qmembangun dinding kiri dan atas, masing-masing dan F f penyakit sisa persegi panjang dengan pencarian berulang.

Meskipun pencarian dasar bersifat iteratif, kami menghilangkan sebagian besar kemungkinan vektor pencarian, pertama dengan membangun kombinasi lebar dan tinggi yang diizinkan untuk persegi panjang master dan kemudian menghilangkan konfigurasi yang tidak mungkin. Kecepatan tambahan dapat diperoleh dalam persegi panjang yang lebih besar dengan menentukan dinding bagian bawah dan kanan sebelum mengisi pusat tetapi tidak diperlukan untuk kecepatan yang layak ketika membatasi hingga 25 persegi panjang interior.

Seth
sumber
Pekerjaan yang baik! Tampaknya berfungsi ... Namun, dapatkah Anda menentukan format output Anda? Tampaknya itu mencetak barang jika berfungsi dan macet jika tidak, yang akan saya izinkan karena ini adalah satu-satunya jawaban. Anda juga dapat menyimpan beberapa byte dengan mencetak "1" alih-alih "Semua orang cocok!" (karena itu diperbolehkan), dan juga beberapa byte dengan tidak mencetak bagaimana mereka diatur. Sangat menyenangkan memiliki yang dicetak, tetapi menggunakan byte yang tidak perlu, dan tujuannya adalah untuk menghemat itu. Kalau tidak, kerja bagus! Saya memperpanjang tenggat waktu setengah bulan, tetapi untuk saat ini, ada upvote. :)
HyperNeutrino
Terima kasih. Saya memperbarui untuk menentukan format dan memperbaiki crash (itu tidak disengaja). Saya meninggalkan output matriks (+ 30bytes) karena bagus dan jika orang lain memposting solusi bahasa golf, mereka tidak akan hanya memukuli saya sampai 30 :)
Seth
-367 byte ... Mungkin golf terbesar yang pernah ada? :-)
HyperNeutrino
:-) Nah, ada gunanya memiliki titik awal hack-y.
Seth
Tentu saja! Golf terbesar saya adalah 337 karakter di Jawa selama beberapa pengeditan, dan saya mulai dengan beberapa ide yang cukup mengerikan (oh, masa lalu yang indah ketika saya akan membuat 50 juta variabel dan hanya perlu 2 ...). Ngomong-ngomong, aku akan terus menunggu jawaban, tapi sepertinya ini satu-satunya yang berfungsi!
HyperNeutrino
6

Haskell, 226 byte

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

Cobalah di Ideone

Bagaimana itu bekerja

Ini secara rekursif mencari semua kemiringan parsial yang bentuknya adalah diagram Young , menambahkan satu persegi panjang pada suatu waktu, dan memeriksa apakah salah satu hasil akhirnya adalah persegi panjang.

Untuk melihat bahwa setiap ubin persegi panjang dapat dibangun dengan cara ini: dalam setiap ubin diagram Young yang kosong, misalkan R adalah himpunan persegi panjang di ubin yang sudut barat dayanya tidak menyentuh persegi panjang lainnya. Karena setiap simpul cekung dari diagram Young adalah berbatasan-tepi (tidak hanya berbatasan sudut) dengan paling banyak satu persegi panjang di R, dan jumlah simpul cekung ini adalah satu kurang dari jumlah persegi panjang di R, harus ada setidaknya satu persegi panjang di R yang berbatasan dengan tidak ada dari simpul cekung ini. Menghapusnya menghasilkan diagram Young lain, sehingga kita dapat melanjutkan dengan induksi.

Anders Kaseorg
sumber
Yang bagus! Ini fantastis. Kerja bagus! :)
HyperNeutrino