Maximal Skittle Enjoyment

Question

You've been given a bag of Skittles. Everybody knows that in order to appreciate the different flavors the most, you need to rotate between the flavors.

Basics:

1. You can only eat 1 skittle at a time
2. The order that you eat your skittles must be periodic.
3. Each period cannot contain a particular flavor more than once.
4. Your bag only has so many skittles. You cannot eat more of a particular flavor of skittle than appears in your bag.
5. You want to eat as many skittles as you can (it may not always be possible)

Examples:

Lets say you start with 3 Red, 2 Blue, and 3 Green skittles:

R B G R B G R G       Invalid:  The last R must be followed by a B, not a G
R B G R B G R         Valid, but sub-optimal
R R R                 Valid, but sub-optimal
R G B R G B R G       Valid and optimal
G R B G R B G R       Also valid and optimal (there are multiple good solutions)

Input/Output

• You are passed a non-empty list of positive integers for the color counts. (The above example would be [3,2,3]).
• You need to return a list containing valid and optimal ordering.
• Instead of using colors, you will use the indices from input list. (The last example output above would be [2,0,1,2,0,1,2,0]).
• Your output may be 0-indexed or 1-indexed. My examples will be 0-indexed

Test Cases

1                          0
4                          0 0 0 0
4 1                        0 0 0 0
3 1                        0 1 0                   or  0 0 0
5 2 2                      0 1 2 0 1 2 0
2 3 5                      2 1 0 2 1 0 2 1         or  1 2 0 1 2 0 1 2
2 4 5                      2 1 2 1 2 1 2 1 2
3 4 5                      2 1 0 2 1 0 2 1 0 2 1   or  1 2 0 1 2 0 1 2 0 1 2
1 1 1 1 1 6                5 0 1 2 3 4 5           (lots of other solutions)
1 1 1 1 1 8                5 5 5 5 5 5 5 5
2 4 6 8                    3 2 1 3 2 1 3 2 1 3 2 1 3 2

This is a code-golf, so make your solutions as short as possible in your favorite language!

Answer 1

JavaScript (ES6), 177 175 bytes

a=>a.map((n,i)=>[n,l=i]).sort((a,b)=>a[0]-b[0]).reduce((P,x,i,a)=>(v=a.reduce((p,c,j)=>j<i?p:p+Math.min(c[0],x[0]+1),0))>m?[...Array(m=v)].map((_,k)=>a[l-k%(l+1-i)][1]):P,m=0)

Formatted and commented

a => a                              // given an array a:
.map((n, i) => [n, l = i])          // map it to [value, index] arrays / set l = length - 1
.sort((a, b) => a[0] - b[0])        // sort it by values in ascending order
.reduce((P, x, i, a) =>             // for each reference entry x at position i:
  (v = a.reduce((p, c, j) =>        //   for each entry c at position j:
    j < i ?                         //     if c is before x:
      p                             //       keep the previous sum (which is 0)
    :                               //     else:
      p + Math.min(c[0], x[0] + 1), //       add minimum(value[j], value[i] + 1)
    0                               //   initialize the sum at 0
  )) > m ?                          //   if the new sum v is better than our current best m:
    [...Array(m = v)].map((_, k) => //     update m to v and update the result to an array
      a[l - k % (l + 1 - i)][1]     //     of length m filled with indices picked repeatedly
    )                               //     between i and l
  :                                 //   else:
    P,                              //     keep the previous result
  m = 0                             // start with best score m = 0
)                                   // the final result is returned by the outer reduce()

Used formula

Below is a table showing how the formula F(i, j) = minimum(value[j], value[i] + 1) is working, here with i = 0 and the input [ 5, 2, 2 ].

This formula can be interpreted as follows: for each Skittle type, we can select no more than the number of the least available type plus one.

 j | Sorted    | value[j] | F(0, j) | Selected        | Output
   | input     |          |         | Skittles        | (starting from bottom left)
---+-----------+----------+---------+-----------------+-----------------------------
 0 | 2 2       |     2    |    2    | [2] [2]         | \
 1 | 1 1       |     2    |    2    | [1] [1]         |  > 0 1 2 0 1 2 0
 2 | 0 0 0 0 0 |     5    |    3    | [0] [0] [0] 0 0 | /

Test cases

let f =

a=>a.map((n,i)=>[n,l=i]).sort((a,b)=>a[0]-b[0]).reduce((P,x,i,a)=>(v=a.reduce((p,c,j)=>j<i?p:p+Math.min(c[0],x[0]+1),0))>m?[...Array(m=v)].map((_,k)=>a[l-k%(l+1-i)][1]):P,m=0)

console.log(JSON.stringify(f([ 1                ]))); // 0
console.log(JSON.stringify(f([ 4                ]))); // 0 0 0 0
console.log(JSON.stringify(f([ 4, 1             ]))); // 0 0 0 0
console.log(JSON.stringify(f([ 3, 1             ]))); // 0 1 0
console.log(JSON.stringify(f([ 5, 2, 2          ]))); // 0 2 1 0 2 1 0
console.log(JSON.stringify(f([ 2, 3, 5          ]))); // 2 1 0 2 1 0 2 1
console.log(JSON.stringify(f([ 2, 4, 5          ]))); // 2 1 2 1 2 1 2 1 2
console.log(JSON.stringify(f([ 3, 4, 5          ]))); // 2 1 0 2 1 0 2 1 0 2 1
console.log(JSON.stringify(f([ 1, 1, 1, 1, 1, 6 ]))); // 5 4 3 2 1 0 5
console.log(JSON.stringify(f([ 1, 1, 1, 1, 1, 8 ]))); // 5 5 5 5 5 5 5 5
console.log(JSON.stringify(f([ 2, 4, 6, 8       ]))); // 3 2 1 3 2 1 3 2 1 3 2 1 3 2

Answer 2

Jelly, 22 bytes

ċЀṢN
ỤṚ;\Ṛẋ"‘Ṣ$ḣ"ÇLÞṪ

1-based indexing.

Try it online!

How?

Repeats each prefix of the indexes sorted by value descending one more time than would be achievable with the given bag of skittles, then removes the final skittle or skittles from each of these as necessary to make them achievable, and returns the one with the most skittles.

The number that should be removed from one extra periodic repetition is just the number with the minimum count across that prefix.

ỤṚ;\Ṛẋ"‘Ṣ$ḣ"ÇLÞṪ - Main link                   e.g. [6,4,2,8]
Ụ                - grade up: sort indices by value  [3,2,1,4]
 Ṛ               - reverse                          [4,1,2,3]
   \             - cumulative reduce with
  ;              -     concatenation (get prefixes) [[4],[4,1],[4,1,2],[4,1,2,3]]
    Ṛ            - reverse                          [[4,1,2,3],[4,1,2],[4,1],[4]]
         $       - last two links as a monad
       ‘         -     increment                    [7,5,3,9]
        Ṣ        -     sort                         [3,5,7,9]
      "          - zip with
     ẋ           -     list repetition              [[4,1,2,3,4,1,2,3,4,1,2,3],[4,1,2,4,1,2,4,1,2,4,1,2,4,1,2],[4,1,4,1,4,1,4,1,4,1,4,1,4,1],[4,4,4,4,4,4,4,4,4]]
            Ç    - call last link (1) as a monad    [-1,-1,-1,-1]
          "      - zip with
           ḣ     - head list to (remove excess)     [[4,1,2,3,4,1,2,3,4,1,2],[4,1,2,4,1,2,4,1,2,4,1,2,4,1],[4,1,4,1,4,1,4,1,4,1,4,1,4],[4,4,4,4,4,4,4,4]]
              Þ  - sort by
             L   -     length                       [[4,4,4,4,4,4,4,4],[4,1,2,3,4,1,2,3,4,1,2],[4,1,4,1,4,1,4,1,4,1,4,1,4],[4,1,2,4,1,2,4,1,2,4,1,2,4,1]]
               Ṫ - tail                             [4,1,2,4,1,2,4,1,2,4,1,2,4,1]

ċЀṢN - Link 1: head amounts (negative of skittle excess of each N+1 repeated period)
   Ṣ  - sort                                        [2,4,6,8]
 Ѐ   - for each mapped over right argument
ċ     - count                                       [1,1,1,1]
    N - negate                                      [-1,-1,-1,-1]

Answer 3

Python3, 174 172 167 Bytes

Idea

Given e.g. 3 Red, 2 Blue, and 3 Green skittles one can arrange them in a grid, sorted by color and amount:

r g
r g b
r g b

If one tries to eat exactly i skittles, one can at least eat i*c skittles in total, where c is the number of skittles in the r-th column, e.g. for i=2 one can at least eat 6 skittles.

r g
# # #
# # #

The only thing left to do is count how many additional skittles can be eaten by an incomplete period.

Golfed

def f(a):
 r=range;f=m=0;s=r(len(a));b=sorted(zip(a,s))[::-1]
 for i in s:
  c=b[i][0];n=-~i*c+sum(c<e[0]for e in b)
  if n>m:f,m=i+1,n
 return[b[j%f][1]for j in r(m)]

Commented

def f(a):
    r = range;
    f = m = 0;                          - Some variables we need later on
    s = r(len(a));                      - Integers from 0 to (num_skittles - 1)
    b = sorted(zip(a,s))[::-1]          - Zip with s to remember initial order,
                                          then sort and reverse
    for i in s:
        c = b[i][0]
        n = (i+1)*c                     - If we attempt to eat i different skittles,
                                          we can surely eat (i+1)*c skittles.
          + sum(1 for e in b if e[0]>c) - The additional sum corresponds to an incomplete period.
        if n>m:                         - If a better way of eating skittles is found:
            f,m = i+1,n                 - update variables
    return [b[j%f][1] for j in r(m)]

Try it online!

Edit: Replaced (i+1) with -~i to save 2 bytes.

Edit: -5 bytes thanks to Dead Possum