Susun Kotak Berat

27

Anda memiliki banyak kotak yang berat dan Anda ingin menumpuknya dalam jumlah tumpukan paling sedikit. Masalahnya adalah Anda tidak bisa menumpuk lebih banyak kotak pada kotak daripada yang bisa didukung, jadi kotak yang lebih berat harus ada di bagian bawah tumpukan.

Tantangan

Input : Daftar bobot kotak, dalam satuan kg.

Keluaran : Daftar daftar yang menggambarkan tumpukan kotak. Ini harus menggunakan tumpukan paling sedikit untuk input. Untuk menjadi tumpukan yang valid, berat masing-masing kotak di tumpukan harus lebih besar dari atau sama dengan jumlah berat semua kotak di atasnya.

Contoh tumpukan yang valid

(Di urutan bawah ke atas)

  • [3]
  • [1, 1]
  • [3, 2, 1]
  • [4, 2, 1, 1]
  • [27, 17, 6, 3, 1]
  • [33, 32, 1]
  • [999, 888, 99, 11, 1]

Contoh tumpukan tidak valid

(Agar dari bawah ke atas)

  • [1, 2]
  • [3, 3, 3]
  • [5, 5, 1]
  • [999, 888, 777]
  • [4, 3, 2]
  • [4321, 3000, 1234, 321]

Contoh Kasus Uji

1

IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

2

IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

3

IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

4

IN: [8, 5, 8, 8, 1, 2]
OUT: [[8, 8], [8, 5, 2, 1]]

Aturan dan Asumsi

  • Aturan I / O standar dan celah terlarang berlaku
  • Gunakan format apa pun yang nyaman untuk I / O
    • Tumpukan dapat digambarkan dari atas ke bawah atau dari bawah ke atas, selama Anda konsisten.
    • Urutan tumpukan (bukan kotak di dalam tumpukan itu) tidak masalah.
    • Anda juga dapat mengambil kotak input sebagai daftar yang dipilih. Urutan tidak terlalu penting untuk input, asalkan masalah umum tidak diselesaikan dengan penyortiran itu sendiri.
  • Jika ada lebih dari satu konfigurasi tumpukan yang optimal, Anda dapat mengeluarkan salah satunya
  • Anda dapat berasumsi bahwa setidaknya ada satu kotak dan semua kotak memiliki berat setidaknya 1 kg
  • Anda harus mendukung bobot hingga 9.999 kg, minimal.
  • Anda harus mendukung hingga 9.999 kotak total, minimal.
  • Kotak dengan berat yang sama tidak dapat dibedakan, jadi tidak perlu membubuhi keterangan kotak mana yang digunakan.

Selamat bermain golf! Semoga berhasil!

Beefster
sumber
2
Bisakah kita mengambil beban dalam urutan terurut? (baik naik atau turun)
Arnauld
4
"Anda harus mendukung hingga 9.999 total kotak, paling tidak." Bagaimana "dukungan" ditafsirkan di sini? Apakah itu semata-mata berarti program harus dapat mengambil input sebesar itu, atau apakah itu berarti bahwa program harus benar-benar memberikan jawaban dalam jumlah waktu yang wajar? Jika ini yang terakhir, harus ada test case yang lebih besar disediakan.
Joel
1
[8, 8, 8, 5, 1][[8, 8], [8, 5, 1]]
Kasing
3
Atau bahkan lebih baik: [8, 5, 8, 8, 1, 2]->[[8, 8], [8, 5, 2, 1]]
Hiatsu
2
@Arnauld, karena kalau tidak itu akan menambahkan kode penyortiran yang tidak menarik untuk sebuah jawaban, saya akan mengatakan ya , Anda dapat menerima input dalam urutan yang diurutkan.
Beefster

Jawaban:

5

Jelly , 19 byte

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ

Cobalah online!

Jelas -3 terima kasih kepada Nick Kennedy ...

Atas ke bawah.

Penjelasan:

Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ  Arguments: S (e.g. [1, 2, 3, 4, 5])
Œ!                   Permutations (e.g. [..., [4, 1, 5, 2, 3], ...])
    €                Map link over left argument (e.g. [..., [..., [[4, 1], [5], [2, 3]], ...], ...])
  ŒṖ                  Partitions (e.g. [..., [[4, 1], [5], [2, 3]], ...])
     Ẏ               Concatenate elements (e.g. [..., ..., [[4, 1], [5], [2, 3]], ..., ...])
               Ƈ     Filter by link (e.g. [..., [[1, 3], [2], [4], [5]], ...])
              Ɗ       Create >=3-link monadic chain (e.g. [[1], [], [0]])
           €           Map link over left argument (e.g. [[1], [], [0]])
          Ʋ             Create >=4-link monadic chain (e.g. [1])
      Ṗ                  Remove last element (e.g. [4])
       Ä                 Cumulative sum (e.g. [4])
         Ḋ               [Get original argument] Remove first element (e.g. [1])
        >                Greater than (vectorizes) (e.g. [1])
            ¬          Logical NOT (vectorizes) (e.g. [[0], [], [1]])
             Ȧ         Check if non-empty and not containing zeroes after flattening (e.g. 0)
                 Þ   Sort by link (e.g. [[[1, 2, 3], [4, 5]], ..., [[5], [4], [3], [2], [1]]])
                L     Length (e.g. 4)
                  Ḣ  Pop first element (e.g. [[1, 2, 3], [4, 5]])
Erik the Outgolfer
sumber
Apakah ada peluang di versi yang kurang ringkas dengan penjelasan? Saya belajar banyak dari itu.
John Keates
1
@JohnKeates Menambahkan satu.
Erik the Outgolfer
5

JavaScript (Node.js),  139 122  116 byte

Mengharapkan input diurutkan dalam urutan menaik.

f=(A,s=[],[n,...a]=A,r)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:f(A,c,a,c[i]=[n,...b]))?S:r?0:f(A,[...s,[]]):S=s

Cobalah online!

Berkomentar

f = (                        // f is a recursive function taking:
  A,                         //   A[] = input array
  s = [],                    //   s[] = list of stacks, initially empty
  [n,                        //   n   = next weight to process
      ...a] = A,             //   a[] = array of remaining weights
  r                          //   r   = recursion flag
) =>                         //
  n ?                        // if n is defined:
    s.some((b, i,            //   for each stack b[] at position i in s[],
                  [...c]) => //   using c[] as a copy of s[]:
      n < eval(b.join`+`) ?  //     if n is not heavy enough to support all values in b[]:
        0                    //       abort
      :                      //     else:
        f(                   //       do a recursive call:
          A, c, a,           //         using A[], c[] and a[]
          c[i] = [n, ...b]   //         with n prepended to c[i]
        )                    //       end of recursive call
    ) ?                      //   end of some(); if successful:
      S                      //     return S[]
    :                        //   else:
      r ?                    //     if this is a recursive call:
        0                    //       do nothing
      :                      //     else:
        f(A, [...s, []])     //       try again with an additional stack
  :                          // else:
    S = s                    //   success: save the solution in S[]
Arnauld
sumber
2

Python 3.8 (pra-rilis) , 178 byte

f=lambda b,s=[[]]:(a for i in range(len(s))if b[0]>=sum(s[i])for a in f(b[1:],s[:i]+[[b[0]]+s[i]]+s[i+1:]+[[]]))if b else[s]
g=lambda a:(c:=sorted(f(a),key=len)[0])[:c.index([])]

Cobalah online!

Sekarang bekerja pada semua input yang mungkin. (Ini habis pada TIO dengan lebih dari sepuluh atau lebih kotak, tetapi menghitung jawaban yang benar)

Hiatsu
sumber
2
list(reversed(sorted(a)))dapat ditulis sorted(a)[::-1]untuk tujuan golf.
Joel
Anda akan berpikir saya akan tahu itu sekarang, terutama karena saya melakukan banyak pengindeksan lainnya. Terima kasih.
Hiatsu
Sama seperti komentar sampingan, jika bukan untuk bermain golf akan lebih baik tulis sorted(a, reverse=True)saja.
Joel