Coloque uma matriz nos compartimentos

12

Nesse simples desafio, você recebe uma matriz Lde números inteiros não negativos e um número de posições bmaior que 0, mas não maior que o comprimento de L. Seu código deve retornar uma nova matriz Mcujo comprimento seja be que tenha colocado na matriz L. Isso é mais fácil explicado com exemplos.

L = [1,0,5,1]e b = 2retorna M = [1,6].

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

Até agora, tão simples. No entanto, nesta questão bnão precisa necessariamente se dividir len(L). Nesse caso, o último compartimento terá apenas menos números para compensar.

Cada compartimento, exceto possivelmente o último, deve ter o mesmo número de números contribuindo para o total. O último compartimento não deve ter mais números contribuindo para ele do que os outros compartimentos. O último compartimento deve ter o maior número possível de contribuintes, sujeito a outras regras.

L = [0,3,7,2,5,1]e b = 4retorna M = [3,9,6,0]. M = [10,8,0,0]não é uma saída aceitável, pois o terceiro compartimento não possui o número de nome de números que contribuem para ele como compartimentos 1e 2.

L = [0,3,7,2,5]e b = 2retorna M = [10,7]. M = [3, 14]não é uma saída aceitável, pois o último compartimento terá 3elementos que contribuem para ele, mas o primeiro possui apenas 2.

L = [1,1,1,1,1,1,1]e b = 3retorna M = [3,3,1].

Como regra final, seu código deve ser executado em tempo linear.

Você pode usar qualquer idioma ou biblioteca que desejar e pode assumir que a entrada é fornecida da maneira que achar conveniente.


Acontece que existem algumas entradas que não podem ser resolvidas. Por exemplo [1,1,1,1,1]e b=4. Seu código pode gerar o que quiser para essas entradas.


fonte
6
Eu acho que mais alguns casos de teste seriam bons.
Jonathan Frech 27/03
5
your code must run in linear time- Eu encontraria qualquer algoritmo que não siga isso naturalmente bem estranho
Uriel
2
@Uriel Não há limite para o quão estranho respostas code-golfe podem ser :)
4
@Lembik Embora de que maneira a proibição de tais abordagens estranhas em potencial seja benéfica para um desafio de código-golfe?
27618 Jonathan Frech
@JonathanFrech é só até as preferências do OP :)

Respostas:

5

APL (Dyalog) , 19 bytes

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

Experimente online!

Anexamos b zeros à matriz antes de remodelá- la em partes iguais de ⌈⍺÷⍨≢⍵( ⌈ comprimento de L ÷ b ⌉ ) e somatá- las, como representado em ,⍺⍴0, uma vez que qualquer quantidade de pontos em branco (que não fazem parte da matriz original) é maior que b - 1 seria preenchido com pelo menos elementos b - 1 de outros pedaços, o que torna o ponto de equilíbrio do último grupo na diferença máxima de b - 1 do resto. Usamos b> b - 1 porque é um código de golfe.

Por exemplo, L com 15 elementos eb = 3 não seria agrupado como

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

mas sim como (observe como os 2 xs mais à direita "preenchem" os zeros mais à esquerda)

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

enquanto uma matriz de 16 elementos seria preenchida com 2 ( 3 - 1 ) pontos em branco, como

x x x x x x
x x x x x x
x x x x 0 0
Uriel
fonte
3

Python 2 , 65 bytes

f=lambda l,n:n and[sum(l[:len(l)/n+1])]+f(l[len(l)/n+1:],n-1)or[]

Experimente online!

totalmente humano
fonte
3

R , 75 71 70 63 bytes

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

Experimente online!

Este almofadas Lcom NAaté que o comprimento é um múltiplo de b, em seguida, leva as somas de coluna Lcomo uma matriz com bcolunas, a remoção de NAvalores.

Explicando como um idioma baseado em pilha:

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
fonte
Muito bom e rápido! A ascensão do codificador R ... #
2
@Lembik Tive a sorte de ter entrado na TNB entre vocês dizendo "Vou postar isso como um desafio" e você realmente postando.
Giuseppe
1
Oh, veja "length [<-" também retornará como nosso amigo favorito "[<-". Nenhum bytes salvo para menos legibilidade:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo 27/03
1
@Vlo no bytes saved for less readabilityé provavelmente o lema do golfe R ... embora eu suponha que sum(L|1)seja um byte salvo length(L)!
Giuseppe
3

MATL , 6 bytes

vi3$es

Experimente online! Ou verifique todos os casos de teste .

Explicação

Considere a entrada 4, [0,3,7,2,5,1]como um exemplo.

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
fonte
1
Esta é a resposta mais impressionante na minha opinião.
3

Ruby , 54 53 bytes

Guardou um byte graças a @Kirill L.

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

Experimente online!

Restabelecer Monica - notmaynard
fonte
Bom, você também pode salvar um byte, substituindo [0]*bpor1..b
Kirill L.
@KirillL. Obrigado. Nem sequer me ocorreu.
Reintegrar Monica - notmaynard
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;}

Experimente online!

Jonathan Frech
fonte
2

Haskell , 61 bytes

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

Experimente online!

totalmente humano
fonte
2
Não parece funcionar [1, 2, 3, 4, 5, 6] # 3.
Nwellnhof 28/03
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;}

Experimente online aqui .

Encontrou uma maneira mais curta de escrever i/(n/b+(n%b==0?0:1) aqui: i/((n+b-1)/b)

Agradecimentos a Olivier Grégoire por jogar 3 bytes.

Versão não destruída:

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
fonte
86 bytes
Olivier Grégoire
@ OlivierGrégoire Obrigado!
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

Experimente online!

O melhor Elixir é dividir em partes com um comprimento de n . E não pode limitar muito bem a divisão como número inteiro; portanto, fazemos a divisão flutuante, arredondando-a para cima. Infelizmente, a única maneira de fazer isso resulta em um float, então o arredondamos novamente para um número inteiro.

Okx
fonte
Algumas de suas saídas têm o tamanho errado.
@Lembik corrigiu.
Okx 27/03
1

Perl 6 ,  52 51  50 bytes

52 bytes: teste

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

51 bytes: teste

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

50 bytes: Experimente

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

47 bytes não concorrentes Testá-lo

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

Não é competitivo, pois ».sumé permitido fazer os cálculos em paralelo. Portanto, pode ou não ser em tempo linear.


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
fonte
1

Carvão , 22 bytes

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

Experimente online! Link é a versão detalhada do código. Explicação:

Nθ

Entrada b.

Aη

Entrada L.

W﹪Lηθ⊞η⁰

Pressione a 0para Laté que Lo comprimento seja divisível por b.

E⪪η÷LηθIΣι

Divida Lo comprimento por be divida-o Lem seções desse comprimento; em seguida, somar cada seção e converter em string para saída implícita em linhas separadas.

Neil
fonte
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]);}

Experimente online!

f()usa os parâmetros da seguinte maneira::
Lponteiro para a matriz de entrada
l: comprimento da matriz de entrada
b: número de posições
m: ponteiro para o buffer que recebe nova matriz

A seguir, é apresentada uma versão 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
fonte
1

PHP, 88 bytes

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

função anônima, pega array e número inteiro, retorna array

O potencial só jogar golfe este tinha estava substituindo ceil(count($a)/$b))com (count($a)-1)/$b+1e abreviar (count($a)-1)com ~-count($a). O float resultante é convertido implicitamente em número inteiro na array_chunkchamada.

Experimente online .

Titus
fonte