After some careful analysis, Santa was able to determine the dock size ranges and get the presents into the correct transportation dock.
Now, he needs you to help him balance out the transportation carts and place the presents in them in the most balanced fashion.
Challenge
You will be given the size of (the base of) the transportation cart as (width, height)
and a list of all of the presents' sizes as integers.
An arrangement of presents on the transportation cart will have a certain center of mass, which should be as close to the center as possible (in other words, you want to minimize the Euclidean Distance between the center of mass and (width / 2, height / 2)
. The center of mass can be calculated by the following formula.
Formula
Let {(x_1, y_1), (x_2, y_2), ..., (x_i, y_i)}
be the coordinates of the centers of the presents (these coordinates may be half-numbers (so #.5) if the
size is even). Let s = {s_1, s_2, ..., s_i}
be the sizes of the presents.
Then, the center of mass is at ((x_1 × s_1 + x_2 × s_2 + ... + x_i × s_i) / sum(s), (y_1 × s_1 + y_2 × s_2 + ... + y_i × s_i) / sum(s))
.
Task
Given the dimensions of the transportation cart m × n
and the sizes of the presents, determine the positions of the presents in the most balanced arrangement. Note that presents may not intersect; each present with size s
is an s × s × s
cube.
Formatting Specifications
You may give the output in any reasonable format; for example, the positions of the top-left corners of the presents, the centers, an m × n
matrix of integers indicating what present covers each space, etc. If there are multiple valid answers, you may return just one (does not have to be deterministic) or you can return them all.
Test Cases
Input
Output (given as the `m × n` matrix as ASCII-art)
----
5 × 5, 2, 2, 2, 2
11022 00220
11022 11220
00000 or 11033
33044 04433
33044 04400
----
5 × 7, 1, 1, 1, 2, 2
1000022
0000022
0003000 (or others)
4400000
4400005
----
3 × 4, 3
1110
1110
1110
---
3 × 4, 2, 1
0110
0110
0020
Please feel free to correct me if my test cases are not correct.
Rules
- Standard Loopholes Apply
- This is a code-golf, so the shortest answer in bytes wins
- No answer will be accepted
- There will always be at least one solution to all of the inputs
Note: I drew inspiration for this challenge series from Advent Of Code. I have no affiliation with this site
You can see a list of all challenges in the series by looking at the 'Linked' section of the first challenge here.
Happy Golfing!
s³
but masss
? So the presents probably looks like this? Poor kids... \$\endgroup\$s²
, nots
. Full box has masss³
. / Must presents be at integer coordinate? \$\endgroup\$