16
\$\begingroup\$

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 1V: 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│
└────────────────────────────────────────────────────────────────┘
\$\endgroup\$

11 Answers 11

9
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ You can use a footer like this so that you don't have to tamper with your actual code. \$\endgroup\$ – Erik the Outgolfer Jul 27 '17 at 13:14
7
\$\begingroup\$

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

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ ask for partition, split, and cumsum once, transpose, repeat. \$\endgroup\$ – Adám Jul 27 '17 at 0:22
  • \$\begingroup\$ @Adám Thanks, I didn't think of that for some reason. \$\endgroup\$ – notjagan Jul 27 '17 at 0:29
  • \$\begingroup\$ I liked the list lookup of two functions anyway :) \$\endgroup\$ – Jonathan Allan Jul 27 '17 at 0:30
  • 2
    \$\begingroup\$ Please make header "Python 3 + numpy" \$\endgroup\$ – Leaky Nun Jul 27 '17 at 4:26
5
\$\begingroup\$

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)

Previous:

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

A full program printing a representation of the result.

\$\endgroup\$
  • \$\begingroup\$ Whoa -50% from previous Jelly answer! \$\endgroup\$ – Adám Jul 26 '17 at 23:39
  • \$\begingroup\$ Whoa what? Wow. I really need to study how you did this... Incredible compared to mine! \$\endgroup\$ – HyperNeutrino Jul 26 '17 at 23:40
  • \$\begingroup\$ Oh this is doing the two directions separately, right? Smart. \$\endgroup\$ – HyperNeutrino Jul 26 '17 at 23:41
  • \$\begingroup\$ I think it's doing roughly the same thing... \$\endgroup\$ – Jonathan Allan Jul 26 '17 at 23:41
  • \$\begingroup\$ Good method. Means I can beat this with APL. I've got 14 bytes. \$\endgroup\$ – Adám Jul 26 '17 at 23:50
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Most impressive. I guess Matlab was kinda made for stuff like this. \$\endgroup\$ – Adám Jul 26 '17 at 23:29
  • \$\begingroup\$ @Adám I'm sure APL's length won't be very different :-) \$\endgroup\$ – Luis Mendo Jul 26 '17 at 23:33
  • \$\begingroup\$ My reference implementation used to generate the test cases is 26 bytes. \$\endgroup\$ – Adám Jul 26 '17 at 23:35
  • \$\begingroup\$ @Adám Darn! APL beating Jelly? This is unacceptable! (must golf my solution... lol) xD \$\endgroup\$ – HyperNeutrino Jul 26 '17 at 23:37
  • \$\begingroup\$ @HyperNeutrino Well, Jelly doesn't have both rank and depth like APL and J have. \$\endgroup\$ – Adám Jul 26 '17 at 23:37
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ t=foldr(zipWith(:))(repeat[]). Not only shorter, also much less inefficient. \$\endgroup\$ – ceased to turn counterclockwis Jul 27 '17 at 11:00
  • \$\begingroup\$ @ceasedtoturncounterclockwis Thanks for the tip. \$\endgroup\$ – jferard Jul 27 '17 at 12:49
1
\$\begingroup\$

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]))
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Too many Euros. \$\endgroup\$ – Adám Jul 26 '17 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 Jul 26 '17 at 23:32
  • \$\begingroup\$ Why are you wasting your money like this €-€ \$\endgroup\$ – V. Courtois Jul 27 '17 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.