Penjumlahan irisan kolom yang tumpang tindih

19

Tugas

Mengingat daftar bilangan bulat L dan lain bilangan bulat s , tujuannya adalah untuk menghitung jumlah kolom-bijaksana semua s -Panjang (berpotensi tumpang tindih) irisan L , sedangkan yang berkaitan posisi mereka relatif terhadap L (lihat di bawah).

Definisi

The s -Panjang (tumpang tindih) irisan dari daftar L adalah semua subsequences bersebelahan (tanpa pembungkus) dari L yang panjang s .

Dalam rangka untuk berhubungan posisi dari irisan s relatif terhadap L , Anda bisa membayangkan membangun sebuah "tangga", di mana setiap irisan s i telah offset i posisi dari awal.


Spesifikasi

  • s adalah bilangan bulat lebih tinggi dari 1 dan ketat lebih kecil dari panjang L .
  • L akan selalu mengandung setidaknya 3 elemen.
  • Anda dapat bersaing dalam bahasa pemrograman apa pun dan dapat mengambil input dan memberikan output melalui metode standar apa pun , sambil memperhatikan bahwa celah ini dilarang secara default. Ini adalah , jadi pengiriman terpendek (dalam byte) untuk setiap bahasa menang.

Contoh dan Kasus Uji

Berikut ini contoh yang berhasil:

[1, 2, 3, 4, 5, 6, 7, 8, 9], 3

[1, 2, 3]
   [2, 3, 4]
      [3, 4, 5]
         [4, 5, 6]
            [5, 6, 7]
               [6, 7, 8]
                  [7, 8, 9]
-------------------------------- (+)  | column-wise summation
[1, 4, 9, 12, 15, 18, 21, 16, 9]

Dan beberapa kasus uji lagi:

[1, 3, 12, 100, 23], 4         -> [1, 6, 24, 200, 23]
[3, -6, -9, 19, 2, 0], 2       -> [3, -12, -18, 38, 4, 0]
[5, 6, 7, 8, 2, -4, 7], 3      -> [5, 12, 21, 24, 6, -8, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9], 3 -> [1, 4, 9, 12, 15, 18, 21, 16, 9]
[1, 1, 1, 1, 1, 1, 1], 6       -> [1, 2, 2, 2, 2, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9], 6 -> [1, 4, 9, 16, 20, 24, 21, 16, 9]
Tuan Xcoder
sumber
2
Kasus uji pertama itu menyebalkan. ;) Hanya karena slebih besar dari L/2. Mungkin menambahkan beberapa test case lagi dimana itu merupakan kasus [1, 1, 1, 1, 1, 1, 1], 6 -> [1, 2, 2, 2, 2, 2, 1] `atau [1, 2, 3, 4, 5, 6, 7, 8, 9], 6 -> [1, 4, 9, 16, 20, 24, 21, 16, 9]?
Kevin Cruijssen
2
@KevinCruijssen Bisakah Anda sunting untuk saya? Itu adalah beberapa test case yang bagus, tapi sekarang saya menggunakan ponsel;) Terima kasih!
Tn. Xcoder

Jawaban:

11

J , 11, 9 8 byte

-1 byte berkat mil!

[:+//.]\

Bagaimana itu bekerja?

Argumen kiri adalah s, yang benar - L

]\ - Membagi L menjadi sub daftar dengan panjang s

/. - mengekstrak diagonal miring (anti-diagonal)

+/ - menambahkannya

[: - membuat garpu dari kata kerja di atas

Inilah contoh sesi J untuk test case pertama:

   a =. 1 2 3 4 5 6 7 8 9

   ] 3 ]\ a 
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9

   ] </. 3 ]\ a 
┌─┬───┬─────┬─────┬─────┬─────┬─────┬───┬─┐
│1│2 2│3 3 3│4 4 4│5 5 5│6 6 6│7 7 7│8 8│9│
└─┴───┴─────┴─────┴─────┴─────┴─────┴───┴─┘

   ] +//. 3 ]\ a 
1 4 9 12 15 18 21 16 9

Cobalah online!

Galen Ivanov
sumber
Apakah ada perbedaan antara "miring diagonal" dan "diagonal"?
Luis Mendo
@Luis Mendo - Saya pikir "miring" berarti bergerak dari kiri ke bawah ke kanan dalam kasus kata keterangan J /., berlawanan dengan diagonal utama yang bergerak dari atas ke kiri ke bawah ke kanan.
Galen Ivanov
1
Ah terima kasih. Jadi itulah yang biasanya disebut anti-diagonal
Luis Mendo
2
Anda bisa mengganti ,/\dengan]\
miles
@miles Ya, tentu saja! Terima kasih!
Galen Ivanov
9

Haskell , 59 56 byte

s#n=[x*minimum[n,i,length s+1-max i n]|(i,x)<-zip[1..]s]

Cobalah online!

Menentukan fungsi (#)yang mengambil daftars dan dan nomor nsebagai argumen.

Ini berdasarkan pengamatan bahwa untuk s = [1, 2, 3, 4, 5, 6, 7, 8, 9]dann = 3

[1, 2, 3]
   [2, 3, 4]
      [3, 4, 5]
         [4, 5, 6]
            [5, 6, 7]
               [6, 7, 8]
                  [7, 8, 9]
---------------------------- (+)
[1, 4, 9,12,15,18,21,16, 9]

sama dengan

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 3, 3, 3, 3, 2, 1]
---------------------------- (*)
[1, 4, 9,12,15,18,21,16, 9]

Untuk membuat daftar ini pada awalnya meningkat, lalu daftar konstan dan akhirnya menurun, kita bisa mulai dengan

[minimum[i, length s + 1 - i] | i<-[1..length s]]

yang menghasilkan [1, 2, 3, 4, 5, 4, 3, 2, 1]. Menambahkan nsebagai kendala tambahan ke dalam minimumekspresi menghasilkan [1, 2, 3, 3, 3, 3, 3, 2, 1]jawaban daftar yang benar untuk n = 3, meskipun untuk n = 6(atau secara umum ada n > lengths s/2) kendala tambahan length s + 1 - ndiperlukan:

[minimum[i, n, length s + 1 - i, length s + 1 - n] | i<-[1..length s]]

atau lebih pendek:

[minimum[i, n, length s + 1 - max i n] | i<-[1..length s]]

Untuk perkalian berpasangan berpasangan [1..length s]dengan zip s, dan karena zipmemotong daftar yang lebih panjang dengan panjang yang lebih pendek daftar tak terbatas [1..]dapat digunakan:

[x * minimum[i, n, length s + 1 - max i n] | (i,x)<-zip[1..]s]
Laikoni
sumber
6

JavaScript (ES6), 65 62 58 byte

Disimpan 4 byte berkat @Shaggy

Mengambil input dalam sintaks currying (a)(n).

a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i)))

Uji kasus

Arnauld
sumber
Apakah a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i)))berfungsi untuk 58 byte?
Shaggy
@Shaggy Entah bagaimana, saya tahu ada sesuatu yang benar-benar bodoh dalam kode saya tetapi tidak bisa mengetahuinya ... Terima kasih banyak!
Arnauld
6

Java 8, 83 byte

L->s->{for(int i=0,l=L.length+1,t,u;++i<l;u=l-(s>i?s:i),L[i-1]*=t<u?t:u)t=i<s?i:s;}

Kasing uji pertama (dan dua yang terakhir saya tambahkan) mengacaukan saya beberapa kali, tetapi akhirnya berfungsi sekarang ..: D

Mengubah array input alih-alih mengembalikan yang baru.

Penjelasan:

Cobalah online.

L->s->{                  // Method with int-array and int parameters, and no return-type
  for(int i=0,           //  Index-integer, starting at 0
      l=L.length+1,      //  The length of the input-array + 1
      t,u;               //  Two temp integers
      ++i<l              //  Loop `i` from 1 to the length (inclusive)
      ;                  //    After every iteration:
       u=l               //     Set temp integer `u` to the length plus 1,
          -(s>i?s:i),    //     minus the highest of `s` and `i`
       L[i-1]*=t<u?t:u)  //     And replace the item with the lowest of `t` and `u`
    t=i<s?i:s;}          //   Set temp integer `t` to the lowest of `i` or `s`
Kevin Cruijssen
sumber
5

MATL , 8 byte

YCPT&Xds

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

Pertimbangkan input [1, 3, 12, 100, 23]dan 4.

YC     % Implicit inputs: row vector L and number s. Create matrix of 
       % overlapping blocks of L with length s, where each block is a column
       % STACK: [  1   3;
                   3  12;
                  12 100;
                 100  23]
P      % Flip vertically
       % STACK: [100  23;
                  12 100;
                   3  12;
                   1   3]
&TXd   % Extract all diagonals, starting from bottom-left, and arrange them as
       % columns of a matrix, with zero padding
       % STACK: [1   3  12 100   0;
                 0   3  12 100  23]
s      % Sum of each column. Since s is less than the length of L, there are
       % at least two rows. Thus function `s` can be used instead of `Xs`.
       % Implicit display
       % STACK: [1   6  24 200  23]
Luis Mendo
sumber
5

APL (Dyalog Unicode) , 19 14 byte SBCS

-5 Terima kasih kepada ngn.

Anix tacit infix function mengambil s sebagai argumen kiri dan L sebagai argumen kanan. Mengasumsikan ⎕IO( I ndex O rigin) 0sebagai default pada banyak sistem.

+⌿∘↑((0,⊢)\,/)

Cobalah online!

Penjelasan dengan contoh kasus [1,3,12,100,23]

(... ) terapkan fungsi diam-diam anonim berikut:

,/ jendela yang tumpang tindih dengan ukuran itu; [[1,3,12],[3,12,100],[12,100,23]]

(... secara )\ kumulatif menerapkan fungsi diam-diam berikut ini:

   argumen yang paling tepat

  0, dengan nol di sebelah kiri

Reduksi kumulatif berarti kita memasukkan fungsi ke setiap "ruang" di antara istilah-istilah yang berurutan, bekerja dengan cara kami dari kanan ke kiri. Untuk setiap "spasi", fungsi akan membuang argumen kiri tetapi menambahkan nol tambahan. Secara efektif, ini menambahkan nol untuk setiap istilah karena ada "spasi" di sebelah kirinya, sehingga suku pertama mendapat nol spasi, yang kedua mendapat satu, dan yang ketiga mendapat dua:[[1,3,12],[0,3,12,100],[0,0,12,100,23]]

 naik pangkat dengan menggabungkan daftar ke dalam matriks tunggal, padding dengan nol;
┌ ┐
│1 3 12 0 0│
│0 3 12 100 0│
│0 0 12 100 23│
└ ┘
 lalu
+⌿ jumlahkan secara vertikal;[1,6,36,200,23]

Adm
sumber
1
⊢,⍨¨0⍴⍨¨⍳∘≢->{0,⍵}\
ngn
@ ngn Anda selalu memikirkan pengurangan pintar ini, tetapi Anda harus memposting ini secara terpisah. Btw, saya menemukan +⌿∘↑((0,⊢)\,/)lebih elegan.
Adám
oh ayolah, ini adalah kasus yang jelas tentang penyederhanaan bagian dari solusi, bukan ide baru
ngn
@ngn Sementara itu, selesaikan CMC ini !
Adám
Saya tidak yakin ini sesuai topik dalam komentar di sini, tetapi mengapa Anda tidak menggunakan "masing-masing"? 2{(⊃⌽⍺),⊃⍵}/⊢->2{⊃¨(⌽⍺)⍵}/⊢
ngn
4

Jelly , 6 byte

JṡṬS×ḷ

Cobalah online!

Bagaimana itu bekerja

JṡṬS×ḷ  Main link. Left argument: A (array). Right argument: n (integer)

J       Indices; yield [1, ..., len(A)].
 ṡ      Split the indices into overlapping slices of length n.
  Ṭ     Untruth; map each array of indices to a Boolean vector, with 1's at the
        specified indices and 0's elsewhere.
        For example, [3, 4, 5] maps to [0, 0, 1, 1, 1].
   S    Sum the rows, essentially counting how many times each index appears in
        the arrays returned by the ṡ atom.
     ḷ  Left; yield A.
    ×   Multiply the counts to the left with the integers to the right.
Dennis
sumber
3

Japt , 13 byte

Butuh waktu terlalu lama untuk ini bekerja ketika s> L/2!

Ë*°EmVUÊÄ-EwV

Cobalah


Penjelasan

                 :Implicit input of array U and integer V
Ë                :Map over each element at 0-based index E in U
 *               :  Multiply by
    m            :  The minumum of
  °E             :    E incremented,
     V           :    V,
          EwV    :    and the maximum of E & V
         -       :    subtracted from
      UÊÄ        :    the length of U plus 1
Shaggy
sumber
Butuh waktu terlalu lama untuk ini bekerja ketika s > L/2! ” Aku memiliki persis sama Kasus uji lainnya mudah, tetapi yang pertama (dan dua yang saya tambahkan di akhir) sangat mengganggu! .. +1 dari saya!
Kevin Cruijssen
2

Julia , 41 byte

a\n=(a[L=end];a.*min(1:L,L:-1:1,n,L-n+1))

Cobalah online!

  • Tetapkan ulang \operator.
  • a[L=end]adalah alternatif yang lebih pendek L=length(a).
  • Menggunakan metode Laikoni .
LukeS
sumber
2

Japt , 13 12 byte

-1 byte terima kasih kepada @ETHproductions

ãV
ËEÆÃcDÃyx

Cobalah online!

Oliver
sumber
1

R , 52 51 byte

function(l,s)l*pmin(s,x<-seq(l),y<-rev(x),y[1]+1-s)

Cobalah online!

Ini setara dengan jawaban Laikoni .

seq(l)menghasilkan indeks 1...length(l)sejak length(l)>1(kalau tidak akan menghasilkan 1...l[1]). Saya menyimpannya sebagai x, menyimpannya sebagai y, dan mengambil elemen pertama dari y(length(l) ) untuk mem-porting jawaban Laikoni dengan rapi dan menyimpan satu byte!

Jawaban asli, 52 byte

function(l,s,L=sum(l|1)+1)l*pmin(s,x<-2:L-1,L-x,L-s)

Cobalah online!

Outputnya adalah lelemen dikalikan dengan minimum s, indeks berbasis elemen 1x , length(l)-x+1dan length(L)-s+1.

Ini juga setara dengan jawaban Laikoni, menggunakan L-xbukan rev(x)karena lebih pendek.

Giuseppe
sumber
1

APL + WIN, 25 byte

Anjuran untuk input layar L diikuti oleh s

+/(1-⍳⍴z)⌽¨(⍴L)↑¨s←⎕,/L←⎕

Penjelasan:

L←⎕ prompt for screen input of L

s←⎕,/ prompt for screen input of s and create nested vector of successive s elements of L

(⍴L)↑¨ pad each element of the nested vector with zeros to the length of L

(1-⍳⍴z)⌽¨ incrementally rotate each element of the nested vector

+/ sum the elements of the nested vector
Graham
sumber
1

K (oK) , 30 byte

Larutan:

{+/t,'(y':x),'|t:(!1-y-#x)#'0}

Cobalah online!

Contoh:

{+/t,'(y':x),'|t:(!1-y-#x)#'0}[3 -6 -9 19 2 0;2]
3 -12 -18 38 4 0

Penjelasan:

Jangan berpikir saya bisa bersaing dengan J yang satu ini. Buat daftar nol untuk ditambahkan dan ditambahkan ke daftar jendela geser, kemudian jumlahkan:

{ t,'(y':x),'|t:(!(#x)+1-y)#'0 }[1 2 3 4 5 6 7 8 9;3]
(1 2 3 0 0 0 0 0 0
 0 2 3 4 0 0 0 0 0
 0 0 3 4 5 0 0 0 0
 0 0 0 4 5 6 0 0 0
 0 0 0 0 5 6 7 0 0
 0 0 0 0 0 6 7 8 0
 0 0 0 0 0 0 7 8 9)

Rinciannya adalah sebagai berikut ... meskipun ini masih terasa canggung.

{+/t,'(y':x),'|t:(!1-y-#x)#'0} / the solution
{                            } / lambda taking x and y implicitly
                          #'0  / take (#) each (') zero
                 (       )     / do this together
                       #x      / count (#) length of x
                     y-        / take count away from length y
                   1-          / take that result from 1
                  !            / til, generate range to that number
               t:              / save in variable t
              |                / reverse it
            ,'                 / join with each
      (y':x)                   / sliding window size y over x
    ,'                         / join with each
   t                           / prepend t
 +/                            / sum up
streetster
sumber
1

Sekam , 4 byte

mΣ∂X

Cobalah online!

Menggunakan ide dari jawaban J Galen Ivanov .

Penjelasan

     -- implicit input number n and list s, e.g. s = [1,2,3,4,5,6] and n = 4 
   X -- get sublists of length n of list s           [[1,2,3,4],[2,3,4,5],[3,4,5,6]]
  ∂  -- anti-diagonals                               [[1],[2,2],[3,3,3],[4,4,4],[5,5],[6]]
mΣ   -- get the sum of each of the lists             [1,4,9,12,10,6]
Laikoni
sumber
0

C (gcc) , 100 byte

j,x;f(L,l,s)int*L;{for(j=0;j<l;j++)L[j]*=j<s&j<l-s?-~j:j>s&j>l-s?l-j:(x=s<l-j?s:l-j)<l-~-s?x:l-~-s;}

Cobalah online!

Jonathan Frech
sumber
0

Python 2 , 68 66 byte

-2 byte terima kasih kepada Laikoni

lambda l,n:[v*min(n,i+1,len(l)-max(i,n-1))for i,v in enumerate(l)]

Cobalah online!

ovs
sumber
max(i,n-1)bukannya [i,n-1][n>i].
Laikoni
0

C (gcc) , 83 81 79 byte

Pada dasarnya ada tiga "fase" untuk manipulasi daftar: ramp-up, sustain, dan cool-off. Saat kita masuk dalam daftar, kita akan meningkatkan faktor kita sampai kita mencapai beberapa maksimum. Jika irisan penuh dapat masuk ke dalam daftar, maksimum ini akan sama dengan panjang irisan. Jika tidak, itu akan sama dengan jumlah irisan yang sesuai. Di ujung yang lain, kita akan mengurangi faktor lagi, menjadi 1 pada elemen terakhir.

Panjang fase ramp-up dan cool-down yang menunjukkan dataran tinggi ini adalah satu kurang dari faktor maksimum.

Loop yang tidak diserami sebelum menggabungkannya diharapkan membuatnya lebih jelas (R = panjang fase ramp-up):

for (r = 1; r <= R; r++) L[r - 1] *= r;
for (; r < n - R; r++)   L[r - 1] *= R + 1;
for (; r < n; r++)       L[r - 1] *= n - r + 1;

Tiga loop terlalu banyak, jadi menentukan faktor berdasarkan r memberi kita satu loop (menggunakan s untuk R untuk menyimpan beberapa byte):

r;f(L,n,s)int*L;{for(r=0,s=2*s-1>n?n-s:s-1;r++<n;)*L++*=r>s?r<n-s?s+1:n-r+1:r;}

Cobalah online!

gastropner
sumber
0

Perl, 45 44 byte

Termasuk +4 untuk -ai Juga perhatikan bahwa kode ini memberikan 2 peringatan perl saat startup. Anda dapat menekan ini dengan biaya satu pukulan dengan menambahkan Xopsi

Berikan panjang mask setelah -iopsi dan array pada satu baris di STDIN:

perl -ai4 -E 'say$_*grep$_~~[$^I..@F],$a..$^I+$a++for@F' <<< "1 3 12 100 23"

Hanya kode:

say$_*grep$_~~[$^I..@F],$a..$^I+$a++for@F
Ton Hospel
sumber
0

Ruby , 62 byte

->a,l{a.map.with_index{|x,i|x*[i+1,l,a.size-[l-1,i].max].min}}

Cobalah online!

Pada dasarnya port jawaban javascript Arnauld , kecuali bahwa kebutuhan with_indexjauh lebih menyakitkan.

Dalam waktu yang dibutuhkan bagi saya untuk memutuskan untuk benar-benar mengirimkan ini, saya bermain golf dari versi 70-byte ini, yang lebih dekat dengan algoritma Dennis .

->a,l{c=a.map{0};(0...a.size).each_cons(l){|h|h.map{|i|c[i]+=a[i]}};c}
benj2240
sumber
0

Clojure, 72 byte

#(let[R(range 1(inc(count %)))](map *(map min(repeat %2)R(reverse R))%))
NikoNyrh
sumber
0

Pyt , 106 byte

ĐŁĐ←⇹řĐ↔Đ04ȘĐ04Ș>Đ04Ș03Ș¬*07ȘážÁ*+04Ș⇹Đ3ȘĐ3Ș-⁺Đ4Ș⇹ŕĐ3Ș<Ь3Ș*3Ș*+⇹ĐŁ⑴04Ș3Ș⇹04Ș*Đ04ȘĐ04Ș<Đ04Ș*06ȘážÁ03Ș¬*++*

Mengambil L pada baris pertama sebagai array, dan mengambil s pada baris kedua

Penjelasan:

                     Implicit input (L)
Đ                    Duplicate L
ŁĐ                   Get length of L (len) and push it twice
←                    Get s
⇹ř                   Push [1,2,...,len]
Đ↔Đ                  Push [len,...,2,1] twice
04ȘĐ                 Push 0, flip top 4 on stack, and duplicate top [1,2,...,len]
04Ș>                 Is [len,...,2,1]>[1,2,...,len] (element-wise) [boolean array]
Đ                    Duplicate top of stack                   
04Ș03Ș¬*             Pushes [1,2,...,ceil(len/2),0,...,0]
07ȘážÁ               Push 0, flip top seven on stack, and remove all 0s from stack
*                    Pushes [0,0,...,0,floor(len/2),floor(len/2)-1,...,1]
+                    Adds top two on stack element-wise

The top of the stack is now:
     [1,2,...,ceil(len/2),floor(len/2),...,2,1] (let's call it z)

04Ș                  Push zero and swap top four on stack
⇹                    Swap top two on stack
Đ3ȘĐ3Ș-⁺Đ4Ș⇹ŕĐ3Ș<Ь3Ș*3Ș*+     Pushes min of (len-s+1,s) [let's call it m]
⇹ĐŁ⑴04Ș3Ș⇹04Ș*                Pushes an array [m,m,...,m] with length len
Đ04ȘĐ04Ș<Đ04Ș*06ȘážÁ03Ș¬*++    Pushes element-wise min of [m,m,...,m] and z
*                              Element-wise multiplication of above with L

Cobalah online!

mudkip201
sumber
0

Python + numpy, 64 byte

from pylab import *
lambda l,N:convolve(*ones((2,len(l)-N-1)))*l

Sebut ini dengan l sebagai daftar, dan N sebagai panjangnya.

pengguna2699
sumber