Temukan area persegi panjang terkecil untuk berisi kotak ukuran hingga n

19

Ini adalah pertanyaan urutan dari tipe yang biasa, seperti yang diterapkan pada urutan OEIS A038666 . Yaitu, lakukan salah satu dari yang berikut:

  • Jangan terima atau masukan apa pun, dan keluaran A038666 sampai matinya panas alam semesta.
  • Terima bilangan bulat positif sebagai input, dan output th jangka A038666 atau pertama istilah. (Jika menggunakan - bukannya -indexing, maka tentu saja Anda juga harus output pada input.)nn0110

The th jangka A038666 adalah wilayah terkecil di antara empat persegi panjang yang berisi kotak tidak tumpang tindih dari ukuran jika Anda menggunakan -indexing.n1×1,2×2,n×n1

Contoh:

Persegi panjang area terkecil yang dapat berisi kuadrat non-overlapping dengan ukuran hingga memiliki dimensi :1×14×47×5

4 4 4 4 3 3 3
4 4 4 4 3 3 3
4 4 4 4 3 3 3
4 4 4 4 2 2 1
x x x x 2 2 x

Oleh karena itu, ( -indexed).a(4)=7×5=351

Demikian pula, persegi panjang area terkecil yang berisi kuadrat non-tumpang tindih ukuran hingga memiliki dimensi , jadi ( -indexed).1×117×17 39×46a(17)=39×46=17941

msh210
sumber

Jawaban:

10

JavaScript (ES6), 172 byte

Saran versi yang lebih lambat tetapi lebih pendek disarankan oleh @JonathanAllan (juga menyimpan 4 byte dalam jawaban asli):

f=(n,A,S=(n,c)=>n>=0?c(n)||S(n-1,c):0)=>S(A,w=>(F=(l,n)=>n?S(w-n,x=>S(A/w-n,y=>l.some(([X,Y,W])=>X<x+n&X+W>x&Y<y+n&Y+W>y)?0:F([...l,[x,y,n]],n-1))):A%w<1)([],n))?A:f(n,-~A)

Cobalah online!


Jawaban asli,  209 183 178  174 byte

Pengembalian yang N th jangka urutan, 1-diindeks.

f=(n,A,S=(n,c)=>n>=0?c(n)||S(n-1,c):0)=>S(A,w=>A%w?0:(F=(l,n)=>n?S(w-n,x=>S(A/w-n,y=>l.some(([X,Y,W])=>X<x+n&X+W>x&Y<y+n&Y+W>y)?0:F([...l,[x,y,n]],n-1))):1)([],n))?A:f(n,-~A)

Cobalah online!

Berkomentar

Fungsi pembantu

Kami pertama-tama menentukan fungsi pembantu S yang memanggil fungsi panggilan balik c untuk n ke 0 (keduanya termasuk) dan berhenti segera setelah panggilan mengembalikan nilai yang sebenarnya.

S = (n, c) =>               // n = integer, c = callback function
  n >= 0 ?                  // if n is greater than or equal to 0:
    c(n) ||                 //   invoke c with n; stop if it's truthy
    S(n - 1, c)             //   or go on with n - 1 if it's falsy
  :                         // else:
    0                       //   stop recursion and return 0

Fungsi utama

Kita mulai dengan A=1 .

Untuk setiap pasangan (w,h) sedemikian rupa sehingga w×h=SEBUAH , kami mencoba untuk memasukkan semua kotak ukuran 1×1 ke n×n (sebenarnya dimulai dengan yang terbesar) di area yang sesuai, sedemikian rupa sehingga mereka jangan tumpang tindih satu sama lain.

Kami melacak daftar kotak dengan posisi mereka (X,Y) dan lebar W dalam l[ ] .

Kami akan mengembalikan SEBUAH jika pengaturan yang valid ditemukan, atau coba lagi dengan SEBUAH+1 .

f = ( n,                    // n = input
      A ) =>                // A = candidate area (initially undefined)
S(A, w =>                   // for w = A to w = 0:
  A % w ?                   //   if w is not a divisor of A:
    0                       //     do nothing
  : (                       //   else:
    F = (l, n) =>           //     F = recursive function taking a list l[] and a size n
      n ?                   //       if n is not equal to 0:
        S(w - n, x =>       //         for x = w - n to x = 0
          S(A / w - n, y => //           for y = A / w - n to y = 0:
            l.some(         //             for each square in l[]
            ([X, Y, W]) =>  //             located at (X, Y) and of width W:
              X < x + n &   //               test whether this square is overlapping
              X + W > x &   //               with the new square of width n that we're
              Y < y + n &   //               trying to insert at (x, y)
              Y + W > y     //
            ) ?             //             if some existing square does overlap:
              0             //               abort
            :               //             else:
              F([ ...l,     //               recursive call to F:
                  [x, y, n] //                 append the new square to l[]
                ],          //
                n - 1       //                 and decrement n
              )             //               end of recursive call
          )                 //           end of iteration over y
        )                   //         end of iteration over x
      :                     //       else (n = 0):
        1                   //         success: stop recursion and return 1
    )([], n)                //     initial call to F with an empty list of squares
) ?                         // end of iteration over w; if it was successful:
  A                         //   return A
:                           // else:
  f(n, -~A)                 //   try again with A + 1
Arnauld
sumber
2
Simpan 6 * dengan tidak mendefinisikan hdan memindahkan tes untuk a%w<1ke ujung TIO rekursi . Tentu saja ini jauh lebih lambat. (* setidaknya - saya bukan pakar JavaScript!)
Jonathan Allan
@ JonathanAllan Terima kasih. :) Sebenarnya, saya ingin tahu apakah a%w<1bisa diganti dengan adil 1. Saya harus mengeceknya nanti.
Arnauld
0

Python 2 (PyPy) , 250 236 byte

-14 byte berkat saran msh210 .

Menghasilkan istilah ke-1 yang diindeks dari urutan.

n=input()
r=range
k=n*-~n*(n-~n)/6
m=k*k
for Q in r(m):
 P={0}
 for X in r(n,0,-1):P|=([x for x in[{(x+a,y+b)for a in r(X)for b in r(X)}for x in r(Q%k-X+1)for y in r(Q/k-X+1)]if not x&P]+[{0}])[0]
 if len(P)>k:m=min(Q%k*(Q/k),m)
print m

Cobalah online! Untuk n> 4, ini membutuhkan banyak waktu. Saya telah memverifikasi hasilnya hingga n = 7 secara lokal.

ovs
sumber
Maukah Anda menyertakan penjelasan tentang cara kerjanya? Juga, saya bayangkan Anda dapat mencukur byte dengan membuat satu spasi pada satu waktu alih-alih tujuh (untuk lekukan kedua). (Sebenarnya, saya pikir mungkin dua forbaris bisa berada di satu baris, dan Anda hanya perlu membuat indentasi satu kali.)
msh210
1
@ msh210 "7 spasi" sebenarnya adalah sebuah tab, seperti pada Python 2 Anda dapat membuat indentasi pertama dengan spasi, kemudian dengan tab. Sayangnya, menempatkan kedua untuk loop pada satu baris akan menjadi sintaks yang tidak valid.
ArBo
1
@ msh210 Saya menemukan cara yang berbeda untuk menggabungkan mereka untuk loop. 7 ruang di mana hanya on line, terima kasih atas tangkapannya. Saya akan mencoba menulis penjelasan besok
ovs