Poner una matriz en contenedores

12

En este desafío simple, se le proporciona una matriz Lde entrada de enteros no negativos y una cantidad de bins bmayor que 0 pero no mayor que la longitud de L. Su código debe devolver una nueva matriz Mcuya longitud es by que ha agrupado la matriz L. Esto se explica más fácilmente con ejemplos.

L = [1,0,5,1]y b = 2vuelve M = [1,6].

L = [0,3,7,2,5,1]y b = 3vuelve M = [3,9,6].

Hasta ahora, muy simple. Sin embargo, en esta pregunta bno necesariamente tiene que dividirse len(L). En este caso, el último contenedor tendrá menos números para compensarlo.

Cada contenedor, excepto posiblemente el último, debe tener el mismo número de números que contribuyen a su total. El último contenedor no debe tener más números que contribuyan a él que los otros contenedores. El último contenedor debe tener tantos números contribuyendo como sea posible sujeto a las otras reglas.

L = [0,3,7,2,5,1]y b = 4vuelve M = [3,9,6,0]. M = [10,8,0,0]no es una salida aceptable ya que el tercer bin no tiene el número de nombres que contribuyen a él como bins 1y 2.

L = [0,3,7,2,5]y b = 2vuelve M = [10,7]. M = [3, 14]no es una salida aceptable ya que el último bin tendrá 3elementos que contribuyen a él, pero el primero solo tiene 2.

L = [1,1,1,1,1,1,1]y b = 3vuelve M = [3,3,1].

Como regla final, su código debe ejecutarse en tiempo lineal.

Puede usar cualquier idioma o biblioteca que desee y puede asumir que la entrada se proporciona de la forma que le resulte conveniente.


Resulta que hay algunas entradas que no se pueden resolver. Por ejemplo [1,1,1,1,1]y b=4. Su código puede generar lo que quiera para esas entradas.


fuente
66
Creo que algunos casos de prueba más serían buenos.
Jonathan Frech
55
your code must run in linear time- Encontraría cualquier algoritmo que no siga esto naturalmente bastante extraño
Uriel
2
@Uriel No hay límite en lo que pueden ser las respuestas extrañas de código de golf :)
44
@Lembik Aunque, ¿de qué manera está rechazando tales enfoques potenciales extraños beneficiosos para un desafío de código de golf?
Jonathan Frech
@JonathanFrech depende de las preferencias del OP :)

Respuestas:

5

APL (Dyalog) , 19 bytes

{+/⍺(⌈⍺÷⍨≢⍵)⍴⍵,⍺⍴0}

Pruébalo en línea!

Agregamos ceros b a la matriz antes de volver a darle forma en partes iguales de ⌈⍺÷⍨≢⍵( ⌈ longitud de L ÷ b ⌉ ) y sumarlos , como se muestra en ,⍺⍴0, ya que cualquier cantidad de puntos en blanco (que no son parte de la matriz original) más grande que b - 1 se rellenaría con al menos b - 1 elementos de otros fragmentos, lo que hace que el punto de equilibrio del último grupo sea máximo b - 1 diferencia del resto. Usamos b> b - 1 porque es código golf.

Por ejemplo, L con 15 elementos y b = 3 no se agruparía como

x x x x x x
x x x x x x
x x x 0 0 0

sino más bien como (observe cómo los 2 xs de la derecha "llenan" los ceros de la izquierda)

x x x x x
x x x x x
x x x x x

mientras que una matriz de 16 elementos se llenaría con 2 ( 3 - 1 ) espacios en blanco, como

x x x x x x
x x x x x x
x x x x 0 0
Uriel
fuente
3

R , 75 71 70 63 bytes

function(L,b)colSums(matrix(L[1:(ceiling(sum(L|1)/b)*b)],,b),T)

Pruébalo en línea!

Este almohadillas Lcon NAhasta que la longitud es un múltiplo de b, a continuación, toma las sumas de columna de Lcomo una matriz con bcolumnas, la eliminación de NAvalores.

Explicando como un lenguaje basado en pila:

function(L,b){
      (ceiling(sum(L|1)/b*b)  # push the next multiple of b >= length(L), call it X
    1:..                      # push the range 1:X
  L[..]                       # use this as an index into L. This forces L
                              # to be padded to length X with NA for missing values
        matrix(..,,b)         # create a matrix with b columns, using L for values
                              # and proceeding down each column, so
                              # matrix(1:4,,2) would yield [[1,3],[2,4]]
colSums(.., na.rm = T)        # sum each column, removing NAs

Giuseppe
fuente
Muy agradable y rápido! El ascenso del codificador R ...
2
@Lembik Tuve la suerte de haber aparecido en TNB justo entre ustedes diciendo "Voy a publicar esto como un desafío" y en realidad lo está publicando.
Giuseppe
1
Oh, mira "length [<-" también regresará como nuestro amigo favorito "[<-". No se guardaron bytes para una menor legibilidad:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@Vlo no bytes saved for less readabilityes probablemente el lema del golf R ... ¡aunque supongo que sum(L|1)es un byte guardado length(L)!
Giuseppe
3

MATL , 6 bytes

vi3$es

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Considere la entrada 4, [0,3,7,2,5,1]como un ejemplo.

v       % Vertically concatenate stack contents. Gives the empty array, []
        % STACK: []
i       % Input b
        % STACK: [], 4
        % Implicitly input L at the bottom of the stack
        % STACK: [0,3,7,2,5,1], [], 4
3$e     % 3-input reshape. This reshapes L with [] rows and b columns, in
        % column-major order (down, then across). [] here means that the
        % number of rows is chosen as needed to give b columns. Padding
        % with trailing zeros is applied if needed
        % STACK: [0 7 5 0;
                  3 2 1 0]
s       % Sum of each column
        % STACK: [3 9 6 0]
        % Implicitly display
Luis Mendo
fuente
1
Esta es la respuesta más impresionante en mi opinión.
3

Ruby , 54 53 bytes

Salvó un byte gracias a @Kirill L.

->l,b{s=1.0*l.size/b;(1..b).map{l.shift(s.ceil).sum}}

Pruébalo en línea!

Restablecer a Monica - notmaynard
fuente
Agradable, también puedes guardar un byte reemplazándolo [0]*bpor1..b
Kirill L.
@KirillL. Gracias. Ni siquiera se me había ocurrido.
Restablece a Monica - notmaynard el
2

C (gcc) , 107 bytes

j,k,t,Q;f(A,l,b)int*A;{for(j=~0;b>++j;printf("%d,",t))for(t=k=0;(Q=!!(l%b)+l/b)>k;t+=Q<l?A[Q]:0)Q=k+++Q*j;}

Pruébalo en línea!

Jonathan Frech
fuente
2

Haskell , 61 bytes

l#0=[]
l#n|o<-length l`div`n+1=sum(take o l):(drop o l)#(n-1)

Pruébalo en línea!

totalmente humano
fuente
2
Parece que no funciona [1, 2, 3, 4, 5, 6] # 3.
nwellnhof
2

Java 10, 96 89 86 bytes

a->b->{int r[]=new int[b],i=0,n=a.length;for(;i<n;)r[i/((n+b-1)/b)]+=a[i++];return r;}

Pruébelo en línea aquí .

Encontré una forma más corta de escribir i/(n/b+(n%b==0?0:1) aquí: i/((n+b-1)/b)

Gracias a Olivier Grégoire por jugar al golf 3 bytes.

Versión sin golf:

input -> bins -> { // input is int[] (original array), bins is int (number of bins)
    int result[] = new int[bins], // resulting array, initialized with all 0
    i = 0, // for iterating over the original array
    n = a.length; // length of the original array
    for(; i < n ;) // iterate over the original array
        result[i / ((n + bins - 1) / bins)] += input[i++]; // add the element to the right bin; that's bin n/bins if bins divides n, floor(n/bins)+1 otherwise
    return result;
}
OOBalance
fuente
86 bytes
Olivier Grégoire
@ OlivierGrégoire Gracias!
OOBalance
1

Elixir , 98 bytes

fn l,b->Enum.map Enum.chunk(l++List.duplicate(0,b-1),round Float.ceil length(l)/b),&Enum.sum/1 end

Pruébalo en línea!

Lo mejor que tiene Elixir es dividirse en partes con una longitud de n . Y no puede limitar la división como número entero muy bien, por lo que hacemos división flotante, redondeamos. Desafortunadamente, la única forma de hacerlo resulta en un flotante, por lo que lo redondeamos nuevamente a un entero.

Okx
fuente
Algunas de sus salidas tienen una longitud incorrecta.
@Lembik lo arregló.
Okx
1

Perl 6 ,  52 51  50 bytes

52 bytes: pruébelo

->\L,\b{L.rotor(:partial,ceiling L/b)[^b].map: &sum}

51 bytes: pruébelo

{@^a.rotor(:partial,ceiling @a/$^b)[^$b].map: &sum}

50 bytes: Pruébalo

{map &sum,@^a.rotor(:partial,ceiling @a/$^b)[^$b]}

47 bytes no competitivos Pruébelo

{@^a.rotor(:partial,ceiling @a/$^b)[^$b]».sum}

No es competitivo ya que ».sumestá permitido hacer los cálculos en paralelo. Entonces puede o no estar en tiempo lineal.


Expandido:

{  # bare block with two placeholder parameters 「@a」 and 「$b」

  map                   # for each sublist

    &sum,               # find the sum


    @^a                 # declare and use first parameter

    .rotor(             # break it into chunks

      :partial,         # include trailing values that would be too few otherwise

      ceiling @a / $^b # the number of elements per chunk

    )[ ^$b ]           # get the correct number of chunks if it would be too few

}
Brad Gilbert b2gills
fuente
1

Carbón de leña , 22 bytes

NθAηW﹪Lηθ⊞η⁰E⪪η÷LηθIΣι

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

Nθ

Entrada b.

Aη

Entrada L.

W﹪Lηθ⊞η⁰

Presione 0a Lhasta que Lla longitud sea divisible por b.

E⪪η÷LηθIΣι

Divida Lla longitud por by divídala Len secciones de esa longitud, luego sume cada sección y convierta en cadena para la salida implícita en líneas separadas.

Neil
fuente
1

C (clang) , 58 bytes

i;f(*L,l,b,*m){b=l/b+!!(l%b);for(i=0;i<l;m[i++/b]+=L[i]);}

Pruébalo en línea!

f()toma los parámetros de la siguiente manera::
Lpuntero a la matriz de entrada
l: longitud de la matriz de entrada
b: número de contenedores
m: puntero al búfer que recibe una nueva matriz

La siguiente es una versión reentrante a 60 bytes:

f(*L,l,b,*m){b=l/b+!!(l%b);for(int i=0;i<l;m[i++/b]+=L[i]);}
GPS
fuente
1

PHP, 88 bytes

function($a,$b){return array_map(array_sum,array_chunk($a,~-count($a)/$b+1))+[$b-1=>0];}

función anónima, toma matriz e entero, devuelve matriz

El potencial sólo jugar al golf esto tenía estaba reemplazando ceil(count($a)/$b))con (count($a)-1)/$b+1y abreviando (count($a)-1)con ~-count($a). El flotante resultante se convierte implícitamente en entero en la array_chunkllamada.

Pruébalo en línea .

Titus
fuente