1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Can we assume that we always are able to give everyone a shirt? \$\endgroup\$ – fəˈnɛtɪk Feb 23 '17 at 14:25
  • \$\begingroup\$ It is guaranteed that everyone will be able to get a T-Shirt, so you must give everyone a T-Shirt. Yes. \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 14:33
  • \$\begingroup\$ Do we have to take the N and K parameters, even though they're just the lengths of the lines/arrays that follow? It may be necessary in a language like C in order to know how many elements to read from each array, but in languages where the sizes of arrays are known it's kinda awkward and redundant. \$\endgroup\$ – smls Feb 23 '17 at 14:44
  • \$\begingroup\$ @smls I guess, you can choose to omit them. Since there are no answers yet, I'll change that in the specs. Thanks for pointing that out. \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 15:06
  • \$\begingroup\$ Is the last array (size of each person) always sorted in ascending order? If so, is there any case where simply outputting the sorted list of available T-Shirts isn't the correct answer? \$\endgroup\$ – smls Feb 23 '17 at 15:17
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can you provide a link to an online test suite? I cannot get it to work. Thanks! \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 23:17
  • \$\begingroup\$ Unfortunately, it does not work in a publicly available interpreter (unless you send the creator an email and ask for a copy of the interpreter). However, I'm working on a shorter variant that does work in oK and it's almost finished! \$\endgroup\$ – zgrep Feb 23 '17 at 23:29
  • \$\begingroup\$ Alright. That's good! I tried testing it with the available interpreter, but unfortunately it doesn't work, so I'm looking forward to seeing your improved version! \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 23:40
  • \$\begingroup\$ @AlexL. The newer version is up along with links to interpreters. \$\endgroup\$ – zgrep Feb 23 '17 at 23:56
  • \$\begingroup\$ This appears to work for all test cases and some edge cases. Good job! \$\endgroup\$ – HyperNeutrino Feb 24 '17 at 0:04
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Can you provide a link to an online tester? Thanks. \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 16:37
  • \$\begingroup\$ @AlexL.: Added. \$\endgroup\$ – smls Feb 23 '17 at 20:15
  • \$\begingroup\$ This appears to work for all test cases and a few additional edge cases I came up with. Good job! \$\endgroup\$ – HyperNeutrino Feb 23 '17 at 20:20
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I thought D was necessary to allow people to wear smaller shirts, because there's always the possibility that the input is simply invalid... \$\endgroup\$ – zgrep Feb 24 '17 at 9:15
  • 2
    \$\begingroup\$ @zgrep It is guaranteed that everyone will be able to get a T-Shirt, so you must give everyone a T-Shirt \$\endgroup\$ – math junkie Feb 24 '17 at 13:39
  • \$\begingroup\$ @zgrep Yeah... I overlooked that this specification made D unnecessary, so a lot of of people exploited that... :D \$\endgroup\$ – HyperNeutrino Feb 24 '17 at 13:45
  • \$\begingroup\$ Good job, this works for all cases I provided and some edge cases! +1! \$\endgroup\$ – HyperNeutrino Feb 24 '17 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.