Bucket and Minimize

Question

The challenge - given a numeric list L and an integer N as inputs, write a function that:

1. finds the bucket sizes for L such that it is split into N whole buckets of equal or near-equal size, and
2. returns for each element in L the minimum of that element's bucket.

Example -

L=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]  
N=5

Compute the bucket sizes with the following:

\$\left \lfloor \frac{| L |}{N} \right \rfloor + 1\$ elements go into \$|L| \bmod N\$ buckets, and

\$\left \lfloor \frac{| L |}{N} \right \rfloor \$ go into the rest,

where |L| is the length of L. For the above, we get

floor(12/5)+1 into 12 mod 5 buckets, and floor(12/5) in the rest:

[[0, 1, 2], [3, 4, 5], [6, 7], [8, 9], [10, 11]]

Finally, we output a list where each element is the minimum of its bucket:

[0, 0, 0, 3, 3, 3, 6, 6, 8, 8, 10, 10]

Some test cases:

In -> Out

[1, 2, 3, 4], 1 -> [1, 1, 1, 1]

[1, 2, 3, 4], 2 -> [1, 1, 3, 3]

[0, 2, 4, 6, 8], 3 -> [0, 0, 4, 4, 8]

[9, 3, 0, 1, 5, 7, 4, 6, 8, 10, 12, 11, 2, 13], 5 -> [0, 0, 0, 1, 1, 1, 4, 4, 4, 10, 10, 10, 2, 2]

[3, 0, -2, 0, -1], 2 -> [-2, -2, -2, -1, -1]

This is a code golf challenge. Shortest answer in bytes wins. Standard loopholes apply and such.

Edit:

1. you may assume L is not empty

2. you do not have to handle the case where N>|L|

3. your answer should return a flat list

Sandbox

Answer 1

APL (Dyalog Unicode), 40 bytes^SBCS

Anonymous infix lambda. Takes \$N\$ as left argument and \$L\$ as right argument.

{p/⌊/¨(-p)↑¨↑∘⍵¨+\p←1+@(⍳⍺|l)⌊⍺⍴⍺÷⍨l←≢⍵}

Try it online!

{…} \$⍺:=N,\ ⍵:=L\$

 l←≢⍵ \$l:=|L|\$

 ⍺÷⍨ \$l\over N\$

 ⍺⍴ \$(\underbrace{\frac{l}N,\frac{l}N,\frac{l}N,\cdots,\frac{l}N}_{N\text{ elements}})\$

 ⌊ \$(\underbrace{\left\lfloor\frac{l}N\right\rfloor,\left\lfloor\frac{l}N\right\rfloor,\left\lfloor\frac{l}N\right\rfloor,\cdots,\left\lfloor\frac{l}N\right\rfloor}_{N\text{ elements}})\$

 1+@(…) increment at the following indices:

  ⍺|l \$|L|\bmod N\$

  ⍳ \$(1,2,3,…,|L|\bmod N)\$

 p← \$p:=(\underbrace{\overbrace{1+\left\lfloor\frac{l}N\right\rfloor,1+\left\lfloor\frac{l}N\right\rfloor,\cdots,1+\left\lfloor\frac{l}N\right\rfloor}^{|L|\bmod N\text{ elements}},\left\lfloor\frac{l}N\right\rfloor,\left\lfloor\frac{l}N\right\rfloor,\cdots,\left\lfloor\frac{l}N\right\rfloor}_{|n|\bmod N\text{ elements}})\$

 +\ cumulative sum of that list

 ↑∘⍵¨ for each element, take that many elements from \$L\$

 (-p)↑¨ for each list, take as many trailing elements as the corresponding number in \$p\$

 ⌊/¨ minimum of each list

 p/ replicate each minimum by the the corresponding number in \$p\$

Answer 2

Jelly, 7 bytes

œsṂṁ$€F

A dyadic Link accepting L on the left and N on the right which yields a list as specified.

Try it online! Or see the test-suite.

(Also œsµṂṁ)F is the same.)

How?

œsṂṁ$€F - Link: list of order-able items, L; positive integer, N
œs      - split L into N chucks, longer ones to the left
     €  - for each chunk:
    $   -   last two links as a monad - i.e. f(chunk):
  Ṃ     -     minimum of chunk
   ṁ    -     mould like chunk
      F - flatten

Answer 3

JavaScript (ES6),  101  87 bytes

Takes input as (array)(n).

a=>n=>a.map(w=_=>--w?m:m=Math.min(...a.slice(p,p+=w=L/n+(i++<L%n)|0)),L=a.length,i=p=0)

Try it online!

How?

Variables

• \$L\$ is the length of the input array
• \$i\$ is the ID of the current bucket
• \$w\$ is the width of the current bucket
• \$m\$ is the minimum value in the current bucket
• \$p\$ is a pointer to the starting point of the next bucket

Commented

a => n =>                     // given the input array a[] and the integer n
  a.map(w =                   // initialize w to a non-numeric value
  _ =>                        // for each value in a[]:
    --w ?                     //   decrement w; if it's not equal to 0:
      m                       //     append the current minimum
    :                         //   else:
      m =                     //     append the updated value of m
        Math.min(             //       which is the minimum value found in
          ...a.slice(         //         the slice of a[]
            p,                //           starting at p
            p +=              //           and ending at the updated value of p (-1):
              w =             //             update w:
                L / n +       //               floor(L / n) is the base width
                (i++ < L % n) //               add 1 if i is less than L mod n
                              //               (then increment i)
                | 0           //               apply the floor()
          )                   //         end of slice()
        ),                    //       end of Math.min()
    L = a.length,             //   initialize L
    i = p = 0                 //   start with i = p = 0
  )                           // end of map()

Answer 4

J, ^{52 50 47 42 39 37 35 32} 27 bytes

](]#(<.//.~I.))[:+/-@[]\]=]

Try it online!

This solution doesn't use any of the arithmetic formulas. Instead it relies on geometric transformations.

We'll use the example

5 f 0 1 2 3 4 5 6 7 8 9 10 11

to see how the transformations work:

• ]=] Does the input equal itself, elementwise? This converts the input to ones:

  1 1 1 1 1 1 1 1 1 1 1 1
  

• -@[]\ Split it into rows whose size is 5 (the left arg), filling the final partial row with zeros:

  1 1 1 1 1
  1 1 1 1 1
  1 1 0 0 0
  

• [:+/ Sum the rows:

  3 3 2 2 2
  

• ] (...(...)) <above result> Execute the verb in parens with that result (3 3 2 2 2) as the right arg, and the original list ] as the left arg. Now we'll break down the verb in inner parens first...

• <.//.~I. This is a dyadic hook which first transforms the right arg 3 3 2 2 2 using I., which duplicates the indexes in place according to the multiplier at each index. Thus I. 3 3 2 2 2 gives:

  0 0 0 1 1 1 2 2 3 3 4 4          
  

• <.//.~ Use this mask to group /.~ the implicit left arg (the original list):

  0 0 0  1 1 1  2 2  3 3  4  4  <-- Mask
  0 1 2  3 4 5  6 7  8 9  10 11 <-- Original List
  

• <./ Returning the min of each group:

  0 3 6 8 10
  

• ]#( ... ) Returning to the verb in outer parens: Make right arg ] (ie, 3 3 2 2 2) copies of # the result of the verb in the inner parens. Thus: make 3 copies of the min of the first group, 3 copies of the min of the 2nd group, 2 copies of the min of the third group, etc:

  0 0 0 3 3 3 6 6 8 8 10 10
  

Answer 5

Pyth, 8 bytes

smLhSdcF

Try it online!

This answer is mostly straightforward in that c provides the appropriate splitting behaviour. After that, we map twice to each element of the inner list the element of that list which is minimal. The interesting part is performing this double map: mLhSd expands into mmhSdd.

Answer 6

R, 52 47 bytes

function(L,n)ave(L,sort(seq(0,a=L)%%n),FUN=min)

Try it online!

ave replaces each member of a group with the value provided by FUN applied to that group; the rest is just figuring out the groups.

Thanks to Robin Ryder for -5 bytes.

Answer 7

Python 3.8, 90 bytes

lambda L,N,x=0:sum([(w:=len(L)//N+(v<len(L)%N))*[min(L[x:(x:=x+w)])]for v in range(N)],[])

Try it online!

Answer 8

CJam, 25 bytes

q~\_,@d/m]/{_,\[:e<]*}%e_

Try it online!

Explanation

q~                         "Read whole input & eval";
  \                        "Swap the splitted-items down";
   _                       "Copy the list";
    ,                      "Find its length";
     @                     "Roll the 3rd-to-top on top";
      d                    "Convert the number to double";
       /                   "Divide them (resulting in a float)";
        m]                 "Find the ceiling of that number";
          /                "Divide the list into that many chunks";
           {         }%    "Map every item in that list";
            _,\            "Preserve the length of the list";
                :e<        "e< doesn't take a single list, so";
                           "we have to reduce by minimum";
               [   ]       "Turn this result into a list";
                    *      "Repeat the list that many times";
                       ]   "Put the result into a list";
                        e_ "Flatten the list";

Answer 9

Python, 118 bytes

def f(L,N):l=len(L);s=l//N;m=l%N;return sum([[min(L[s*i+i*(m>0):s*i+s+i*(m>0)+(i<m)])]*(s+(i<m))for i in range(N)],[])

Try it online!

Answer 10

Charcoal, 21 bytes

Ｆη⊞υＥ÷Ｌθ⁻ηι⊟θＦ⮌υＩＥι⌊ι

Try it online! Link is to verbose version of code. Explanation:

Ｆη

Loop from N down to 1.

⊞υＥ÷Ｌθ⁻ηι⊟θ

Remove the last |L|/N elements of L and add them to a separate list.

Ｆ⮌υＩＥι⌊ι

Reverse the secondary list to restore the elements to their original order, but map each to their minimum before implicitly printing them on separate lines.

Answer 11

05AB1E, 7 5 bytes

äεWδ,

-2 bytes thanks to @Grimmy.

Prints each of the integers on a separated line.

Try it online or verify all test cases.

Outputting as a list would be 6 bytes instead:

äεWδ]˜

Try it online or verify all test cases.

Explanation:

ä       # Split the (implicit) input-list into the (implicit) input-integer
        # amount of pieces, with smaller pieces at the left side if not all are equal
 ε      # Map each inner integer-list to:
  W     #  Push the minimum (without popping the list itself)
   δ    #  Using this minimum, apply to each value in the list:
    ,   #   Print (this minimum) with trailing newline

ä       # Split the (implicit) input-list into the (implicit) input-integer
        # amount of pieces, with smaller pieces at the left side if not all are equal
 ε      # Map each inner integer-list to:
  W     #  Push the minimum (without popping the list itself)
   δ    #  Using this minimum, apply to each value in the list:
    ]   #   Close both this double-vectorized apply-each, as well as the map itself,
        #   leaving the minimums in the inner lists after the apply-each is finished
     ˜  # Flatten this list of integer-lists
        # (after which the resulting list is output implicitly as result)

Answer 12

Perl 6 Raku, 66 65 63 59 bytes

-4 bytes thanks to Jo King.

{flat map {.min xx$_},@^m.rotor((1,0 X+@m/$^n)Zxx@m%$n,$n)}

Try it online!

This function causes an exception when first executed, but subsequently works. In previous versions of Rakudo, it always worked, and I have filed a Rakudo bug. Thanks for helping me find it.

Explanation

{                                                         } # anonymous function with parameters @m (array) and $n (bucket size)
                                       @m/$^n               # calculate bucket size: length(@m) / $n
                                (1,0 X+      )              # make a list consisting of 1 + bucket-size, bucket-size
                                                            # using the cross-product metaoperator X with operator +
                                              Zxx@m%$n,$n   # repeat (1 + bucket-size) length(@m) % $n times
                                                            # and repeat bucket-size $n times (* didn't work)
                                                            # using the zip metaoperator Z with operator xx
                      @^m.rotor(                         )  # take batches of those sizes from the list @m
      map {.min xx$_},  # replace each bucket with its minimum repeated by its length
 flat                   # flatten the list

Previous version, 65 61 bytes

{$/=$^m/$^n;flat map {.min xx$_},$m.rotor(1+$/xx$m%$n,$/xx*)}

Try it online!

Explanation

{                                                           } # anonymous function with params $m (array) and $n (bucket size)
 $/=$^m/$^n;                                                  # calculate minimum bucket size $/
                                          1+$/xx$m%$n         # take (length of m)%n batches of size 1+$/
                                                     ,$/xx*   # and then as many batches of size $/ as possible
                                 $m.rotor(                 )  # from the list $m
                 map {.min xx$_},                             # replace each bucket with its minimum repeated by its length
            flat                                              # flatten the list

Answer 13

Haskell, 158 145 bytes

Thank you @SirBogman and @PostRockGarfHunter for saving 13 bytes and for the great tip

Please feel free to improve it.

l%n=map(minimum.o)[0..t-1]where(t,w,v,g,a)=(length l,t`div`n,w+1,t`mod`n*v,map(l!!));n&b=div n b*b;o i|i<g=a[i&v..i&v+w]|b<-g+(i-g)&w=a[b..b+w-1]

Explanation

list % n=
  map
  (minimum . sublist)
  [0..listSize - 1]
  where
    (listSize, widthLastBlocks, widthFirstBlocks, lengthFirstBlocks, indecesToElem)=
      (length l                        -- t
      ,listSize`div`n                  -- w
      ,widthLastBlocks+1               -- v
      ,listSize`mod`n*widthFirstBlocks -- g
      ,map(list!!))                    -- a

    n & b = div n b * b -- bigest multiple of b smaller than n

    sublist i           -- o
      |i < lengthFirstBlocks =
        indecesToElem [i & widthFirstBlocks
                       ..
                       i&widthFirstBlocks + widthFirstBlocks - 1]
      |b <- lenghtFirstBlocks + (i - lengthFirstBlocks) & widthLastBlocks =
        indecesToElem [b..b + widthLastBlocks - 1]

Answer 14

Ruby, 91 77 bytes

->l,n{(0..z=l.size).flat_map{|x|(k=l.slice!(0,z/n+(z%n>x ?1:0))).map{k.min}}}

Try it online!

Answer 15

C (clang), 107 105 bytes

Z,x,y,i,m;f(*a,z,n){for(x=z%n,Z=z/n;m=*a,y=Z,z;a+=y)for(z-=i=y+=x-->0;i--;)wmemset(a,m=a[i]<m?a[i]:m,y);}

Try it online!

Thanks to @ceilingcat for saving 2

Answer 16

Haskell, 116 bytes

p=replicate
[]&_=[]
f&(x:xs)=(p x$minimum$take x f)++(drop x f)&xs
f%n|(q,r)<-divMod(length f)n=f&((p r$q+1)++p n q)

Try it online!

The % operator is the bucket and minimize function, where f is the list and n is the bucket size. The & operator is a helper that repeats x times the minimum of the first x elements of the list f, where x is the head of the right parameter list. The sum of the right parameter list may be greater than the length of the left parameter list, but the left parameter list must be divided evenly.