Spaltenweise Summierung überlappender Schichten

19

Aufgabe

Ausgehend von einer Liste von ganzen Zahlen L und einer anderen ganzen Zahl s besteht das Ziel darin, die spaltenweisen Summen aller (möglicherweise überlappenden) Schichten mit der Länge s von L zu berechnen , während ihre Positionen in Bezug auf L angegeben werden (siehe unten).

Definitionen

Die s- Länge (überlappende) Schichten der Liste L sind alle zusammenhängenden Teilfolgen (ohne Umbruch) von L , die die Länge s haben .

Um die Positionen der Slices s relativ zu L zu bestimmen , können Sie sich vorstellen, eine "Leiter" zu bauen, in der jedes Slice s i von Anfang an einen Versatz von i Positionen hat.


Technische Daten

  • s eine ganze Zahl größer als 1 und streng kleiner als die Länge L .
  • L enthält immer mindestens 3 Elemente.
  • Sie können in jeder Programmiersprache antreten und über jede Standardmethode Eingaben und Ausgaben vornehmen. Beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind. Dies ist , daher gewinnt die kürzeste Übermittlung (in Bytes) für jede Sprache .

Beispiele und Testfälle

Hier ist ein Beispiel:

[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]

Und noch ein paar Testfälle:

[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]
Mr. Xcoder
quelle
2
Dieser erste Testfall ist nervig. ;) Einfach weil sgrößer ist als L/2. Vielleicht noch ein paar Testfälle hinzufügen, in denen dies der Fall ist [1, 1, 1, 1, 1, 1, 1], 6 -> [1, 2, 2, 2, 2, 1] `oder [1, 2, 3, 4, 5, 6, 7, 8, 9], 6 -> [1, 4, 9, 16, 20, 24, 21, 16, 9]?
Kevin Cruijssen
2
@KevinCruijssen Kannst du dich bitte für mich anmelden? Das sind ein paar gute Testfälle, aber ich bin jetzt auf dem Handy;) Danke!
Mr. Xcoder

Antworten:

11

J , 11, 9 8 Bytes

-1 Byte dank Meilen!

[:+//.]\

Wie es funktioniert?

Das linke Argument ist s, das rechte - L

]\ - teilt L in Unterlisten mit der Länge s

/. - extrahiert die schrägen Diagonalen (Antidiagonalen)

+/ - summiert sie auf

[: - macht eine Gabelung aus den oben genannten Verben

Hier ist ein Beispiel für eine J-Sitzung für den ersten Testfall:

   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

Probieren Sie es online!

Galen Ivanov
quelle
Gibt es einen Unterschied zwischen einer "schrägen Diagonale" und einer "Diagonale"?
Luis Mendo
@ Luis Mendo - Ich denke, "schräg" bedeutet im Fall des J-Adverbs von links nach rechts /., im Gegensatz zur Hauptdiagonale von links nach rechts nach oben.
Galen Ivanov
1
Ah danke. Das nennt man normalerweise Antidiagonale
Luis Mendo
2
Sie könnten ,/\mit]\
Meilen
@miles Ja natürlich! Vielen Dank!
Galen Ivanov
9

Haskell , 59 56 Bytes

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

Probieren Sie es online!

Definiert eine Funktion (#) die eine Liste sund eine Nummer annimmtn als Argumente verwendet.

Dies basiert auf der Beobachtung, dass für s = [1, 2, 3, 4, 5, 6, 7, 8, 9]undn = 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]

ist das gleiche wie

[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]

Um diese zunächst ansteigende, dann konstante und schließlich absteigende Liste zu generieren, können wir mit beginnen

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

was ergibt [1, 2, 3, 4, 5, 4, 3, 2, 1]. Das Hinzufügen einer nzusätzlichen Einschränkung zum minimumAusdruck ergibt die richtige [1, 2, 3, 3, 3, 3, 3, 2, 1]Listenantwort für n = 3, obwohl für n = 6(oder allgemein für n > lengths s/2) die zusätzliche Einschränkung length s + 1 - nerforderlich ist:

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

oder kürzer:

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

Für die paarweise Multiplikation [1..length s]wird mit gezippt s, und da zipdie längere Liste auf die Länge der kürzeren Liste gekürzt wird, [1..]kann die unendliche Liste verwendet werden:

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

JavaScript (ES6), 65 62 58 Byte

4 Bytes gespart dank @Shaggy

Übernimmt Eingaben in der Currying-Syntax (a)(n).

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

Testfälle

Arnauld
quelle
Funktioniert das a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i)))für 58 Bytes?
Shaggy
@Shaggy Irgendwie wusste ich, dass mein Code etwas wirklich Dummes enthält, konnte es aber nicht herausfinden ... Vielen Dank!
Arnauld
6

Java 8, 83 Bytes

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

Dieser erste Testfall (und die letzten beiden, die ich hinzugefügt habe) haben mich mehrmals durcheinander gebracht, aber jetzt funktioniert es endlich.: D

Ändert das Eingabearray, anstatt ein neues zurückzugeben.

Erläuterung:

Probieren Sie es online aus.

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
quelle
5

MATL , 8 Bytes

YCPT&Xds

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Betrachten Sie Eingaben [1, 3, 12, 100, 23]und 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
quelle
5

APL (Dyalog Unicode) , 19 14 Byte SBCS

-5 danke an ngn.

Anonyme implizite Infix-Funktion, bei der s als linkes Argument und L als rechtes Argument verwendet werden. Geht davon aus ⎕IO( I ndex O Rigin) wird 0als Standard auf vielen Systemen ist.

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

Probieren Sie es online!

Erklärung mit Beispielfall [1,3,12,100,23]

() Wenden folgende anonyme stillschweigende Funktion an:

,/ überlappende Fenster dieser Größe; [[1,3,12],[3,12,100],[12,100,23]]

()\ Kumulativ diese stillschweigende folgende anonyme stillschweigende Funktion anwenden:

   das richtige (die meisten) Argument

  0, mit einer Null auf der linken Seite

Kumulative Reduktion bedeutet, dass wir die Funktion in jeden "Raum" zwischen aufeinanderfolgenden Begriffen einfügen und von rechts nach links arbeiten. Für jedes "Leerzeichen" verwirft die Funktion das linke Argument, fügt jedoch eine zusätzliche Null hinzu. Tatsächlich werden so viele Nullen an jeden Term angehängt, wie links davon "Leerzeichen" stehen, sodass der erste Term null Leerzeichen erhält, der zweite eins und der dritte zwei:[[1,3,12],[0,3,12,100],[0,0,12,100,23]]

 Erhöhen Sie den Rang, indem Sie die Listen in einer einzigen Matrix zusammenfassen und mit Nullen auffüllen.
┌ ┐
│1 3 12 0 0│
│0 3 12 100 0│
│0 0 12 100 23│
└ ┘
 dann
+⌿ summiere vertikal;[1,6,36,200,23]

Adam
quelle
1
⊢,⍨¨0⍴⍨¨⍳∘≢->{0,⍵}\
ngn
@ngn Du denkst immer an diese cleveren Reduzierungen, aber das solltest du wirklich separat posten. Übrigens finde ich +⌿∘↑((0,⊢)\,/)eleganter.
Adám
Ach komm schon, dies ist ein klarer Fall der Vereinfachung eines Teils einer Lösung, keine neue Idee
ngn
@ngn In der Zwischenzeit löse diese CMC!
Adám
Ich bin mir nicht sicher, ob dies in den Kommentaren hier zum Thema gehört, aber warum verwenden Sie nicht "each"? 2{(⊃⌽⍺),⊃⍵}/⊢->2{⊃¨(⌽⍺)⍵}/⊢
ngn
4

Gelee , 6 Bytes

JṡṬS×ḷ

Probieren Sie es online!

Wie es funktioniert

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
quelle
3

Japt , 13 Bytes

Es hat viel zu lange gedauert, bis dies funktionierte, als s> L/2!

Ë*°EmVUÊÄ-EwV

Versuch es


Erläuterung

                 :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
Zottelig
quelle
" Es hat viel zu lange gedauert, bis das funktioniert, wenn s > L/2! " Ich hatte genau das gleiche. Die anderen Testfälle sind einfach, aber der erste (und die beiden, die ich am Ende hinzugefügt habe) waren nervig! .. +1 von mir!
Kevin Cruijssen
1

R , 52 51 Bytes

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

Probieren Sie es online!

Dies entspricht der Antwort von Laikoni .

seq(l)produziert die Indizes 1...length(l)seit length(l)>1(sonst würde es produzieren 1...l[1]). Ich speichere es als x, speichere sein Gegenteil als yund nehme das erste Element von y(length(l) ), um Laikonis Antwort ordentlich zu portieren und ein Byte zu speichern!

Ursprüngliche Antwort, 52 Bytes

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

Probieren Sie es online!

Der Ausgang wird lelementweise durch die mindestens multipliziert s, der 1 basierten Index des Elements x, length(l)-x+1und length(L)-s+1.

Dies ist auch gleichbedeutend mit Laikonis Antwort und verwendet L-xstatt rev(x)wie es kürzer ist.

Giuseppe
quelle
1

APL + WIN, 25 Bytes

Fordert zur Eingabe von L gefolgt von s auf

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

Erläuterung:

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

K (oK) , 30 Bytes

Lösung:

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

Probieren Sie es online!

Beispiel:

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

Erläuterung:

Glaube nicht, dass ich in dieser Sache mit J mithalten kann . Generieren Sie eine Liste mit Nullen, die an die Liste der Schiebefenster angehängt und ihnen vorangestellt werden sollen, und fassen Sie dann Folgendes zusammen:

{ 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)

Die Aufteilung ist wie folgt ... obwohl sich dies immer noch ungeschickt anfühlt.

{+/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
quelle
1

Schale , 4 Bytes

mΣ∂X

Probieren Sie es online!

Verwendet die Idee aus Galen Ivanovs J-Antwort .

Erläuterung

     -- 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
quelle
0

Python 2 , 68 66 Bytes

-2 Bytes dank Laikoni

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

Probieren Sie es online!

ovs
quelle
max(i,n-1)statt [i,n-1][n>i].
Laikoni
0

C (GCC) , 83 81 79 Bytes

Grundsätzlich gibt es drei "Phasen" bei der Bearbeitung der Liste: Hochfahren, Halten und Abkühlen. Wenn wir die Liste durchgehen, werden wir unseren Faktor erhöhen, bis wir ein Maximum erreicht haben. Wenn eine vollständige Reihe von Slices in die Liste passen kann, entspricht dieses Maximum der Länge der Slices. Andernfalls entspricht dies der Anzahl der passenden Slices. Am anderen Ende verringern wir den Faktor erneut, um beim letzten Element auf 1 zu landen.

Die Länge der Hochlauf- und Abkühlphasen, die dieses Plateau belegen, liegt um einen Faktor unter diesem Maximalwert.

Die ungolfed Schleifen vor dem Kombinieren machen es hoffentlich klarer (R = Länge der Hochlaufphase):

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;

Drei Schleifen sind viel zu viel. Wenn Sie also den Faktor basierend auf r bestimmen, erhalten Sie die eine Schleife (verwenden Sie s für R, um einige Bytes zu sparen):

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

Probieren Sie es online!

Gastropner
quelle
0

Perl, 45 44 Bytes

Enthält +4 für. Beachten Sie -ai außerdem, dass dieser Code beim Start 2 Perl-Warnungen ausgibt. Sie können diese auf Kosten eines Strichs unterdrücken, indem Sie die XOption hinzufügen

Geben Sie die -iMaskenlänge nach der Option und das Array in einer Zeile in STDIN an:

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

Nur der Code:

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

Ruby , 62 Bytes

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

Probieren Sie es online!

Im Grunde genommen eine Portierung von Arnauld's Javascript-Antwort , mit der Ausnahme, dass das Benötigen with_indexviel schmerzhafter ist.

In der Zeit, die ich brauchte, um mich zu entscheiden, dies tatsächlich einzureichen, habe ich mich von dieser 70-Byte-Version verabschiedet, die Dennis 'Algorithmus näher kommt .

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

Clojure, 72 Bytes

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

Pyt , 106 Bytes

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

Nimmt L in der ersten Zeile als Array und s in der zweiten Zeile

Erläuterung:

                     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

Probieren Sie es online!

mudkip201
quelle
0

Python + Numpy, 64 Bytes

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

Nennen Sie dies mit l als Liste und N als Länge.

user2699
quelle