2D partitioned cumulative sum

Question

Challenge

Given a matrix M with r rows and c columns, and two Boolean lists V of length r and H of length c, calculate the partitioned cumulative vertical and horizontal sums.

Rules

r and c are greater than or equal to one
H and V begin with a true value
The values in M are within your language's reasonable numeric domain.
Partitioning and summing begins in the top left corner.

Walk through

Given 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

Split M into groups of columns, beginning a new group at every true value of H

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

Split each group of columns into groups of rows, beginning a new group at every true value of V:

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

Cumulatively sum each cell horizontally:

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

Cumulatively sum each cell vertically:

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

Result:

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

Additional test cases

M:

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

H: 1 0 0 1 V: 1 0

Result:

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

M:

┌─┐ │7│ └─┘

Result (H and V must be 1):

┌─┐ │7│ └─┘

M:

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

V: 1 1 0 (H must be 1)

Result:

┌──┐ │ 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

Result:

┌────────────────────────────────────────────────────────────────┐ │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│ └────────────────────────────────────────────────────────────────┘

miles · Accepted Answer · 2017-07-27 03:59:14Z

Jelly, 10 bytes

Zœṗ@+\€Ẏð/

Try it online! and The Last Test Case (With a G at the end for readability).

Input is taken as a list [M, H, V].

Explanation

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)

You can use a footer like this so that you don't have to tamper with your actual code. — Erik the Outgolfer
– Erik the Outgolfer, Commented Jul 27, 2017 at 13:14

Adám · Accepted Answer · 2017-07-27 08:45:24Z

APL (Dyalog), 13 bytes

Takes ist of V H M as argument.

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

Try it online!

{…}/ insert (reduce by) the following anonymous function, where the term in the left is represented by ⍺ and the term on the right is represented by ⍵. Due to APL functions being right associative, this is therefore V f (H f M).

⍺⊂⍵ partition ⍵ according to ⍺

+\¨ cumulative sum of each part

,/ reduce by concatenation (this encloses the result to reduce rank)

⊃ disclose

⍉ transpose

notjagan · Accepted Answer · 2017-07-27 12:55:52Z

6

Python 2 + numpy, 143 138 117 115 110 108 bytes

^{-21 bytes thanks to 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*

Try it online!

edited Jul 27, 2017 at 12:55

answered Jul 27, 2017 at 0:20

notjagan

4,21110 silver badges27 bronze badges

1

\$\begingroup\$ ask for partition, split, and cumsum once, transpose, repeat. \$\endgroup\$

Adám
– Adám

2017-07-27 00:22:16 +00:00
Commented Jul 27, 2017 at 0:22
\$\begingroup\$ @Adám Thanks, I didn't think of that for some reason. \$\endgroup\$

notjagan
– notjagan

2017-07-27 00:29:54 +00:00
Commented Jul 27, 2017 at 0:29
\$\begingroup\$ I liked the list lookup of two functions anyway :) \$\endgroup\$

Jonathan Allan
– Jonathan Allan

2017-07-27 00:30:16 +00:00
Commented Jul 27, 2017 at 0:30
2

\$\begingroup\$ Please make header "Python 3 + numpy" \$\endgroup\$

Leaky Nun
– Leaky Nun

2017-07-27 04:26:30 +00:00
Commented Jul 27, 2017 at 4:26

Add a comment |

Jonathan Allan · Accepted Answer · 2017-07-27 00:24:56Z

Jelly, 15 14 bytes

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

A dyadic link taking H,V on the left and M on the right and returning the resulting matrix.

Try it online!

Alternatively as a single line also for 14: Ḣœṗ+\€Ẏ$¥Ð€Zð⁺

How?

œṗ+\€Ẏ - 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)

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

A full program printing a representation of the result.

Whoa what? Wow. I really need to study how you did this... Incredible compared to mine! — hyperneutrino
– hyperneutrino ♦, Commented Jul 26, 2017 at 23:40
Oh this is doing the two directions separately, right? Smart. — hyperneutrino
– hyperneutrino ♦, Commented Jul 26, 2017 at 23:41
Good method. Means I can beat this with APL. I've got 14 bytes. — Adám
– Adám, Commented Jul 26, 2017 at 23:50

Luis Mendo · Accepted Answer · 2017-07-27 00:01:43Z

MATL, 19 bytes

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

Inputs are M (matrix), H (column vector), V (column vector). The row separator is ;.

Try it online! Or verify all test cases: 1, 2, 3, 4, 5.

Explanation

This does the cumulative sum horizontally, then vertically.

, % 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

Most impressive. I guess Matlab was kinda made for stuff like this. — Adám
– Adám, Commented Jul 26, 2017 at 23:29
My reference implementation used to generate the test cases is 26 bytes. — Adám
– Adám, Commented Jul 26, 2017 at 23:35
@Adám Darn! APL beating Jelly? This is unacceptable! (must golf my solution... lol) xD — hyperneutrino
– hyperneutrino ♦, Commented Jul 26, 2017 at 23:37
@HyperNeutrino Well, Jelly doesn't have both rank and depth like APL and J have. — Adám
– Adám, Commented Jul 26, 2017 at 23:37

miles · Accepted Answer · 2017-07-27 04:03:19Z

J, 20 bytes

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

Try it online!

Input is taken as an array of boxes containing [V, H, M].

Explanation

;@(<@(+/\);.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

ZaMoC · Accepted Answer · 2017-07-27 04:09:47Z

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]])&

input
[M,H,V]

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

Charlie · Accepted Answer · 2017-07-27 07:04:07Z

C# (.NET Core), 164 bytes

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

Try it online!

Basically it does exactly as specified in the OP. It first iterates to sum horizontally and then it iterates again to sum vertically.

jferard · Accepted Answer · 2017-07-27 12:49:08Z

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

Try it online!

Saved 10 bytes thanks to @ceasedtoturncounterclockwis

t (for transpose) switches rows and columns. A quick explanation:

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

Read from right to left: we browse rows from bottom to up, and push each value in its destination column.

s is basically a rolling sum of vectors, but resets when a True value arises in v

f sums the rows with s following v and do the same with the columns following h

t=foldr(zipWith(:))(repeat[]). Not only shorter, also much less inefficient. — ceased to turn counterclockwis
– ceased to turn counterclockwis, Commented Jul 27, 2017 at 11:00

Neil · Accepted Answer · 2017-07-27 09:16:22Z

JavaScript (ES6), 88 bytes

(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]))

hyperneutrino · Accepted Answer · 2017-07-26 23:37:58Z

0

Jelly, 31 bytes

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

Try it online!

Gah this is way too long for Jelly xD

BTW, 11/31 bytes in this program consists of euro characters. That's over a third of the program!

edited Jul 26, 2017 at 23:37

answered Jul 26, 2017 at 23:30

hyperneutrino♦

42.8k5 gold badges72 silver badges227 bronze badges

\$\begingroup\$ Too many Euros. \$\endgroup\$

Adám
– Adám

2017-07-26 23:31:14 +00:00
Commented Jul 26, 2017 at 23:31
\$\begingroup\$ @Adám My thoughts exactly :P Working with doubly partitioned matrices isn't as fun as I thought it would be, because I'm doing second-level to third-level mapping xD \$\endgroup\$

hyperneutrino
– hyperneutrino ♦

2017-07-26 23:32:32 +00:00
Commented Jul 26, 2017 at 23:32
\$\begingroup\$ Why are you wasting your money like this €-€ \$\endgroup\$

V. Courtois
– V. Courtois

2017-07-27 07:53:43 +00:00
Commented Jul 27, 2017 at 7:53

Add a comment |

Stack Exchange Network

2D partitioned cumulative sum

Challenge

Rules

Walk through

Additional test cases

11 Answers 11

Jelly, 10 bytes

Explanation

APL (Dyalog), 13 bytes

Python 2 + numpy, 143 138 117 115 110 108 bytes

Jelly, 15 14 bytes

How?

MATL, 19 bytes

Explanation

J, 20 bytes

Explanation

Mathematica, 212 bytes

C# (.NET Core), 164 bytes

Haskell, 129 bytes 119 bytes

JavaScript (ES6), 88 bytes

Jelly, 31 bytes

Hot Network Questions

2D partitioned cumulative sum

Challenge

Rules

Walk through

Additional test cases

11 Answers 11

Jelly, 10 bytes

Explanation

APL (Dyalog), 13 bytes

Python 2 + numpy, 143 138 117 115 110 108 bytes

Jelly, 15 14 bytes

How?

MATL, 19 bytes

Explanation

J, 20 bytes

Explanation

Mathematica, 212 bytes

C# (.NET Core), 164 bytes

Haskell, 129 bytes 119 bytes

JavaScript (ES6), 88 bytes

Jelly, 31 bytes

Related

Hot Network Questions