Saya punya beberapa buku dan rak buku. Saya ingin meletakkan sebanyak mungkin buku di rak, tetapi saya memiliki peraturan. Semua dimensi buku (tinggi, lebar, dan kedalaman) harus membentuk urutan yang tidak bertambah di rak.
Ini berarti setiap buku setidaknya harus setinggi buku setelahnya sendiri. Hal yang sama berlaku untuk lebar dan kedalaman. Anda tidak dapat memutar buku untuk menukar tinggi, lebar, dan dalamnya.
Anda harus menulis program atau fungsi yang memberikan dimensi semua buku sebagai input input atau mengembalikan jumlah maksimal buku yang bisa saya letakkan di rak.
Memasukkan
- Daftar kembar tiga bilangan bulat positif tempat setiap triplet menentukan tinggi, lebar, dan kedalaman buku.
- Setidaknya akan ada satu triplet dalam daftar input.
- Dua buku dapat memiliki panjang yang sama di sepanjang sejumlah dimensi.
Keluaran
- Satu bilangan bulat positif, jumlah maksimal buku yang muat di rak mematuhi aturan.
Kompleksitas waktu
Algoritme Anda harus memiliki polinomial kompleksitas waktu terburuk dalam jumlah buku. Ini berarti bahwa misalnya kompleksitas waktu berikut semuanya valid: O (N ^ 3), O (log (N) * N ^ 2), O (N) dan yang berikut ini tidak valid: O (2 ^ N), O (N!), O (N ^ N).
Contohnya
Input => Output
(1, 1, 1) => 1
(5, 2, 5), (1, 3, 5) => 1
(5, 2, 5), (1, 2, 5) => 2
(2, 2, 2), (2, 2, 2), (2, 2, 2), (1, 3, 6) => 3
(1, 2, 5), (1, 3, 5), (1, 2, 8), (1, 2, 5), (7, 7, 7) => 4
(5, 19, 3), (9, 4, 16), (15, 16, 13), (7, 4, 16), (1, 13, 14), (20, 1, 15), (9, 8, 19), (4, 11, 1) => 3
(1, 1, 18), (1, 13, 7), (14, 1, 17), (8, 15, 16), (18, 8, 12), (8, 8, 15), (10, 1, 14), (18, 4, 6), (10, 4, 11), (17, 14, 17), (7, 10, 10), (19, 16, 17), (13, 19, 2), (16, 8, 13), (14, 6, 12), (18, 12, 3) => 5
Ini adalah kode golf sehingga entri terpendek menang.
Tantangan penyortiran buku terkait yang menarik: Book Stack Sort .
sumber
Jawaban:
Python 3: 436 byte
Pada awalnya saya melihat ini sebagai masalah NP-lengkap untuk menemukan jalur sederhana terpanjang dalam grafik berarah dengan siklus. Namun, setiap siklus dalam grafik (sebenarnya subgraph lengkap) dapat direpresentasikan sebagai satu simpul. Dengan kata lain, perlakukan buku-buku identik sebagai satu buku, untuk ditempatkan di rak sebagai satu unit. Kita kemudian dapat membuat grafik asiklik terarah di mana a-> b berarti b dapat mengikuti a di rak. Akhirnya, kami menemukan ketinggian maksimum pohon keluar (s) menggunakan metode rekursif.
sumber
Pyth, 40 byte
Tidak cepat, tetapi jumlahnya banyak.
Setara Python3:
sumber
Python 2, 231 byte
Coba di sini
Program saya saat ini mendapatkan dua contoh terakhir yang salah. Bisakah seseorang membantu saya memperbaikinya? Terima kasih.
Saya mengurutkan semua daftar 6 kemungkinan permutasi dari 3 dimensi, kemudian melihat apa hubungan pemesanan terus menerus terpanjang dalam daftar, kemudian menemukan maks dari mereka.
Juga, saya tahu jika bisa bermain golf lebih banyak, tetapi saya tidak tahu apakah saya bisa menggunakannya
reduce
untuk melakukan ini. Sederhananya, cara ini adalah yang termudah untuk dilakukan dalam waktu yang wajar tanpa otak saya meledak.sumber