21
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Do we have to handle an empty \$L\$? \$\endgroup\$ – Adám Jan 23 at 19:07
  • 2
    \$\begingroup\$ Do we have to handle \$N>|L|\$? \$\endgroup\$ – Adám Jan 23 at 19:07
  • 1
    \$\begingroup\$ Ah, does the output have to be flat or is a list of list acceptable? \$\endgroup\$ – Jonathan Allan Jan 23 at 20:46
  • 2
    \$\begingroup\$ @JonathanAllan yes your output must be a flat list \$\endgroup\$ – scrawl Jan 24 at 9:43
  • 1
    \$\begingroup\$ @JonathanAllan non-positive test case added \$\endgroup\$ – scrawl Jan 24 at 9:46

16 Answers 16

6
\$\begingroup\$

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\$

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ "mould like chunk"... gotta love the jelly builtins \$\endgroup\$ – Jonah Jan 23 at 20:24
4
\$\begingroup\$

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()
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
    
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 47 bytes \$\endgroup\$ – Robin Ryder Jan 25 at 22:49
  • \$\begingroup\$ @RobinRyder thanks! \$\endgroup\$ – Giuseppe Jan 26 at 1:14
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – RGS Jan 23 at 23:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Jonathan Allan Jan 23 at 23:51
  • \$\begingroup\$ sure. Very clever! \$\endgroup\$ – RGS Jan 23 at 23:52
2
\$\begingroup\$

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";
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 21 bytes

Fη⊞υE÷Lθ⁻ηι⊟θF⮌υIEι⌊ι

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

Fη

Loop from N down to 1.

⊞υE÷Lθ⁻ηι⊟θ

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

F⮌υIEι⌊ι

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 5 bytes with vertical output: äεWδ= \$\endgroup\$ – Grimmy Jan 24 at 16:46
  • 1
    \$\begingroup\$ 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, \$\endgroup\$ – Grimmy Jan 24 at 16:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Jan 24 at 17:33
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can narrow down the bug to rotoring with a Seq of Seqs. Try it online! \$\endgroup\$ – Jo King Jan 30 at 9:18
  • 1
    \$\begingroup\$ @JoKing Thanks, I've updated the bug. \$\endgroup\$ – SirBogman Jan 30 at 17:26
1
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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=.... \$\endgroup\$ – Wheat Wizard Jan 28 at 0:48
  • \$\begingroup\$ @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. \$\endgroup\$ – Leonardo Moraes Jan 28 at 15:58
  • \$\begingroup\$ 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. \$\endgroup\$ – Wheat Wizard Jan 29 at 1:19
  • \$\begingroup\$ 151 bytes: Rearranged things a bit more without fully understanding the code. Could probably golf more. Try it online! \$\endgroup\$ – SirBogman Jan 29 at 5:32
  • 1
    \$\begingroup\$ 145 bytes: 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] 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] \$\endgroup\$ – SirBogman Jan 29 at 5:46
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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}} \$\endgroup\$ – SirBogman Feb 2 at 5:16
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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.