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

• Jonah: Very nicely done!

Answer 3

Charcoal, (削除) 52 (削除ここまで) 42 bytes

WS⊞υιI⊟Φ⊕Lυ∧ι›⬤υ⬤λ=ν§§υ−μ%μι−ξ%ξι∨%Lυι%Lθι

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

WS⊞υι

Input the matrix.

I⊟Φ⊕Lυ∧ι

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 ...

ι∨%Lυι%Lθι

... 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.

• Bubbler: Doesn't work on all-same tall matrices (e.g. o\no\no) since there is only one tile and ;.3 fails to pad it to a square. The previous version (using <./@$) works. Nice use of decrement-until-it-works loop though.
• Jonah: Ah yeah, thanks. Reverted.

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.

• pajonk: Nice use of the kronecker product! Also, -2.
• pajonk: And another -1.
• Dominic van Essen: @pajonk - Thanks! Great trick with diag - and it led to 2 more bytes saved by using ^0 instead of |1...

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!

• xnor: You forgot to count the f= for the recursive function

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()

• Neil: x-x++%w seems to save 4 bytes but I can't figure out why you can't also use y-y%w.
• Neil: So how many bytes did y-y%w end up saving you?
• Arnauld: @Neil It actually saves 7 bytes indirectly. Fixing the original version to start with w=1 leads to the exact same size. But once we start with w=1, we can just iterate on m.
• Neil: Ah, so it costs 4 bytes to save 4 bytes, but then allows a subsequent 7 byte golf? Thanks for explaining.
• Arnauld: @Neil Yep. And using reduce() saves another byte. ;-)

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).

• Dominic van Essen: el is shorter than max
• Dominic van Essen: ...but I've found a shorter approach...
• pajonk: @DominicvanEssen looks like el doesn't work here for some test cases, for example the 2x8 one.
• Dominic van Essen: Ah, you're right, I didn't notice because they didn't give errors...

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)

• Kevin Cruijssen: @LuisMendo Taking the dimensions as additional first input-pair would save a byte: Sg to à (pop and get max) or P (pop and get product), but taking the input as string-list is still preferred over a flattened list of characters.

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.