En este desafío simple, se le proporciona una matriz L
de entrada de enteros no negativos y una cantidad de bins b
mayor que 0 pero no mayor que la longitud de L
. Su código debe devolver una nueva matriz M
cuya longitud es b
y que ha agrupado la matriz L
. Esto se explica más fácilmente con ejemplos.
L = [1,0,5,1]
y b = 2
vuelve M = [1,6]
.
L = [0,3,7,2,5,1]
y b = 3
vuelve M = [3,9,6]
.
Hasta ahora, muy simple. Sin embargo, en esta pregunta b
no 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 = 4
vuelve 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 1
y 2
.
L = [0,3,7,2,5]
y b = 2
vuelve M = [10,7]
. M = [3, 14]
no es una salida aceptable ya que el último bin tendrá 3
elementos que contribuyen a él, pero el primero solo tiene 2
.
L = [1,1,1,1,1,1,1]
y b = 3
vuelve 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.
your code must run in linear time
- Encontraría cualquier algoritmo que no siga esto naturalmente bastante extrañoRespuestas:
APL (Dyalog) , 19 bytes
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
sino más bien como (observe cómo los 2
x
s de la derecha "llenan" los ceros de la izquierda)mientras que una matriz de 16 elementos se llenaría con 2 ( 3 - 1 ) espacios en blanco, como
fuente
Python 2 , 65 bytes
Pruébalo en línea!
fuente
R ,
75717063 bytesPruébalo en línea!
Este almohadillas
L
conNA
hasta que la longitud es un múltiplo deb
, a continuación, toma las sumas de columna deL
como una matriz conb
columnas, la eliminación deNA
valores.Explicando como un lenguaje basado en pila:
fuente
function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
no bytes saved for less readability
es probablemente el lema del golf R ... ¡aunque supongo quesum(L|1)
es un byte guardadolength(L)
!MATL , 6 bytes
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.fuente
Ruby ,
5453 bytesSalvó un byte gracias a @Kirill L.
Pruébalo en línea!
fuente
[0]*b
por1..b
C (gcc) , 107 bytes
Pruébalo en línea!
fuente
Haskell , 61 bytes
Pruébalo en línea!
fuente
[1, 2, 3, 4, 5, 6] # 3
.Java 10,
968986 bytesPrué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:
fuente
Elixir , 98 bytes
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.
fuente
Perl 6 ,
52 5150 bytes52 bytes: pruébelo
51 bytes: pruébelo
50 bytes: Pruébalo
47 bytes no competitivos Pruébelo
No es competitivo ya que
».sum
está permitido hacer los cálculos en paralelo. Entonces puede o no estar en tiempo lineal.Expandido:
fuente
Carbón de leña , 22 bytes
Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:
Entrada
b
.Entrada
L
.Presione
0
aL
hasta queL
la longitud sea divisible porb
.Divida
L
la longitud porb
y divídalaL
en secciones de esa longitud, luego sume cada sección y convierta en cadena para la salida implícita en líneas separadas.fuente
JavaScript (Node.js) , 71 bytes
Pruébalo en línea!
fuente
C (clang) , 58 bytes
Pruébalo en línea!
f()
toma los parámetros de la siguiente manera::L
puntero a la matriz de entradal
: longitud de la matriz de entradab
: número de contenedoresm
: puntero al búfer que recibe una nueva matrizLa siguiente es una versión reentrante a 60 bytes:
fuente
PHP, 88 bytes
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+1
y abreviando(count($a)-1)
con~-count($a)
. El flotante resultante se convierte implícitamente en entero en laarray_chunk
llamada.Pruébalo en línea .
fuente