# Bucket and Minimize

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$/extract_tex] 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 • Do we have to handle an empty \L\? – Adám Jan 23 '20 at 19:07 • Do we have to handle \N>|L|\? – Adám Jan 23 '20 at 19:07 • Ah, does the output have to be flat or is a list of list acceptable? – Jonathan Allan Jan 23 '20 at 20:46 • @JonathanAllan yes your output must be a flat list – scrawl Jan 24 '20 at 9:43 • @JonathanAllan non-positive test case added – scrawl Jan 24 '20 at 9:46 ## 16 Answers # APL (Dyalog Unicode), 40 bytesSBCS 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\$$ # 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  • "mould like chunk"... gotta love the jelly builtins – Jonah Jan 23 '20 at 20:24 # 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()  # J, 5250474239373532 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


# 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.

# 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.

• 47 bytes – Robin Ryder Jan 25 '20 at 22:49
• @RobinRyder thanks! – Giuseppe Jan 26 '20 at 1:14

# 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!

• I really like what you did with the walrus operator there! Do you think it makes sense for me to say that, in a way, you were able to use the := operator to stuff variable definitions inside the lambda expression? – RGS Jan 23 '20 at 23:43
• @RGS Yes, although since I needed x to be zero for the first use in the list comprehension I had to define it in the function's arguments. – Jonathan Allan Jan 23 '20 at 23:51
• sure. Very clever! – RGS Jan 23 '20 at 23:52

# 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";


# 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!

# 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.

# 05AB1E, 7 5 bytes

äεWδ,


-2 bytes thanks to @Grimmy.

Prints each of the integers on a separated line.

Outputting as a list would be 6 bytes instead:

äεWδ]˜


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)

• 5 bytes with vertical output: äεWδ= – Grimmy Jan 24 '20 at 16:46
• iirc one element per line is an allowed-by-default output method for lists, but just in case it isn't, here's 6 bytes with horizontal output, – Grimmy Jan 24 '20 at 16:58
• @Grimmy Ah, nice approach with =. I actually tried using the δ to create the list and get rid of the Duplicate, but couldn't really figure it out. I also had no idea using  δ] inside another map/loop would work like that. o.Ô That's pretty interesting. – Kevin Cruijssen Jan 24 '20 at 17:33

# 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

• You can narrow down the bug to rotoring with a Seq of Seqs. Try it online! – Jo King Jan 30 '20 at 9:18
• @JoKing Thanks, I've updated the bug. – SirBogman Jan 30 '20 at 17:26

# 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,tdivn,w+1,tmodn*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
,listSizedivn                  -- w
,widthLastBlocks+1               -- v
,listSizemodn*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]

• Welcome to the site. Nice to see Haskell. where is rarely the answer though. Here you can use bindings inside of a guard. e.g. l%n|t<-length l,w<-div t n=.... – Wheat Wizard Jan 28 '20 at 0:48
• @PostRockGarfHunter thank you, that's great, but how do I deal with o/sublist, since it's defined upon w and g? I tried that and had some erros saying that these variables were not in scope. – Leonardo Moraes Jan 28 '20 at 15:58
• I've taken a bit of a look and to be honest I can't really read your code. Obviously that is not your fault it is golfed after all. It is just pretty different from most golfed code I see so I don't really have the instincts. I would suggest trying again from scratch keeping in mind that pattern guards are shorter than where and I think the result will be shorter, or even just keep it in mind for next time. But I am not sure how to transform your current code into pattern guards since I don't have a good grasp of it. – Wheat Wizard Jan 29 '20 at 1:19
• 151 bytes: Rearranged things a bit more without fully understanding the code. Could probably golf more. Try it online! – SirBogman Jan 29 '20 at 5:32
• 145 bytes: l%n=map(minimum.o)[0..t-1]where(t,w,v,g,a)=(length l,tdivn,w+1,tmodn*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] Try it online Replaced |0<1=a[g+(i-g)&w..g+(i-g)&w+w-1] with |b<-g+(i-g)&w=a[b..b+w-1] – SirBogman Jan 29 '20 at 5:46

# 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!

• In Ruby 2.7 save one byte with ->l,n{a=b=0;l.chunk{b+=(a+=1)>(w=l.size)/n+(b<w%n ?1:0)?a=1:0}.flat_map{[_2.min]*_2.size}} – SirBogman Feb 2 '20 at 5:16

# 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

# 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.