2D unterteilte kumulative Summe

16

Herausforderung

Gegeben sei eine Matrix M mit r Zeilen und c Spalten und zwei Booleschen Listen V der Länge r und H der Länge c die unterteilten kumulativen vertikalen und horizontalen Summen.

Regeln

  • r und c sind größer als oder gleich eins

  • H und V beginnen mit einem wahren Wert

  • Die Werte in M liegen im angemessenen numerischen Bereich Ihrer Sprache.

  • Partitionierung und Summierung beginnen in der oberen linken Ecke.

Gehen Sie durch

Gegeben M :

┌──────────────┐
│ 1  2  3  4  5│
│ 6  7  8  9 10│
│11 12 13 14 15│
│16 17 18 19 20│
└──────────────┘

H :1 0 1 0 0

V :1 1 0 1

Teilen Sie M in Spaltengruppen auf und beginnen Sie eine neue Gruppe bei jedem wahren Wert von H

┌─────┬────────┐
│ 1  2│ 3  4  5│
│ 6  7│ 8  9 10│
│11 12│13 14 15│
│16 17│18 19 20│
└─────┴────────┘

Teilen Sie jede Gruppe von Spalten in Gruppen von Zeilen auf und beginnen Sie eine neue Gruppe bei jedem wahren Wert von V :

┌─────┬────────┐
│ 1  2│ 3  4  5│
├─────┼────────┤
│ 6  7│ 8  9 10│
│11 12│13 14 15│
├─────┼────────┤
│16 17│18 19 20│
└─────┴────────┘

Summiere jede Zelle horizontal:

┌─────┬────────┐
│ 1  3│ 3  7 12│
├─────┼────────┤
│ 6 13│ 8 17 27│
│11 23│13 27 42│
├─────┼────────┤
│16 33│18 37 57│
└─────┴────────┘

Summiere jede Zelle vertikal:

┌─────┬────────┐
│ 1  3│ 3  7 12│
├─────┼────────┤
│ 6 13│ 8 17 27│
│17 36│21 44 69│
├─────┼────────┤
│16 33│18 37 57│
└─────┴────────┘

Ergebnis:

┌──────────────┐
│ 1  3  3  7 12│
│ 6 13  8 17 27│
│17 36 21 44 69│
│16 33 18 37 57│
└──────────────┘

Zusätzliche Testfälle

M :

┌───────────┐
│15 11 11 17│
│13 20 18  8│
└───────────┘

H : 1 0 0 1V :1 0

Ergebnis:

┌───────────┐
│15 26 37 17│
│28 59 88 25│
└───────────┘

M :

┌─┐
│7│
└─┘

Ergebnis ( H und V müssen sein 1):

┌─┐
│7│
└─┘

M :

┌──┐
│ 3│
│-1│
│ 4│
└──┘

V : 1 1 0( H muss sein 1)

Ergebnis:

┌──┐
│ 3│
│-1│
│ 3│
└──┘

M :

┌───────────────────────────────────────────────────────┐
│10    7.7 1.9 1.5 5.4  1.2 7.8 0.6 4.3 1.2  4.5 5.4 0.3│
│ 2.3  3.8 4.1 4.5 1    7.7 3   3.4 6.9 5.8  9.5 1.3 7.5│
│ 9.1  3.7 7.2 9.8 3.9 10   7.6 9.6 7.3 6.2  3.3 9.2 9.4│
│ 4.3  4.9 7.6 2   1.4  5.8 8.1 2.4 1.1 2.3  7.3 3.6 6  │
│ 9.3 10   5.8 9.6 5.7  8.1 2.1 3.9 4   1.3  6.3 3.1 9  │
│ 6.6  1.4 0.5 6.5 4.6  2.1 7.5 4.3 9   7.2  2.8 3.6 4.6│
│ 1.7  9.9 2.4 4.5 1.3  2.6 6.4 7.8 6.2 3.2 10   5.2 8.9│
│ 9.9  5.3 4.5 6.3 1.4  3.1 2.3 7.9 7.8 7.9  9.6 4   5.8│
└───────────────────────────────────────────────────────┘

H :1 0 0 1 0 1 1 1 0 1 1 1 0

V :1 0 0 0 0 1 0 0

Ergebnis:

┌────────────────────────────────────────────────────────────────┐
│10   17.7 19.6  1.5  6.9  1.2  7.8  0.6  4.9  1.2  4.5  5.4  5.7│
│12.3 23.8 29.8  6   12.4  8.9 10.8  4   15.2  7   14    6.7 14.5│
│21.4 36.6 49.8 15.8 26.1 18.9 18.4 13.6 32.1 13.2 17.3 15.9 33.1│
│25.7 45.8 66.6 17.8 29.5 24.7 26.5 16   35.6 15.5 24.6 19.5 42.7│
│35   65.1 91.7 27.4 44.8 32.8 28.6 19.9 43.5 16.8 30.9 22.6 54.8│
│ 6.6  8    8.5  6.5 11.1  2.1  7.5  4.3 13.3  7.2  2.8  3.6  8.2│
│ 8.3 19.6 22.5 11   16.9  4.7 13.9 12.1 27.3 10.4 12.8  8.8 22.3│
│18.2 34.8 42.2 17.3 24.6  7.8 16.2 20   43   18.3 22.4 12.8 32.1│
└────────────────────────────────────────────────────────────────┘
Adam
quelle

Antworten:

9

Gelee , 10 Bytes

Zœṗ@+\€Ẏð/

Probieren Sie es online! und der letzte Testfall (mit aG am Ende für die Lesbarkeit).

Die Eingabe wird als Liste übernommen [M, H, V] .

Erläuterung

Zœṗ@+\€Ẏð/  Input: [M, H, V]
        ð/  Insert the previous (f) as a dyadic link
            Forms f( f(M, H) , V)
            For f(x, y):
Z             Transpose x
 œṗ@          Partition the rows of x^T at each true in y
    +\€       Compute the cumulative sums in each partition
       Ẏ      Tighten (Joins all the lists at the next depth)
Meilen
quelle
Sie können eine Fußzeile wie diese verwenden, damit Sie Ihren tatsächlichen Code nicht manipulieren müssen.
Erik der Outgolfer
7

APL (Dyalog) , 13 Bytes

Nimmt ist von VHM als Argument.

{⍉⊃,/+\¨⍺⊂⍵}/

Probieren Sie es online!

{}/ Fügen Sie die folgende anonyme Funktion ein (reduzieren um), wobei der Term links durch term und der Term rechts durch ⍵ dargestellt wird. Da APL-Funktionen rechtsassoziativ sind, ist dies daher V f ( H f M ).

⍺⊂⍵ Partition ⍵ nach ⍺

+\¨ kumulative Summe jedes Teils

,/ durch Verkettung reduzieren (dies schließt das Ergebnis ein, um den Rang zu reduzieren)

 offenbaren

 transponieren

Adam
quelle
6

Python 2 + Anzahl, 143 138 117 115 110 108 Bytes

-21 Bytes dank Adám !

lambda M,*L:reduce(lambda m,l:vstack(map(lambda p:cumsum(p,0),split(m,*where(l)))).T,L,M)
from numpy import*

Probieren Sie es online!

notjagan
quelle
1
Nach Partition fragen, teilen und einmal abspritzen, transponieren, wiederholen.
Adám
@ Adám Danke, ich habe aus irgendeinem Grund nicht daran gedacht.
Notjagan
Ich mochte die Liste Lookup von zwei Funktionen trotzdem :)
Jonathan Allan
2
Bitte machen Sie Header "Python 3 + Numpy"
Leaky Nun
5

Jelly ,  15 bis  14 Bytes

œṗ+\€Ẏ
ḢçЀZð⁺

Eine dyadische Verknüpfung, H,Vdie links und Mrechts aufnimmt und die resultierende Matrix zurückgibt.

Probieren Sie es online!

Alternativ als einfache Linie auch für 14: Ḣœṗ+\€Ẏ$¥Ð€Zð⁺

Wie?

œṗ+\€Ẏ - Link 1: partition and cumSum: list of partition bools, list of values
œṗ     - partition (the values) at truthy indexes (of the bools)
    €  - for €ach part:
  +\   -   cumulative reduce by addition
     Ẏ - tighten (flattens back into a list)

ḢçЀZð⁺ - Main link: list of lists, [H,V]; list of lists, M
      ⁺ - perform this twice:
     ð  - [it's a dyadic chain for the second pass, first pass is dyadic implicitly]
Ḣ       -   head, pop it & modify (so H the first time, V the second)
  Ѐ    -   map across right: (M the first time, the intermediate result the second)
 ç      -     the last link (1) as a dyad
    Z   -   transpose the result (do the rows first time, and the columns the second)

Bisherige:

œṗ@+\€Ẏ
ç€Zç€⁵Z

Ein vollständiges Programm, das eine Darstellung des Ergebnisses druckt.

Jonathan Allan
quelle
Whoa -50% von der vorherigen Gelee-Antwort!
Adám
Whoa was? Beeindruckend. Ich muss wirklich lernen, wie du das gemacht hast ... Unglaublich im Vergleich zu meinem!
HyperNeutrino
Oh, das macht die beiden Richtungen getrennt, oder? Clever.
HyperNeutrino
Ich denke, es macht ungefähr das Gleiche ...
Jonathan Allan
Gute Methode. Das heißt, ich kann das mit APL schlagen. Ich habe 14 Bytes.
Adám
4

MATL , 19 Bytes

,!ix"0GYs@12XQ!g]v!

Eingaben sind M(Matrix), H(Spaltenvektor), V(Spaltenvektor). Das Zeilentrennzeichen ist; .

Probieren Sie es online! Oder überprüfen Sie alle Testfälle: 1 , 2 , 3 , 4 , 5 .

Erläuterung

Dies ergibt die kumulative Summe horizontal und dann vertikal.

,          % Do the following twice
  !        %   First time this inputs M implicitly. Transpose. Second time
           %   it transposes the result of the horizontal cumulative sum
  ix       %   Input H (first time) or V (second time). Delete it; but gets
           %   copied into clipboard G
  "        %   For each column of the matrix
    0G     %     Push most recent input: H (first time) or V (second)
    Ys     %     Cumulative sum. This produces a vector of integer values
           %     such that all columns (first time) or rows (second) of M 
           %     with the same value in this vector should be cumulatively
           %     summed
    @      %     Push current column of M transposed (first time) or M after
           %     horizontal cumulative sum (second time)
    12XQ   %     Cumulative sum. Gives a cell array of row vectors
    !g     %     Join those vectors into one row vector
  ]        %   End
  v        %   Concatenate the row vectors vertically into a matrix
  !        %   Transpose. This corrects for the fact that each column vector
           %   of the matrix was cumulatively summed into a row vector
           % Implicit end. Implicit display
Luis Mendo
quelle
1
Am beeindruckendsten. Ich denke, Matlab war irgendwie für solche Sachen gemacht.
Adám
@ Adám Ich bin sicher, dass die Länge von APL nicht sehr unterschiedlich sein wird :-)
Luis Mendo
Meine Referenzimplementierung, die zum Generieren der Testfälle verwendet wird, ist 26 Byte.
Adám
@ Adám Darn! APL gegen Jelly? Das ist inakzeptabel! (muss meine Lösung Golf ... lol) xD
HyperNeutrino
@HyperNeutrino Nun, Jelly hat nicht den gleichen Rang und die gleiche Tiefe wie APL und J.
Adám
3

J , 20 Bytes

;@(<@(+/\);.1|:)&.>/

Probieren Sie es online!

Die Eingabe wird als ein Array von Feldern verstanden, die Folgendes enthalten [V, H, M].

Erläuterung

;@(<@(+/\);.1|:)&.>/  Input: [V H M]
  (     g      )   /  Insert g and reduce (right-to-left)
                      Forms V g H g M = V g (H g M)
                & >     Unbox each
             |:         Transpose the right arg
          ;.1           Partition
      +/\               Reduce each prefix using addition (cumulative sum)
   <@                   Box each partition
;@                      Raze (Concatenate the contents in each box)
                &.>     Box the result
Meilen
quelle
2

Mathematica, 212 Bytes

(T=Transpose;A=AppendTo;J=Flatten;f[s_]:=Block[{},t=2;r=1;w={};While[t<=Length@s,If[s[[t]]==0,r++,w~A~r;r=1];t++];w~A~r];K[x_,y_]:=Accumulate/@#&/@(FoldPairList[TakeDrop,#,f@y]&/@x);d=J/@K[#,#2];T[J/@K[T@d,#3]])&


Eingabe
[M, H, V]

[{{15, 11, 11, 17}, {13, 20, 18, 8}}, {1, 0, 0, 1}, {1, 0}]

J42161217
quelle
2

C # (.NET Core) , 164 Byte

(M,H,V)=>{int a=M.Length,b=M[0].Length,i,j;for(i=0;i<a;i++)for(j=0;j<b;j++)if(!H[j])M[i][j]+=M[i][j-1];for(i=0;i<a;i++)for(j=0;j<b;j++)if(!V[i])M[i][j]+=M[i-1][j];}

Probieren Sie es online!

Grundsätzlich geht es genau so, wie es im OP festgelegt ist. Es iteriert zuerst, um horizontal zu summieren, und iteriert dann erneut, um vertikal zu summieren.

Charlie
quelle
2

Haskell , 129 Bytes 119 Bytes

s m v=tail$scanl(\a(x,s)->if s then x else zipWith(+)a x)[](zip m v)
t=foldr(zipWith(:))$repeat[]
f m h v=t$s(t$s m v)h

Probieren Sie es online!

Dank @ceasedtoturncounterclockwis 10 Byte gespart

t(für transponieren) wechselt Zeilen und Spalten. Eine kurze Erklärung:

foldr(zipWith(:))(repeat[])(r1,...,rn) =
zipWith(:) r1 (zipWith(:) r2 (... zipWith(:) rn (repeat [])))

Lesen Sie von rechts nach links: Wir durchsuchen die Zeilen von unten nach oben und verschieben jeden Wert in seine Zielspalte.

s ist im Grunde eine fortlaufende Summe von Vektoren, wird jedoch zurückgesetzt, wenn ein wahrer Wert in entsteht v

fsummiert die Zeilen mit dem sFolgenden vund macht dasselbe mit den folgenden Spaltenh

jferard
quelle
t=foldr(zipWith(:))(repeat[]). Nicht nur kürzer, sondern auch weniger ineffizient.
aufgehört, gegen den Uhrzeigersinn
@ceasedtoturncounterclockwis Danke für den Tipp.
jferard
1

JavaScript (ES6), 88 Byte

(a,h,v)=>a.map(b=>b.map((e,i)=>t=h[i]?e:t+e)).map((b,j)=>t=v[j]?b:t.map((e,i)=>e+b[i]))
Neil
quelle
0

Gelee , 31 Bytes

+\€€
œṗḊZ€⁵œṗ$€Ḋ€Ç€ÇZ€€Z€;/€€;/

Probieren Sie es online!

Gah, das ist für Jelly xD viel zu lang

Übrigens bestehen 11/31 Bytes in diesem Programm aus Euro-Zeichen. Das ist mehr als ein Drittel des Programms!

HyperNeutrino
quelle
Zu viele Euros.
Adám
@ Adám Genau meine Gedanken: P Das Arbeiten mit doppelt partitionierten Matrizen macht nicht so viel Spaß, wie ich es mir vorgestellt habe, da ich xD
HyperNeutrino 26.07.17
Warum verschwenden Sie Ihr Geld so € - €
V. Courtois