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 = A , 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 A + 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
h
dan memindahkan tes untuka%w<1
ke ujung TIO rekursi . Tentu saja ini jauh lebih lambat. (* setidaknya - saya bukan pakar JavaScript!)a%w<1
bisa diganti dengan adil1
. Saya harus mengeceknya nanti.Python 2 (PyPy) ,
250236 byte-14 byte berkat saran msh210 .
Menghasilkan istilah ke-1 yang diindeks dari urutan.
Cobalah online! Untuk n> 4, ini membutuhkan banyak waktu. Saya telah memverifikasi hasilnya hingga n = 7 secara lokal.
sumber
for
baris bisa berada di satu baris, dan Anda hanya perlu membuat indentasi satu kali.)