Find a matrix whose sliding sum is the input

Question

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 code-golf, so shortest answer per language (in bytes) wins.

Answer 1

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}\$

Answer 2

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!

Answer 3

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!

Answer 4

Charcoal, 62 53 bytes

Ｆ⊖η⊞υＥ⊖⁺ζＬ§θι⁰Ｆθ«≔Ｅ⊖ζ⁰ε⊞υεＦι⊞ε⁻κΣＥ…⮌υη↨¹✂λ⁻⊕Ｌεζ⊕Ｌε»Ｉυ

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

Ｆ⊖η⊞υＥ⊖⁺ζＬ§θι⁰

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

Ｆθ«

Loop over the rows of the input matrix.

≔Ｅ⊖ζ⁰ε

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.

Ｆι

Loop over the cells of the current input matrix row.

⊞ε⁻κΣＥ…⮌υη↨¹✂λ⁻⊕Ｌεζ⊕Ｌε

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.

»Ｉυ

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