# Find the area of the smallest rectangle to contain squares of sizes up to n

This is a sequence question of the usual type, as applied to OEIS sequence A038666. That is, do either of the following:

• Accept no or any input, and output A038666 until the heat death of the universe.
• Accept a positive integer as input, and output the $$\n\$$th term of A038666 or its first $$\n\$$ terms. (If using $$\0\$$- instead of $$\1\$$-indexing, then of course you also have to output 1 on 0 input.)

The $$\n\$$th term of A038666 is the least area among rectangles that contain non-overlapping squares of sizes $$\1\times1,2\times2,\dots n\times n\$$ if you're using $$\1\$$-indexing.

### Example:

The smallest-area rectangle which can contain non-overlapping squares of sizes $$\1\times1\$$ through $$\4\times4\$$ has dimensions $$\7\times5\$$:

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


Therefore, $$\a(4)=7\times5=35\$$ ($$\1\$$-indexed).

Similarly, the least-area rectangle containing non-overlapping squares of sizes $$\1\times1\$$ through $$\17\times17\$$ has dimensions $$\39\times46\$$, so $$\a(17)=39\times46=1794\$$ ($$\1\$$-indexed).

# JavaScript (ES6), 172 bytes

Slower but shorter version suggestion suggested by @JonathanAllan (also saving 4 bytes in the original answer):

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)


Try it online!

# Original answer,  209 183 178  174 bytes

Returns the $$\N\$$th term of the sequence, 1-indexed.

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)


Try it online!

## Commented

### Helper function

We first define a helper function $$\S\$$ which invokes a callback function $$\c\$$ for $$\n\$$ to $$\0\$$ (both included) and stops as soon as a call returns a truthy value.

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


### Main function

We start with $$\A=1\$$.

For each pair $$\(w,h)\$$ such that $$\w\times h = A\$$, we try to insert all squares of size $$\1\times1\$$ to $$\n\times n\$$ (actually starting with the largest one) in the corresponding area, in such a way that they don't overlap with each other.

We keep track of the list of squares with their position $$\(X,Y)\$$ and their width $$\W\$$ in $$\l[\text{ }]\$$.

We either return $$\A\$$ if a valid arrangement was found, or try again with $$\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

• Save 6* by not defining h and moving the test for a%w<1 to the tail of the recursion TIO. Of course it's much slower. (* at least - I'm no JavaScript expert!) May 6, 2019 at 10:52
• @JonathanAllan Thanks. :) Actually, I wonder if a%w<1 could be replaced with just 1. I'll have to double-check that later. May 6, 2019 at 11:12

# Python 2 (PyPy), 250 236 bytes

-14 bytes thanks to msh210's suggestions.

Outputs the 1-indexed nth term of the sequence.

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}])
if len(P)>k:m=min(Q%k*(Q/k),m)
print m


Try it online! For n>4, this takes lot of time. I have verified the result up to n=7 locally.

• Would you mind including an explanation of how it works? Also, I imagine you can shave bytes by indenting one space at a time instead of seven (for the second indentation). (In fact, I think maybe the two for lines can be on one line, and you only need to indent once.) May 7, 2019 at 18:16
• @msh210 the "7 spaces" are in fact a tab, as in Python 2 you can indent first with a space, then with a tab. Putting the two for loops on one line would be invalid syntax unfortunately.
– ArBo
May 7, 2019 at 18:24
• @msh210 I found a different way to combine those for loops. Those 7 spaces where only on line, thanks for the catch. I will try to write an explanation tomorrow
– ovs
May 7, 2019 at 18:40