Give everyone T-Shirts

Question

You're in charge of distributing T-Shirts to everyone. Simple enough, right? But remember, there are different sizes of T-Shirts, and you have to keep that in mind...

Challenge Specifications

There are N T-Shirt sizes. There are K people. Each person may wear any T-Shirt that is larger than them, but they can only wear a T-Shirt that is D sizes down. You want to figure out what the optimal configuration is, based on the cost of the system. It is guaranteed that everyone will be able to get a T-Shirt, so you must give everyone a T-Shirt.

The cost is calculated as such:
Start from 0 and add up.
For every person who receives a T-Shirt, add |S1 - S2|, where the person is size S1 and they are receiving a T-Shirt of size S2.

Input Specifications

The input starts with the integers N, K, and D. You can choose to not input N or K if you want. These can be given in an array, one on each line, space separated, or pretty much anything you want, but they must be given in this order. You must specify how you want input.

Then, the next part of the input is N integers representing how many T-Shirts of each size there are. For example, with N := 3, [1, 4, 2] means that there is 1 size 1 T-Shirt, 4 size 2 T-Shirts, and 2 size 3 T-Shirt. It is guaranteed that the sum of these numbers equals K. This can be taken as an array, an array contained at the end of the first part of input, an array joined to the end of the first part of the input, one on each line, space separated, or some other one that does not put you at a clear advantage. Again, please specify how you want input.

Then, the next part of the input is K integers representing the individual size of each person. This order matters. This can be taken as an array, an array contained at the end of the first part of the input, etc.

You can also choose to start with size-0.

Output Specifications

Output must consist of K + 1 integers. The first K of these represents the size of T-Shirt given to each person, and the last integer is the overall cost. This can be outputted as an array, space-separated integers, one on each line, etc.

Test Cases

Input:

3 10 1
3 5 2
1 1 1 2 2 2 2 2 3 3

Output:

1 1 1 2 2 2 2 2 3 3 0

Explanation:

This one's an easy case; each person gets the size of T-Shirt matching them, so the overall cost is 0.

Input:

2 10 0
5 5
1 1 1 1 1 1 2 2 2 2

Output:

1 1 1 1 1 2 2 2 2 2 1 # Or 2 1 1 1 1 1 2 2 2 2, or similar outputs

Explanation:

There are 5 size-1 shirts, which are given to 5 of 6 size-1 people. There are 5 size-2 shirts, 4 of which are given to the 4 size-2 people. There is one more size-1 person and one more size-2 shirt, so this assignment is made at a cost of 1.

Input:

7 20 2
5 0 5 0 5 0 5
3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9

Output:

1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 40

Explanation:

At first glance, it may make sense to assign everyone the size of T-Shirt they need. However, then we get 5 size-9 people and 5 size-1 T-Shirts, and people can only wear shirts down 2 sizes, so we assign everyone a T-Shirt 2 sizes down, at a cost of 40.

This test case is also in place to address the possible confusion that you can output the shirt sizes sorted. This is not always the case, as shown in this test case.

This is a code-golf challenge, so the shortest valid submission by March 14th (Pi Day) wins!

Answer 1

Perl 6, 77 bytes

->$,\t,\p{flat(1..*Zxx t)[[p].&{@(.sort)=0..*;$_}].&{|$_,(p Z-$_)».abs.sum}}

Try it online!

Simply matches the n'th smallest T-Shirt to the person with the n'th smallest size.

I'm not absolutely sure if that is guaranteed to give the correct result for all possible inputs, but it works for the test-cases given in the task description.

---

Perl 6, 97 bytes

->\d,\t,\p{flat(1..*Zxx t).permutations.map({|$_,(p Z-$_)».&{$_>d??∞!!.abs}.sum}).min(*[*-1])}

Try it online!

Dumb brute-force solutions.
Takes around 15 minutes for the test-cases with 10 people, so the test-case with 20 people should only take, uh, millions of years... :D

(Memory usage should remain steady though, because permutations and map return lazy one-off sequences, and min also only needs to keep one element in memory.)

---

Both versions take three input arguments:

• The number D.
• The array for the T-Shirts.
• The array for the people.

Answer 2

Python 2, 121 119 115 106 bytes

def f(a,b):
 j=h=0
 for i in a:j+=1;exec"q=b.index(min(b));h+=abs(j-b[q]);b[q]=`j`;"*i
 print map(int,b),h

Try it Online!

Takes both lists, without N, K or D. Outputs a list of sizes, followed by the cost

Edit: I found a cool trick using exec that took off 9 bytes!

Answer 3

k, 47 44 35 25 bytes

Stealing from the Perl6 solution, it matches the smallest shirt to the smallest person it can.

It turns out, D is also unnecessary! This takes advantage of that. It takes in two lists as arguments.

{x,+/%y*y:y-x:(1+&x)@<<y}

Try it online!

Try it in oK.

Explanation:

{                       } /function(x,y)
                     <<y  /grade up the grade up of the people
                          /  returns indices needed to rearrange a list of shirts
              (1+&x)      /expand the list into a list of shirts
            x:      @     /x = rearrange shirts by said indices
          y-              /S1 - S2
     %y*y:                /absolute value
   +/                     /total to get the score
 x,                       /prepend the list of rearranged shirts