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”
$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
on0
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
$endgroup$
add a comment |
$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
on0
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
$endgroup$
add a comment |
$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
on0
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
$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
on0
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
code-golf packing
edited 2 days ago
msh210
asked May 5 at 20:14
msh210msh210
2,4521232
2,4521232
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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
$endgroup$
1
$begingroup$
Save 6* by not definingh
and moving the test fora%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 ifa%w<1
could be replaced with just1
. I'll have to double-check that later.
$endgroup$
– Arnauld
2 days ago
add a comment |
$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 twofor
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
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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
$endgroup$
1
$begingroup$
Save 6* by not definingh
and moving the test fora%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 ifa%w<1
could be replaced with just1
. I'll have to double-check that later.
$endgroup$
– Arnauld
2 days ago
add a comment |
$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
$endgroup$
1
$begingroup$
Save 6* by not definingh
and moving the test fora%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 ifa%w<1
could be replaced with just1
. I'll have to double-check that later.
$endgroup$
– Arnauld
2 days ago
add a comment |
$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
$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
edited 2 days ago
answered May 5 at 23:48
ArnauldArnauld
83.2k798340
83.2k798340
1
$begingroup$
Save 6* by not definingh
and moving the test fora%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 ifa%w<1
could be replaced with just1
. I'll have to double-check that later.
$endgroup$
– Arnauld
2 days ago
add a comment |
1
$begingroup$
Save 6* by not definingh
and moving the test fora%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 ifa%w<1
could be replaced with just1
. 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
add a comment |
$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 twofor
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
add a comment |
$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 twofor
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
add a comment |
$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$
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.
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 twofor
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
add a comment |
$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 twofor
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
add a comment |
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).
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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