# Expand a matrix goo-ily

## Input

An $$\m\$$ by $$\n\$$ binary matrix, with $$\m\$$ and $$\n\$$ both at least 2.

Think of the ones as gobs of melted cheese, which stretch as we expand the matrix horizontally and vertically.

More precisely...

## Output

A $$\2m-1\$$ by $$\2n-1\$$ binary matrix, constructed as follows...

First insert rows of zeros between the rows, and insert columns of zeros between the columns. For example, consider the input:

0 1 1
1 0 1
1 0 0


After we insert the zeros:

0 0 1 0 1
0 0 0 0 0
1 0 0 0 1
0 0 0 0 0
1 0 0 0 0


To make it extra clear what we're doing, here is the same matrix with the new zeros visualized as #:

0 # 1 # 1
# # # # #
1 # 0 # 1
# # # # #
1 # 0 # 0


Now, for each new 0 (or # in our visualization), if is between two ones (horizontally, vertically, or diagonally), convert it to a 1:

0 # 1 1 1
# 1 # 1 1
1 # 0 # 1
1 # # # #
1 # 0 # 0


Or, exiting our visualization and converting # back to 0:

0 0 1 1 1
0 1 0 1 1
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0


And that is the actual, final result you return.

## Rules

• This is code golf with standard site rules
• You may take input in any reasonable format (array of arrays, built-in matrix type, single flat list, etc)
• With one exception: you may not take a list of the coordinates of the ones.
• This exception applies to the output as well: you must output all of the zeros and ones in some reasonable form.
• You may optionally take $$\m\$$ and $$\n\$$ as a second argument
• You can do I/O using images, so long as there is a 1-1 mapping with the matrix entries.

## Brownie Points

• Solution using images for I/O.
• J solution under 47 bytes.

## Test Cases

1 0
0 1
->
1 0 0
0 1 0
0 0 1

1 1
0 1
->
1 1 1
0 1 1
0 0 1

1 1
1 1
->
1 1 1
1 1 1
1 1 1

1 1
0 0
->
1 1 1
0 0 0
0 0 0

1 1 0 1 0 1
1 0 0 1 0 0
0 1 0 0 1 0
0 1 0 0 1 1
1 0 1 0 0 0
->
1 1 1 0 0 0 1 0 0 0 1
1 1 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 1 0
0 0 1 0 0 0 0 0 1 1 1
0 1 0 1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0

• Can it be assumed that the last row and last column contain a 1? (Since taking a sparse representation is forbidden, but converting to one isn't.) Mar 25, 2022 at 3:23
• @UnrelatedString It's possible those final rows or columns are all zeroes. I will clarify that the output also must not be sparse. Mar 25, 2022 at 3:24
• It would be interesting to see an answer that manipulates images instead of text-based input. (Unfortunately, that wouldn't be a valid answer IIUC.) Mar 25, 2022 at 11:42
• @LorenDB I’d be fine with that, so long as there was a 1-1 pixel mapping Mar 25, 2022 at 13:41

# Python 3 with numpy, 97 70 bytes

lambda m:abs(diff(diff(kron(m,1j**eye(2))),1,0))>=2
from numpy import*


Try it online!

The basic idea is this: Expand each element into a 2-by-2 block, then look at each 2-by-2 square (overlapping) in the resulting matrix; each square should correspond to a 1 iff it contains a pair of diagonally opposite 1s.

The implementation works a bit differently. kron expands each 1 into 1j**eye(2), which is $$\ \begin{array}{|c|c|} \hline i & 1 \\ \hline 1 & i \\ \hline \end{array} \$$, and taking diff in both directions is equivalent to a sum with multipliers $$\ \begin{array}{|c|c|} \hline 1 & -1 \\ \hline -1 & 1 \\ \hline \end{array} \$$ on each 2-by-2 square (overlapping). Then, each square contains two diagonally opposite nonzero values iff its result has real or imaginary component at least 2 in absolute value, which with integer components is equivalent to its own absolute value being at least 2.

# 05AB1E, 453819 16 bytes

2F€Dø€ü2}εεRøPà


-19 bytes porting @m90's Python answer, so make sure to upvote him/her as well!
-3 bytes thanks to @m90.

Explanation:

2F       # Loop 2 times:
€D     #  Duplicate each value in the current list
ø      #  Zip/transpose; swapping rows/columns
€     #  For each inner list:
ü2   #   Create overlapping pairs
}        # Close the loop
# (we now have overlapping 2x2 blocks of the input-matrix after that has been
# expanded to 2x2 for each individual value)
ε       # Map over each list of blocks:
ε      #  Map over each 2x2 block:
#   Pop and push both pairs separated to the stack
#    STACK: [[a,b],[c,d]] → [a,b] and [c,d]
R    #   Reverse the top pair
#    STACK: [a,b] and [d,c]
ø   #   Create pairs of these two pairs
#    STACK: [[a,d],[b,c]]
P  #   Take the product of each inner pair to check if both are 1
#    STACK: [a*d,b*c]
à #   Take the maximum to check if either was truthy
#   (so whether the diagonal or anti-diagonal of the 2x2 block were both 1s)


2Føε0ìSĆ]2Fø€ü3}εε2FøíÐÅsˆÅ\ˆ}¯ειPà}à´


Explanation:

Step 1: Surround each value with 0s (including a border of 0s around the entire matrix, unlike the challenge description):

2F         # Loop 2 times:
ø        #  Zip/transpose; swapping rows/columns
#  (which will use the implicit input-matrix in the first iteration)
ε       #  Map over each inner list:
0ì     #   Prepend a 0 in front of each digit
S    #   Then convert it to a flattened list of digits
Ć   #   Enclose; append its own head (for the trailing border of 0s)
]          # Close both the inner map and outer loop


Step 2: Create overlapping 3x3 blocks of this matrix:

2F         # Loop 2 times again:
ø        #  Zip/transpose; swapping rows/columns
€       #  For each inner list:
ü3     #   Create overlapping triplets
}          # Close the loop


Step 3: Transform each 3x3 block to a quartet of triplets of its middle row; middle column; main diagonal; and main anti-diagonal:

ε          # Map over each list of blocks:
ε         #  Map over each 3x3 block:
2F       #   Loop 2 times:
øí     #    Rotate the 3x3 block 90 degrees clockwise:
ø      #     Zip/transpose; swapping rows/columns
í     #     Reverse each inner row
Ð    #    Triplicate this 3x3 block
Ås  #    Pop one, and push its middle row
ˆ #    Pop and add this triplet to the global array
Å\ˆ #    Do the same for the main diagonal
}¯      #   After the loop: push the global array


Step 4: Check if either the middle is already 1, or if any sides of a middle row/column/diagonal/anti-diagonal are both 1:

  ε        #   Map over the list of triplets:
ι       #    Uninterleave it from [a,b,c] to [[a,c],[b]]
P      #    Take the product of each inner list: [a*c,b]
à     #    Pop and push the maximum
}à       #   After the map: pop and push the maximum
´      #   And clear the global array
# (after which the result is output implicitly)

• Improvement: 2F€Dø€ü2}εεRøPà, moving the duplication into the loop.
– m90
Apr 3, 2022 at 7:31

# PARI/GP, 82 bytes

m->matrix(2*#m~-1,2*#m-1,x,y,m[i=x++\2,j=y++\2]*m[k=i+x%2,l=j+y%2]||m[i,l]*m[k,j])

Attempt This Online!

# Octave, 45 bytes

A port of @m90's Python (NumPy) answer.

@(m)abs(diff(diff(kron(m,[i,1;1,i])),1,2))>=2


Try it online!

# Octave, 70 bytes

-5 bytes thanks to @Luis Mendo.

@(m)(n=kron(m,e(2)))(i=1:end-1,j=1:end-1)&n(i+1,j+1)|n(i,j+1)&n(i+1,j)


Try it online!

## how

Takes m = [0 1 1; 1 0 1; 1 0 0] as an example:

octave:1> m = [0 1 1; 1 0 1; 1 0 0]
m =

0   1   1
1   0   1
1   0   0

octave:2> n = kron(m,e(2))    # Repeats each element by 2x2
n =

0   0   1   1   1   1
0   0   1   1   1   1
1   1   0   0   1   1
1   1   0   0   1   1
1   1   0   0   0   0
1   1   0   0   0   0

octave:3> n11 = n(1:end - 1, 1:end - 1)
n11 =

0   0   1   1   1
0   0   1   1   1
1   1   0   0   1
1   1   0   0   1
1   1   0   0   0

octave:4> n12 = n(1:end - 1, 2:end)
n12 =

0   1   1   1   1
0   1   1   1   1
1   0   0   1   1
1   0   0   1   1
1   0   0   0   0

octave:5> n21 = n(2:end, 1:end - 1)
n21 =

0   0   1   1   1
1   1   0   0   1
1   1   0   0   1
1   1   0   0   0
1   1   0   0   0

octave:6> n22 = n(2:end, 2:end)
n22 =

0   1   1   1   1
1   0   0   1   1
1   0   0   1   1
1   0   0   0   0
1   0   0   0   0

octave:7> (n11 & n22) | (n12 & n21)
ans =

0  0  1  1  1
0  1  0  1  1
1  0  0  0  1
1  0  0  0  0
1  0  0  0  0

• You can replace ones(2,2) by e(2) Mar 25, 2022 at 19:13

# Jelly, 15 bytes

żḢS€E?ƝẎ)Z$⁺Ạ€€  A monadic Link that accepts a list of lists of 1s and 0s and yields a list of lists of 1s and 0s. Try it online! Or see the test-suite. ### How? The basic idea is to insert a value, f(left,right), between each neighbouring pair, [left,right], of each row then to transpose, and then to repeat the same thing again (insert values, transpose). In order to handle the diagonal requirement, we must have an f(left,right) that maintains the necessary information between the steps. That is, when neighbours are not equal we need to remember which one was a one during the first pass and have those values work for us during the second pass. The code below implements f(left,right) as "if left equals right then yield left else yield the sum of each of [left,right]" (ḢS€E?). This means that the first pass can yield [1,0] or [0,1] (to be treated as 0s in the end) in addition to 0 and 1, and the second pass can then yield [1,1] too (to be treated as a 1 in the end). żḢS€E?ƝẎ)Z$⁺Ạ€€ - Link: list of list of 1s and 0s, M
$⁺ - do this twice - f(Current=M): ) - for each Row in Current: Ɲ - for neighbouring pairs of elements in Row: ? - if... E - ...condition: equal? Ḣ - ...then: head first pass: [0,0]->0 [1,1]->1 second pass: [ 0 , 0 ]-> 0 [ 1 , 1 ]-> 1 [[1,0],[1,0]]->[1,0] [[0,1],[0,1]]->[0,1] S€ - ...else: sum each first pass: [0,1]->[0,1] [1,0]->[1,0] second pass: [ 0 , 1 ]->[0,1] [ 0 ,[0,1]]->[0,1] [ 0 ,[1,0]]->[0,1] [ 1 , 0 ]->[1,0] [ 1 ,[0,1]]->[1,1] [ 1 ,[1,0]]->[1,1] [[0,1], 0 ]->[1,0] [[0,1], 1 ]->[1,1] [[0,1],[1,0]]->[1,1] [[1,0], 0 ]->[1,0] [[1,0], 1 ]->[1,1] [[1,0],[0,1]]->[1,1] ż - zip Curent and those together Ẏ - tighten (flattens by one level, to counter the zip) Z - transpose Ạ€€ - all? for each element in each row 0->0 1->1 [0,1]->0 [1,0]->0 [1,1]->1  Implementing f(left,right) as a hash function, with Jelly's ḥ built-in, I've only found a 16: ż⁽7&,14ḥ$ƝẎ)Z\$⁺Ḃ


# Charcoal, 35 bytes

ＷＳ⊞υιＥ⊖⊗Ｌυ⭆⊖⊗Ｌθ⌈Ｅ²⌊Ｅ²§§υ⊘⁺ιπ⊘⁺λ¬⁼νπ


Try it online! Link is to verbose version of code. Takes I/O as a list of newline-terminated strings of 0s and 1s. Explanation:

ＷＳ⊞υι


Input the binary matrix.

Ｅ⊖⊗Ｌυ⭆⊖⊗Ｌθ⌈Ｅ²⌊Ｅ²§§υ⊘⁺ιπ⊘⁺λ¬⁼νπ


Loop over the dimensions of the expanded matrix, calculating the positions of the possible adjacent 1s, and for each output 1 if one pair of positions is both 1. This is equivalent to the following operations, starting with:

WX
YZ


This first gets expanded by duplication, i.e.

ABC WWX
DEF=WWX
GHI YYZ


Then for each position in the grid, two pairs of cells are checked: the cell itself and the one diagonally below right, and the cells below and to the right:

A -> AE | BD = WW | WW = W
B -> BF | CE = WX | XW = WX
D -> DH | EG = WY | WY = WY
E -> EI | FH = WZ | XY as desired


# Pip-xP, 25 bytes

{MX B*R_MPaZb}MP_WV_MaWVa


Attempt This Online!

### Explanation

{MX B*R_MPaZb}MP_WV_MaWVa
`