14
\$\begingroup\$

Given a matrix like this:

1  1  3 -2
3 -4  1 -1
1  1  1  0
0 -1  0  0

By taking a 2×2 "sliding sum", where the sum of every 2×2 region of the matrix is one element of the resulting matrix, we get:

1  1  1
1 -1  1
1  1  1

We can do this for sliding windows of any size. For example, a 1×3 sliding sum of the same input matrix would be:

 5  2
 0 -4
 3  2
-1 -1

In this challenge, you'll be given an output matrix and a window size, and should return a matrix whose sliding sum with the given window size is the input. The window size will be at least 1×1, but there is no maximum size.

Inputs and outputs will consist only of integers. Note that there are arbitrarily many correct solutions for most window sizes.

This is , so shortest answer per language (in bytes) wins.

\$\endgroup\$
6
  • \$\begingroup\$ can we accept the matrix as an array or list? \$\endgroup\$
    – pacman256
    Oct 19, 2022 at 16:23
  • 1
    \$\begingroup\$ @Pacmanboss256 Sure, any reasonable representation. \$\endgroup\$ Oct 19, 2022 at 16:23
  • 1
    \$\begingroup\$ Must the output only consist of integers or may we use other numbers? \$\endgroup\$ Oct 19, 2022 at 16:32
  • 1
    \$\begingroup\$ return a whose ~> return a matrix whose, I guess. \$\endgroup\$
    – Arnauld
    Oct 19, 2022 at 17:28
  • 2
    \$\begingroup\$ To whoever added open-ended-function, I don't think that tag is meaningful here. \$\endgroup\$ Oct 19, 2022 at 17:55

4 Answers 4

10
\$\begingroup\$

Python, 130 bytes

lambda A,m,n:[g(r,n)for r in zip(*(g(c,m)for c in zip(*A)))]
g=lambda A,k:A and g(A[:-1],k)+[sum(A[::-k])-sum(A[-2::-k])]or[0]*~-k

Attempt This Online!

This solves the problem dimension by dimension. The function g essentially implements multiplication by a pseudoinverse of the 1d convolution matrix which depending on dimensions looks somewhat like

\$\begin{pmatrix}1&0&0&0&0&0\\-1&1&0&0&0&0\\0&-1&1&0&0&0\\1&0&-1&1&0&0\\-1&1&0&-1&1&0\\0&-1&1&0&-1&1\\1&0&-1&1&0&-1\\-1&1&0&-1&1&0\end{pmatrix}\$

which inverts

\$\begin{pmatrix}1&1&1&0&0&0&0&0\\0&1&1&1&0&0&0&0\\0&0&1&1&1&0&0&0\\0&0&0&1&1&1&0&0\\0&0&0&0&1&1&1&0\\0&0&0&0&0&1&1&1\end{pmatrix}\$

\$\endgroup\$
3
\$\begingroup\$

Python3, 556 bytes:

from itertools import*
R=range
D=lambda l,y:l*y-(y-1)*(l-1)
def O(V,v):
 c=0
 while c:=c+1:
  for i in product(*[[R(-c,c+1),[a]][b]for a,b in V]):
   if sum(i)==v:return[*i]
def f(m,x,y):
 q=[([[[0,0]for _ in R(D(len(m[0]),y))]for _ in R(D(len(m),x))],0,0,[j for k in m for j in k])]
 while q:
  b,X,Y,v=q.pop(0)
  if[]==v:return[[a for a,_ in i]for i in b]
  r=O([b[j][k]for j in R(X,X+x)for k in R(Y,Y+y)],v[0])
  B=eval(str(b))
  for j in R(X,X+x):
   for k in R(Y,Y+y):B[j][k]=[r.pop(0),1]
  q+=[(B,[X+1,X][Y+y<len(b[0])],[0,Y+1][Y+y<len(b[0])],v[1:])]

Try it online!

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

PARI/GP, 150 bytes

f(a,m,n)=b=matinverseimage(matrix(#a*H=#a~,(w=#a+n-1)*h=H+m-1,i,j,![m<=x=j--%h-i--%H,x<0,n<=y=j\h-i\H,y<0]),concat(Vec(a)));matrix(h,w,i,j,b[i+j--*h])

Attempt This Online!

Or 119 bytes if we can output a flatten array:

f(a,m,n)=matinverseimage(matrix(#a*H=#a~,(#a+n-1)*h=H+m-1,i,j,![m<=x=j--%h-i--%H,x<0,n<=y=j\h-i\H,y<0]),concat(Vec(a)))

Attempt This Online!

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

Charcoal, 62 53 bytes

F⊖η⊞υE⊖⁺ζL§θι⁰Fθ«≔E⊖ζ⁰ε⊞υεFι⊞ε⁻κΣE…⮌υη↨¹✂λ⁻⊕Lεζ⊕Lε»Iυ

Try it online! Link is to verbose version of code. Explanation:

F⊖η⊞υE⊖⁺ζL§θι⁰

Generate zero rows of the final width which will pad the final matrix to the final height.

Fθ«

Loop over the rows of the input matrix.

≔E⊖ζ⁰ε

Start a new row of the output matrix with zeros which will pad the row to the final width.

⊞υε

Append the new row to the output matrix.

Fι

Loop over the cells of the current input matrix row.

⊞ε⁻κΣE…⮌υη↨¹✂λ⁻⊕Lεζ⊕Lε

Add the next entry to the output matrix row so that the sliding sum for this cell of the input matrix becomes correct. Note that "base 1" is used to sum the cells in a row because in the case of a window of width 1 the final row's cell does not exist yet.

»Iυ

Output the resulting matrix in default Charcoal format.

Example: For the given 2×2 sliding sum:

 1  1  1
 1 -1  1
 1  1  1

First a padding row is constructed, then a padding cell for the first input row:

 0  0  0  0
 0

To make the first sliding sum correct, a 1 is needed:

 0  0  0  0
 0  1

To make the second sliding sum correct, a 0 is needed:

 0  0  0  0
 0  1  0

To make the third sliding sum correct, another 1 is needed:

 0  0  0  0
 0  1  0  1

The new row starts again with a padding cell. To make the fourth sliding sum correct, a 0 is needed:

 0  0  0  0
 0  1  0  1
 0  0

To make the fifth sliding sum correct, a -2 is needed:

 0  0  0  0
 0  1  0  1
 0  0 -2

Continuing in this way, the resulting matrix is as follows:

 0  0  0  0
 0  1  0  1
 0  0 -2  2
 0  1  2 -1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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