Advent Challenge 7: Balance the storage carts!

Question

<< Prev Next >>

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!

Answer 1

Python 3, 533 494 476 bytes

from numpy import*
def o(a,v,t=[],n=1):
 if len(v)<1:return[[sum((d-e)**2for d,e in zip([sum(a)/sum(r)for a in zip(*[[a*k for k in b]for a,b in zip(r,t)])],[-~a/2 for a in a.shape]))**.5,a]]
 s,k=v[0],[[]]
 for p,i,j,l in[[copy(a),i,j,(i-~s/2,j-~s/2)]for i in range(a.shape[0]-s+1)for j in range(a.shape[1]-s+1)if all(a[i:i+s,j:j+s]<1)]:p[i:i+s,j:j+s]=n;k+=o(p,v[1:],t+[l],n+1)
 return k
w=input()
q,r=w[0],w[1:]
print(min([a for a in o(zeros(q),r)if a],key=lambda a:a[0])[1])

Try it online!

I used the numpy library in Python. It is a very popular Python library and it specializes matrix/multi-dimensional array manipulation.

Mine finds a different, but equally valid, solution. I did double check my work and, when I tried to find all solutions, it did find the one presented in the question as well.

Basic methodology is to bruteforce it. So, every possible present location is checked, then the one with the least distance between it's center of gravity and the center of the slay is returned (or at least one of the possible solutions).

---

Pseudo-Ungolfed Version

I figured providing the ungolfed version would help people understand the algorithm. I have made marginal improvements since this version, but this should give you a jump start in understanding it:

import numpy as np

with open("test.txt","w") as fo:
    input = lambda: [[3,4], 2, 1]

    def bruteForce(array, size, number):
        for i in range(array.shape[0]-size+1):
            for j in range(array.shape[1]-size+1):
                if np.all(array[i:i+size,j:j+size] == 0):
                    temp = np.copy(array)
                    temp[i:i+size,j:j+size] = number
                    yield temp, (i+(size+1)/2,j+(size+1)/2)
                    
    #y, x because of how numpy works
    #euclid = https://codegolf.stackexchange.com/a/70536/67929
    def recursiveCheck(array,presents,presentLocations=[],number=1,currentMin=[10000,[]]):
        global rest, size
        if (len(presents) == 0):
            centerI = sum(a*b[0] for a,b in zip(rest,presentLocations)) / sum(rest)
            centerJ = sum(a*b[1] for a,b in zip(rest,presentLocations)) / sum(rest)
            euclid = lambda a,b:sum((d-e)**2for d,e in zip(a,b))**.5
            centerDelta = euclid([centerI,centerJ],[(a+1)/2 for a in array.shape])
            if centerDelta <= currentMin[0]:
                currentMin[0] = centerDelta
                currentMin[1] = array
                fo.write(repr(array) + "\n")
                fo.write(repr(presentLocations) + "\n")
                fo.write(repr([centerI,centerJ]) + "\n")
                fo.write(repr(centerDelta) + "\n")
            return
        for potentialPresentArray, newPresentLocation in bruteForce(array,presents[0],number):
            recursiveCheck(potentialPresentArray,presents[1:],presentLocations+[newPresentLocation],number+1,currentMin)

    suMatrix = input()
    size = suMatrix[0]
    rest = suMatrix[1:]
    recursiveCheck(np.zeros(size),rest)

---

Credits

I used a response by CarpetPython to aide me in creating a euclidean distance calculation in a minimal amount of bytes.

Mr. Xcoder reduced it by 28 bytes.