Find the area of the smallest rectangle to contain squares of sizes up to nFind Possible Word RectanglesSquarefinder – Locating regular tetragonsCover a Region with RectanglesRemove an unobstructed rectangleDetermine the Dimensions of a Rotated RectangleMondrian Puzzle SequenceRectangular differenceVisualize Inclusion-ExclusionTrapped Knight SequencePatience, young “Padovan”

Can you turn a recording upside-down?

Using wilcox.test() and t.test() in R yielding different p-values

Renting a house to a graduate student in my department

Why valarray so slow on VS2015?

I might have messed up in the 'Future Work' section of my thesis

Does STATISTICS IO output include Version Store reads?

How to get MAX value using SOQL when there are more than 50,000 rows

What replaces x86 intrinsics for C when Apple ditches Intel CPUs for their own chips?

What happens when the drag force exceeds the weight of an object falling into earth?

Does Thread.yield() do anything if we have enough processors to service all threads?

What's the difference between "ricochet" and "bounce"?

Lorentz invariance of Maxwell's equations in matter

What is the Ancient One's mistake?

Can a planet still function with a damaged moon?

Double underlining a result in a system of equations with calculation steps on the right side

Why are thrust reversers not used to slow down to taxi speeds?

Why is there a cap on 401k contributions?

TeX Gyre Pagella Math Integral sign much too small

Why did they wait for Quill to arrive?

My perfect evil overlord plan... or is it?

How long can fsck take on a 30 TB volume?

Compactness in normed vector spaces.

Passport stamps art, can it be done?

Ugin's Conjurant vs. un-preventable damage



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


Find Possible Word RectanglesSquarefinder – Locating regular tetragonsCover a Region with RectanglesRemove an unobstructed rectangleDetermine the Dimensions of a Rotated RectangleMondrian Puzzle SequenceRectangular differenceVisualize Inclusion-ExclusionTrapped Knight SequencePatience, young “Padovan”













17












$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 $1times1,2times2,dots ntimes n$ if you're using $1$-indexing.



Example:



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



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)=7times5=35$ ($1$-indexed).



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












share|improve this question











$endgroup$
















    17












    $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 $1times1,2times2,dots ntimes n$ if you're using $1$-indexing.



    Example:



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



    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)=7times5=35$ ($1$-indexed).



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












    share|improve this question











    $endgroup$














      17












      17








      17


      1



      $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 $1times1,2times2,dots ntimes n$ if you're using $1$-indexing.



      Example:



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



      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)=7times5=35$ ($1$-indexed).



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












      share|improve this question











      $endgroup$




      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 $1times1,2times2,dots ntimes n$ if you're using $1$-indexing.



      Example:



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



      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)=7times5=35$ ($1$-indexed).



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









      code-golf packing






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 2 days ago







      msh210

















      asked May 5 at 20:14









      msh210msh210

      2,4521232




      2,4521232




















          2 Answers
          2






          active

          oldest

          votes


















          9












          $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 $wtimes h = A$, we try to insert all squares of size $1times1$ to $ntimes 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





          share|improve this answer











          $endgroup$








          • 1




            $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
            2 days ago










          • $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
            2 days ago


















          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.






          share|improve this answer











          $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
            yesterday






          • 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
            yesterday






          • 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
            yesterday











          Your Answer






          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "200"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185221%2ffind-the-area-of-the-smallest-rectangle-to-contain-squares-of-sizes-up-to-n%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          9












          $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 $wtimes h = A$, we try to insert all squares of size $1times1$ to $ntimes 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





          share|improve this answer











          $endgroup$








          • 1




            $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
            2 days ago










          • $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
            2 days ago















          9












          $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 $wtimes h = A$, we try to insert all squares of size $1times1$ to $ntimes 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





          share|improve this answer











          $endgroup$








          • 1




            $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
            2 days ago










          • $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
            2 days ago













          9












          9








          9





          $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 $wtimes h = A$, we try to insert all squares of size $1times1$ to $ntimes 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





          share|improve this answer











          $endgroup$



          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 $wtimes h = A$, we try to insert all squares of size $1times1$ to $ntimes 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






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited 2 days ago

























          answered May 5 at 23:48









          ArnauldArnauld

          83.2k798340




          83.2k798340







          • 1




            $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
            2 days ago










          • $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
            2 days ago












          • 1




            $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
            2 days ago










          • $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
            2 days ago







          1




          1




          $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
          2 days ago




          $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
          2 days ago












          $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
          2 days ago




          $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
          2 days ago











          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.






          share|improve this answer











          $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
            yesterday






          • 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
            yesterday






          • 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
            yesterday















          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.






          share|improve this answer











          $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
            yesterday






          • 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
            yesterday






          • 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
            yesterday













          0












          0








          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.






          share|improve this answer











          $endgroup$




          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.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited yesterday

























          answered yesterday









          ovsovs

          19.7k21161




          19.7k21161











          • $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
            yesterday






          • 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
            yesterday






          • 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
            yesterday
















          • $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
            yesterday






          • 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
            yesterday






          • 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
            yesterday















          $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
          yesterday




          $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
          yesterday




          1




          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
          yesterday




          $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
          yesterday




          1




          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
          yesterday




          $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
          yesterday

















          draft saved

          draft discarded
















































          If this is an answer to a challenge…



          • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


          • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
            Explanations of your answer make it more interesting to read and are very much encouraged.


          • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.


          More generally…



          • …Please make sure to answer the question and provide sufficient detail.


          • …Avoid asking for help, clarification or responding to other answers (use comments instead).




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f185221%2ffind-the-area-of-the-smallest-rectangle-to-contain-squares-of-sizes-up-to-n%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Category:9 (number) SubcategoriesMedia in category "9 (number)"Navigation menuUpload mediaGND ID: 4485639-8Library of Congress authority ID: sh85091979ReasonatorScholiaStatistics

          Circuit construction for execution of conditional statements using least significant bitHow are two different registers being used as “control”?How exactly is the stated composite state of the two registers being produced using the $R_zz$ controlled rotations?Efficiently performing controlled rotations in HHLWould this quantum algorithm implementation work?How to prepare a superposed states of odd integers from $1$ to $sqrtN$?Why is this implementation of the order finding algorithm not working?Circuit construction for Hamiltonian simulationHow can I invert the least significant bit of a certain term of a superposed state?Implementing an oracleImplementing a controlled sum operation

          Magento 2 “No Payment Methods” in Admin New OrderHow to integrate Paypal Express Checkout with the Magento APIMagento 1.5 - Sales > Order > edit order and shipping methods disappearAuto Invoice Check/Money Order Payment methodAdd more simple payment methods?Shipping methods not showingWhat should I do to change payment methods if changing the configuration has no effects?1.9 - No Payment Methods showing upMy Payment Methods not Showing for downloadable/virtual product when checkout?Magento2 API to access internal payment methodHow to call an existing payment methods in the registration form?