3
\$\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\$
6
  • \$\begingroup\$ Can we assume that we always are able to give everyone a shirt? \$\endgroup\$ Feb 23, 2017 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\$
    – hyper-neutrino
    Feb 23, 2017 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, 2017 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\$
    – hyper-neutrino
    Feb 23, 2017 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, 2017 at 15:17

3 Answers 3

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\$
3
  • \$\begingroup\$ Can you provide a link to an online tester? Thanks. \$\endgroup\$
    – hyper-neutrino
    Feb 23, 2017 at 16:37
  • \$\begingroup\$ @AlexL.: Added. \$\endgroup\$
    – smls
    Feb 23, 2017 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\$
    – hyper-neutrino
    Feb 23, 2017 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\$
4
  • \$\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, 2017 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\$ Feb 24, 2017 at 13:39
  • \$\begingroup\$ @zgrep Yeah... I overlooked that this specification made D unnecessary, so a lot of of people exploited that... :D \$\endgroup\$
    – hyper-neutrino
    Feb 24, 2017 at 13:45
  • \$\begingroup\$ Good job, this works for all cases I provided and some edge cases! +1! \$\endgroup\$
    – hyper-neutrino
    Feb 24, 2017 at 13:46
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\$
7
  • \$\begingroup\$ Can you provide a link to an online test suite? I cannot get it to work. Thanks! \$\endgroup\$
    – hyper-neutrino
    Feb 23, 2017 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, 2017 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\$
    – hyper-neutrino
    Feb 23, 2017 at 23:40
  • \$\begingroup\$ @AlexL. The newer version is up along with links to interpreters. \$\endgroup\$
    – zgrep
    Feb 23, 2017 at 23:56
  • \$\begingroup\$ This appears to work for all test cases and some edge cases. Good job! \$\endgroup\$
    – hyper-neutrino
    Feb 24, 2017 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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