19
\$\begingroup\$

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).

\$\endgroup\$
10
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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!) \$\endgroup\$ – Jonathan Allan May 6 at 10:52
  • \$\begingroup\$ @JonathanAllan Thanks. :) Actually, I wonder if a%w<1 could be replaced with just 1. I'll have to double-check that later. \$\endgroup\$ – Arnauld May 6 at 11:12
0
\$\begingroup\$

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}])[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.

\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – msh210 May 7 at 18:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – ArBo May 7 at 18:24
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – ovs May 7 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.