Compute matrix blockiness

Question

Consider a non-empty binary matrix M and a natural number n. For the purposes of this challenge, M is said to have blockiness n if it can be built using adjacent square blocks of size n, where each block has equal entries; and it cannot be formed using square blocks of any larger size. Intuitively, n can be thought of as the "pixel size" of the matrix.

Example 1: let the values of the matrix be represented as + and o for clarity.

++oo++++
++oo++++
oo++++++
oo++++++

has blockiness 2. Although some entries can be considered to belong to larger blocks, 2 is the maximum block size that is valid for all entries. To be specific, the blocks are shown below, using · as separator:

++·oo·++·++
++·oo·++·++
···········
oo·++·++·++
oo·++·++·++

Example 2:

+++oo+++
+++oo+++

has blockiness 1. Even if any entry can be seen as belonging to some "sliding" block of size 2, it is not possible to form the matrix using adjacent blocks of that size.

The challenge

Given a non-empty binary matrix, output its blockiness.

Rules

• Any two consistent values can be chosen to define the matrix. Input format is flexible as usual (2D array, list of lists of numbers, flattened array and one or two numbers defining its shape, list of strings, ...).
• Input and output means are flexible as usual. Programs or functions are allowed. Standard loopholes are forbidden.
• Code golf, shortest wins.

Test cases

See also "inputs in common formats" at the end.

• Blockiness 1:

+

ooo

+o
++

+++oo+++
+++oo+++

ooo+++
ooo+++
++++++
++oooo

ooooo
ooooo
ooooo
ooooo

• Blockiness 2:

oo
oo

++++
++++

++oo++++
++oo++++

++oo++++
++oo++++
oo++++++
oo++++++

• Blockiness 3:

++++++ooo
++++++ooo
++++++ooo

ooo+++ooo
ooo+++ooo
ooo+++ooo
+++ooo+++
+++ooo+++
+++ooo+++

• Blockiness 4:

++++++++
++++++++
++++++++
++++++++

++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo
++++++++oooo

Inputs in common formats:

• Numerical matrix, Matlab/Octave
• Character matrix, Matlab/Octave
• Nested list, Python
• List of strings, Python
• Flattened array (row-major order) and shape (numbers of rows and columns)
• If you think that some common format is missing, leave a comment and I'll try to generate it automatically.

Answer 1

Wolfram Language (Mathematica), 33 bytes

GCD@@Length/@Split@Join[2#,#]&

Try it online!

Take a 2d array of 2's and 3's, or any two values \$a\$, \$b\$ such that \$\{a,b\}\cap\{2a,2b\}=\{\}\$.

Split the array into runs of identical rows and columns, and take the GCD of the lengths of these runs.

Here  is the postfix operator for matrix transpose.

Answer 2

J, 24 bytes

+./@,&I.&(1#.0&,~:,&0)|:

Try it online!

Port of alephalpha's Mathematica answer.

+./@,&I.&(1#.0&,~:,&0)|:    NB. Input: matrix M
     &                |:    NB. For M and its transpose:
             0&,            NB. M with a zero row prepended
                  ,&0       NB. M with a zero row appended
                ~:          NB. Elementwise unequal of the two
          1#.   NB. Row-wise sum
      I.&       NB. Indices; x[i] copies of i
+./@,           NB. Concatenate the two results and GCD reduce

---

J, 39 bytes

1 i:~0,(2 2$#)\(];.3*/@,@e.0 1+[$1:)"2]

Try it online!

The input format is a matrix of 1's and 2's.

How it works

1 i:~0,(2 2$#)\(];.3*/@,@e.0 1+[$1:)"2]    NB. input: matrix M having n rows

(2 2$#)\    NB. 3D block, each layer is 2x2 matrix of i where i <- 1..n
(...)"2]    NB. For each layer of above and the entirety of matrix M...
 ];.3       NB.  A: Extract ixi blocks of M, padding with zeros
            NB.  (when some padding exists, the test always fails)
 0 1+[$1:   NB.  B: 3D block having two layers: ixi of 1's and ixi of 2's
 */@,@e.    NB.  Test if every 2D cell of A exists as a cell in B
            NB.  i.e. Test if all ixi blocks of M are valid
1 i:~0,     NB. Extract the last 1-based index of 1

Answer 3

Charcoal, 52 42 bytes

ＷＳ⊞υιＩ⊟Φ⊕Ｌυ∧ι›⬤υ⬤λ⁼ν§§υ⁻μ﹪μι⁻ξ﹪ξι∨﹪Ｌυι﹪Ｌθι

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings. Explanation:

ＷＳ⊞υι

Input the matrix.

Ｉ⊟Φ⊕Ｌυ∧ι

Output the largest number from 1 to the height of the matrix...

›⬤υ⬤λ⁼ν§§υ⁻μ﹪μι⁻ξ﹪ξ

... for which each character equals that at the top left corner of its aligned submatrix ...

ι∨﹪Ｌυι﹪Ｌθι

... and which divides both its height and width.

Answer 4

J, ^{57 51 50 48 44 43} 39 bytes

<:@]^:(0 e.[:,[:="1[,;.3~2 2$])^:_<./@$

Try it online!

-4 thanks to Bubbler's idea of using 1-2 encoding to capitalize on automatic 0-padding

Input is 1-2 matrix.

• <./@$ - Starting with the smaller dimension of the input (call it d)...
• <:@] - Decrement d while...
• ^:...^:_ - Stuff (elaborated below) that checks if, when we tile the input with d x d tiles, any one of them is non-homogeneous:
  • 0 e. Is 0 an element of...
  • [:, The flatten of...
  • [:="1 The catalog of... (the catalog of a list is all ones only for a homogeneous list)
  • [,;.3~2 2$] Each d x d tile flattened. Partial tiles are 0 padded, and thus guaranteed to be non-homogeneous.

Answer 5

Python 3 with numpy, 92 bytes

from numpy import*
f=lambda m,k=1:k<len(m)and f(m,k+1)or all(m==kron(m[::k,::k],eye(k)<2))*k

Try it online!

Takes a numpy ndarray.

m[::k,::k] takes every kth element of m in both dimensions; eye(k)<2 is a short way to make a k-by-k matrix with every entry True (which is equivalent to 1 here). With these arguments, kron expands each element from m[::k,::k] to a k-by-k block. Next, the equality check with m produces a matrix of individual Boolean results if the sizes are the same, or False if the sizes are different (deprecated); all turns this into a single Boolean representing whether the matrices are the same.

Answer 6

R, 104 97 90 85 bytes

Edit: -3 bytes thanks to pajonk

f=function(m,b=nrow(m))`if`(identical(m[i<-1:b<2,i,drop=F]%x%diag(b)^0,m),b,f(m,b-1))

Try it online!

Recursive function: tests blockiness b starting with number of rows of matrix m, and recurses decreasing b until it finds one that fits.
Blockiness test consists of calculating the kronecker product (%x% function in R) of each b-th element of m, and a bxb matrix of 1s: the result should be identical to m if b is the correct blockiness.

Answer 7

05AB1E, 6 bytes

xø«Åγ¿

Try it online!

Port of my Mathematica answer.

Take a list of lists of 2's and 3's as input.

x       # Pop a and push a, 2a
 ø      # Transpose
  «     # Concatenate
   Åγ   # Run-length encode
     ¿  # GCD

Answer 8

Ruby, 118 bytes

f=->m,z=$.=m.size{x=[]
(0...$.).step(z){|r|y=[]
(0...m[0].size).step(z){|c|y+=[m[r][c]]*z}
x+=[y]*z}
x==m ?z:f[m,z-1]}

Try it online!

• Recursively (starting from one dimension length) try block sizes, return first valid value.
• Reconstructs the matrix by taking a value at each block, repeating it z times to form each block. Finally compare with original input.

Tried a different approach by slicing each block but ended at 125B

->m{(1..m.size).select{|z|x=[]
m.each_slice(z){|s|x+=s.transpose.each_slice(z).map(&:flatten)}
x.all?{|b|b==[b[0]]*z*z}}.max}

Answer 9

Python 3, 108, 104, 97 bytes

-7 by borowing @m90's better control flow

f=lambda M,n=1:n<len(M)and f(M,n+1)or all(X==[*sum(zip(*n*[X[::n]]),())]for X in[M,[*zip(*M)]])*n

Try it online!

Old version

Straight-forward approach; tries successively smaller block sizes until a working one is found.

Old, longer but more readable version:

f=lambda M,n=0:n and all(X[i::n]==X[::n]for i in range(n)for X in[M,[*zip(*M)]])and n or f(M,~-n%-~len(M))  

Try it online!

Answer 10

JavaScript (ES6),  101 92 90  89 bytes

Saved 4 bytes thanks to @Neil, and  7  8 more bytes from there

m=>m.reduce(o=>++w*m.some(r=>r.some(v=>v-m[y-y%w][x-x++%w],x=0)*++y|x%w,y=0)|y%w?o:w,w=0)

Try it online!

Commented

m =>                 // m[] = input matrix
m.reduce(o =>        // for each row in m[], using o as an accumulator:
  ++w *              //   increment w
  m.some(r =>        //   for each row r[] in m[]:
    r.some(v =>      //     for each value v in r[]:
      v -            //       compare v with
      m[y - y % w]   //       the top-left corner of the submatrix of
      [x - x++ % w], //       width w in which we're currently located
                     //       increment x afterwards
      x = 0          //       start with x = 0
    )                //     end of inner some()
    * ++y            //     increment y
    | x % w,         //     force to fail if w does not divide x
    y = 0            //     start with y = 0
  )                  //   end of outer some()
  | y % w            //   force to fail if w does not divide y
  ?                  //   if failed:
    o                //     leave o unchanged
  :                  //   else:
    w,               //     update it to w
  w = 0              //   start with o = w = 0
)                    // end of reduce()

Answer 11

R, 143 139 132 bytes

Or R>=4.1, 118 bytes by replacing two function occurences with \s.

function(M,k=dim(M))for(n in k:1)if(!any(k%%n,tapply(M,(row(M)-1)%/%n*max(k)+(col(M)-1)%/%n,function(x)sum(table(x)|1)-1)))return(n)

Try it online!

Bases heavily on the split idea from my answer to Square chunk my matrix (although here we have rectangular matices, which are a little trickier).

Answer 12

05AB1E, 27 bytes

SgLR.Δδôøy©δô€`εSDËsgt®Q*}P

Inputs as list of strings.

Try it online or verify all test cases.

Explanation:

S                # Convert the (implicit) input-list of strings to a flattened list of
                 # characters
 g               # Pop and push its length
  L              # Pop and push a list in the range [1,length]
   R             # Reverse it to [length,1]
    .Δ           # Find the first block-size `y` which is truthy for:
      δ          #  Map over each string in the (implicit) input-list:
       ô         #   Split it into substrings of size `y`
        ø        #  Zip/transpose; swapping rows/columns
           δ     #  Map over each inner list again:
         y  ô    #   And split it into blocks of size `y` again
          ©      #  Also store block-size `y` in variable `®` (without popping)
             €`  #  Flatten this list of lists of blocks one level down
      ε          #  Map over each `y` by `y` sized block (or smaller, if we couldn't
                 #  divide a row or column into size `y` with builtin `ô`)
       S         #   Convert the current block to a flattened list of characters
        D        #   Duplicate it
         Ë       #   Check if all characters are the same
          s      #   Swap so the list of characters is at the top again
           g     #   Push its length
            t    #   Take the square-root of that
             ®Q  #   Check if this is equal to block-size `®`
               * #   Check if both are truthy
      }P         #  After the map: check if all were truthy
                 # (after which the found result is output implicitly)

Answer 13

Core Maude, 319 317 bytes

mod M is pr LIST{Nat}*(op size to z). ops b n : Nat Nat ~> Nat . var A B M N
W X Y Z :[Nat]. eq b(M,W)= n(M,W s W). ceq n(M,W s N)= n(M,W N)if X A Y B Z :=
M /\ W rem N + z(M)quo W rem N =/= 0 or A + B == 1 and z(X)quo W quo N(z(X)rem W
quo N)== z(X A Y)quo W quo N(z(X A Y)rem W quo N). eq n(M,W s N)= N[owise]. endm

To obtain the result, reduce the b function with the matrix as a flattened list, and the row length. (Maude has a matrix type, but we're not using it.)

Example Session

Maude> --- Blockiness 1
> 
> red b(
>     0,
>     1
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1,
>     3
> ) .
result NzNat: 1
Maude> 
> red b(
>     0 1
>     0 0,
>     2
> ) .
result NzNat: 1
Maude> 
> red b(
>     0 0 0 1 1 0 0 0
>     0 0 0 1 1 0 0 0,
>     8
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1 0 0 0
>     1 1 1 0 0 0
>     0 0 0 0 0 0
>     0 0 1 1 1 1,
>     6
> ) .
result NzNat: 1
Maude> 
> red b(
>     1 1 1 1 1
>     1 1 1 1 1
>     1 1 1 1 1
>     1 1 1 1 1,
>     5
> ) .
result NzNat: 1
Maude> 
> 
> --- Blockiness 2
> 
> red b(
>     1 1
>     1 1,
>     2
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 0 0
>     0 0 0 0,
>     4
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 1 1 0 0 0 0
>     0 0 1 1 0 0 0 0,
>     8
> ) .
result NzNat: 2
Maude> 
> red b(
>     0 0 1 1 0 0 0 0
>     0 0 1 1 0 0 0 0
>     1 1 0 0 0 0 0 0
>     1 1 0 0 0 0 0 0,
>     8
> ) .
result NzNat: 2
Maude> 
> 
> --- Blockiness 3
> 
> red b(
>     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,
>     9
> ) .
result NzNat: 3
Maude> 
> red b(
>     1 1 1 0 0 0 1 1 1
>     1 1 1 0 0 0 1 1 1
>     1 1 1 0 0 0 1 1 1
>     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,
>     9
> ) .
result NzNat: 3
Maude> 
> 
> --- Blockiness 4
> 
> red b(
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0
>     0 0 0 0 0 0 0 0,
>     8
> ) .
result NzNat: 4
Maude> 
> red b(
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1
>     0 0 0 0 0 0 0 0 1 1 1 1,
>     12
> ) .
result NzNat: 4

Ungolfed

mod M is
    pr LIST{Nat} * (op size to z) .

    ops b n : Nat Nat ~> Nat .

    var A B M N W X Y Z : [Nat] .

    eq b(M, W) = n(M, W s W) .

    ceq n(M, W s N) = n(M, W N)
        if X A Y B Z := M
        /\ W rem N + z(M) quo W rem N =/= 0
        or A + B == 1
        and z(X) quo W quo N (z(X) rem W quo N)
            == z(X A Y) quo W quo N (z(X A Y) rem W quo N) .
    eq n(M, W s N) = N [owise] .
endm

For a given N, we essentially test every partition of the input list into five sublists (including ones where A and B aren't single elements). Then we verify if that partition corresponds to an actual counter-example for N. This is very slow — the last case for blockiness 4 takes several minutes to run. But it terminates!

---

Saved 2 bytes by removing two pairs of parentheses. Parentheses don't often cost bytes in Maude because they can often replace a space due to tokenization weirdness, but in this case there were two pairs of parentheses next to each other.