Masukkan array ke dalam tempat sampah

12

Dalam tantangan sederhana ini Anda akan diberikan array input Lbilangan bulat non-negatif dan sejumlah nampan blebih besar dari 0 tetapi tidak lebih dari panjangnya L. Kode Anda harus mengembalikan array baru Myang panjangnya bdan yang telah membuang array L. Ini paling mudah dijelaskan dengan contoh.

L = [1,0,5,1]dan b = 2kembali M = [1,6].

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

Sejauh ini, sangat sederhana. Namun dalam pertanyaan bini tidak harus membelah len(L). Dalam hal ini, nampan terakhir hanya memiliki jumlah yang lebih sedikit untuk menebusnya.

Setiap bin kecuali mungkin yang terakhir harus memiliki jumlah angka yang sama yang berkontribusi terhadap totalnya. Nampan terakhir tidak boleh memiliki lebih banyak angka yang berkontribusi daripada nampan lainnya. Tempat sampah terakhir harus memiliki jumlah yang berkontribusi sebanyak mungkin sesuai dengan aturan lainnya.

L = [0,3,7,2,5,1]dan b = 4kembali M = [3,9,6,0]. M = [10,8,0,0]bukan keluaran yang dapat diterima karena nampan ketiga tidak memiliki nomor nama yang berkontribusi sebagai nampan 1dan 2.

L = [0,3,7,2,5]dan b = 2kembali M = [10,7]. M = [3, 14]bukan keluaran yang dapat diterima karena nampan terakhir akan memiliki 3elemen yang berkontribusi padanya tetapi yang pertama hanya memiliki 2.

L = [1,1,1,1,1,1,1]dan b = 3kembali M = [3,3,1].

Sebagai aturan terakhir, kode Anda harus dijalankan dalam waktu linier.

Anda dapat menggunakan bahasa atau perpustakaan apa saja yang Anda suka dan dapat berasumsi bahwa input disediakan dengan cara apa pun yang Anda rasa nyaman.


Ternyata ada beberapa input yang tidak bisa diselesaikan. Sebagai contoh [1,1,1,1,1]dan b=4. Kode Anda dapat menampilkan apa pun yang diinginkan untuk input tersebut.


sumber
6
Saya pikir beberapa kasus uji lagi akan menyenangkan.
Jonathan Frech
5
your code must run in linear time- Saya akan menemukan algoritma yang tidak mengikuti ini secara alami sangat aneh
Uriel
2
@Uriel Tidak ada batasan seberapa aneh jawaban kode-golf :)
4
@ Lembik Meskipun dengan cara apa menolak potensi pendekatan aneh seperti itu bermanfaat untuk tantangan kode-golf?
Jonathan Frech
@JonathanFrech itu hanya ke preferensi OP :)

Jawaban:

5

APL (Dyalog) , 19 byte

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

Cobalah online!

Kami menambahkan b nol ke array sebelum membentuknya kembali menjadi bagian yang sama ⌈⍺÷⍨≢⍵( of panjang L ÷ b ⌉ ) dan menjumlahkannya, seperti yang digambarkan ,⍺⍴0, karena jumlah tempat kosong (yang bukan bagian dari array asli) lebih besar dari b - 1 akan diisi dengan setidaknya b - 1 elemen dari bongkahan lain, yang membuat titik penyeimbang grup terakhir maksimum b - 1 berbeda dari yang lain. Kami menggunakan b> b - 1 karena ini adalah kode golf.

Misalnya, L dengan 15 elemen dan b = 3 tidak akan dikelompokkan sebagai

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

melainkan sebagai (perhatikan bagaimana 2 xs paling kanan "mengisi" nol paling kiri)

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

sedangkan array 16 elemen akan diisi dengan 2 ( 3 - 1 ) tempat kosong, seperti

x x x x x x
x x x x x x
x x x x 0 0
Uriel
sumber
3

Python 2 , 65 byte

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

Cobalah online!

benar-benar manusiawi
sumber
3

R , 75 71 70 63 byte

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

Cobalah online!

Ini bantalan Ldengan NAsampai panjangnya adalah kelipatan b, kemudian mengambil jumlah kolom Lsebagai matriks dengan bkolom, menghapus NAnilai-nilai.

Menjelaskan sebagai bahasa berbasis tumpukan:

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
sumber
Sangat bagus dan cepat! Munculnya kode R ...
2
@Lembik Saya cukup beruntung telah muncul di TNB tepat di antara Anda mengatakan "Saya akan memposting ini sebagai tantangan" dan Anda benar-benar mempostingnya.
Giuseppe
1
Oh, lihat "panjang [<-" akan kembali juga seperti teman favorit kami "[<-". Tidak ada byte yang disimpan untuk keterbacaan yang lebih sedikit:function(L,b)colSums(matrix("length<-"(L,ceiling(length(L)/b)*b),,b),T)
Vlo
1
@Vo no bytes saved for less readabilitymungkin moto dari golf R ... meskipun saya kira itu sum(L|1)adalah byte yang disimpan length(L)!
Giuseppe
3

MATL , 6 byte

vi3$es

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Pertimbangkan input 4, [0,3,7,2,5,1]sebagai contoh.

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
sumber
1
Ini adalah jawaban paling mengesankan menurut saya.
3

Ruby , 54 53 byte

Menyimpan satu byte berkat @Kirill L.

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

Cobalah online!

Pasang kembali Monica - notmaynard
sumber
Bagus, Anda juga dapat menyimpan byte dengan menggantinya [0]*bdengan1..b
Kirill L.
@ KirillL. Terima kasih. Bahkan tidak terpikir oleh saya.
Pasang kembali Monica - notmaynard
2

C (gcc) , 107 byte

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;}

Cobalah online!

Jonathan Frech
sumber
2

Haskell , 61 byte

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

Cobalah online!

benar-benar manusiawi
sumber
2
Sepertinya tidak berhasil [1, 2, 3, 4, 5, 6] # 3.
nwellnhof
2

Java 10, 96 89 86 byte

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;}

Cobalah online di sini .

Temukan cara yang lebih singkat untuk menulis di i/(n/b+(n%b==0?0:1) sini: i/((n+b-1)/b)

Terima kasih kepada Olivier Grégoire karena bermain golf 3 byte.

Versi tidak disatukan:

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;
}
Ketidakseimbangan
sumber
86 byte
Olivier Grégoire
@ OlivierGrégoire Terima kasih!
OOBalance
1

Elixir , 98 byte

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

Cobalah online!

Elixir terbaik yang dimiliki adalah membelah menjadi beberapa bagian dengan panjang n . Dan itu tidak dapat menghentikan pembagian sebagai integer dengan sangat baik, jadi kami melakukan pembagian float, mengumpulkannya. Sayangnya satu-satunya cara untuk melakukan ini menghasilkan float, jadi kami membulatkannya lagi menjadi integer.

Okx
sumber
Beberapa output Anda memiliki panjang yang salah.
@Lembik memperbaikinya.
Okx
1

Perl 6 ,  52 51  50 byte

52 byte: Uji itu

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

51 byte: Uji itu

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

50 byte: Cobalah

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

47 byte non-bersaing Uji itu

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

Ini tidak bersaing karena ».sumdiperbolehkan melakukan perhitungan secara paralel. Jadi mungkin atau tidak dalam waktu linier.


Diperluas:

{  # 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
sumber
1

Arang , 22 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Nθ

Masukan b.

Aη

Masukan L.

W﹪Lηθ⊞η⁰

Mendorong 0untuk Lsampai L's panjang habis dibagi b.

E⪪η÷LηθIΣι

Bagi Lpanjang dengan bmembagi Lmenjadi beberapa bagian dari panjang itu, kemudian jumlah masing-masing bagian dan dilemparkan ke string untuk output implisit pada baris yang terpisah.

Neil
sumber
1

C (dentang) , 58 byte

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

Cobalah online!

f()mengambil parameter sebagai berikut::
Lpointer ke array input
l: panjang array input
b: jumlah sampah
m: pointer ke buffer yang menerima array baru

Berikut ini adalah versi kembali-masuk @ 60 byte:

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

PHP, 88 byte

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

fungsi anonim, mengambil array dan integer, mengembalikan array

Satu-satunya golf potensi ini harus telah menggantikan ceil(count($a)/$b))dengan (count($a)-1)/$b+1dan menyingkat (count($a)-1)dengan ~-count($a). Float yang dihasilkan secara implisit dilemparkan ke integer dalam array_chunkpanggilan.

Cobalah online .

Titus
sumber