19
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ 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.) \$\endgroup\$ Mar 25 at 3:23
  • 1
    \$\begingroup\$ @UnrelatedString It's possible those final rows or columns are all zeroes. I will clarify that the output also must not be sparse. \$\endgroup\$
    – Jonah
    Mar 25 at 3:24
  • 2
    \$\begingroup\$ 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.) \$\endgroup\$
    – LorenDB
    Mar 25 at 11:42
  • 1
    \$\begingroup\$ @LorenDB I’d be fine with that, so long as there was a 1-1 pixel mapping \$\endgroup\$
    – Jonah
    Mar 25 at 13:41

7 Answers 7

8
\$\begingroup\$

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.

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

05AB1E, 45 38 19 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.

Try it online or verify all test cases or try it online with step-by-step debug lines.

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)

Original 45 38 bytes answer:

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

Try it online or verify all test cases or try it online with step-by-step debug lines.

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Improvement: 2F€Dø€ü2}εε`RøPà, moving the duplication into the loop. \$\endgroup\$
    – m90
    Apr 3 at 7:31
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can replace ones(2,2) by e(2) \$\endgroup\$
    – Luis Mendo
    Mar 25 at 19:13
3
\$\begingroup\$

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

Charcoal, 35 bytes

WS⊞υιE⊖⊗Lυ⭆⊖⊗Lθ⌈E²⌊E²§§υ⊘⁺ιπ⊘⁺λ¬⁼νπ

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:

WS⊞υι

Input the binary matrix.

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

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

Pip -xP, 25 bytes

{MX B*R_MPaZb}MP_WV_MaWVa

Attempt This Online!

Explanation

Port of Neil's Charcoal answer.

{MX B*R_MPaZb}MP_WV_MaWVa
                     a     First command-line input (eval'd as list due to -x flag)
                      WVa  Weave with itself (double each row)
                    M      Map to each row:
                _WV_         Weave with itself (double each column)
{            }MP           Map to each pair of rows:
          aZb                Zip the two rows together
        MP                   Map to each pair of [upper lower] pairs (i.e. 2x2 submatrix):
      R_                       Reverse the first pair
    B*                         Multiply itemwise by the second pair
 MX                            Maximum (1 if either product is 1, 0 otherwise)
\$\endgroup\$

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.