Minimal Centrosymmetrization

Question

_{Topically related.}

Objective: Given a matrix of positive integers \$M\$, output the smallest centrosymmetric matrix which contains \$M\$ (this matrix may contain non-positive integers as well).

A centrosymmetric matrix is a square matrix with rotational symmetry of order 2—i.e. it remains the same matrix after rotating it twice. For example, a centrosymmetric matrix has the top-left element the same as the bottom-right, and the element above the center the same as the one below the center. A useful visualization can be found here.

More formally, given a matrix \$M\$, produce a square matrix \$N\$ such that \$N\$ is centrosymmetric and \$M\subseteq N\$, and there is no other square matrix \$K\$ such that \$\dim K<\dim N\$.

\$A\$ is a subset of \$B\$ (notation: \$A\subseteq B\$) if and only if each value \$A_{i,j}\$ appears at index \$B_{i+i^\prime,j+j^\prime}\$ for some pair of integers \$(i^\prime, j^\prime)\$.

Note: some matrices have multiple solutions (e.g. [[3,3],[1,2]] being solved as [[2,1,0],[3,3,3],[0,1,2]] or [[3,3,3],[1,2,1],[3,3,3]]); you must output at least one of the valid solutions.

Test cases

input
example output

[[1, 2, 3],
 [4, 5, 6]]
[[1, 2, 3, 0],
 [4, 5, 6, 0],
 [0, 6, 5, 4],
 [0, 3, 2, 1]]

[[9]]
[[9]]

[[9, 10]]
[[9, 10],
 [10, 9]]

[[100, 200, 300]]
[[100, 200, 300],
 [  0,   0,   0],
 [300, 200, 100]]

[[1, 2, 3],
 [4, 5, 4]]
[[1, 2, 3],
 [4, 5, 4]
 [3, 2, 1]]

[[1, 2, 3],
 [5, 6, 5],
 [3, 2, 1]]
[[1, 2, 3],
 [5, 6, 5],
 [3, 2, 1]]

[[4, 5, 4],
 [1, 2, 3]]
[[3, 2, 1],
 [4, 5, 4],
 [1, 2, 3]]

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1]]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

Answer 1

Brachylog, 12 bytes

ṁ↔ᵐ↔?aaᵐ.&≜∧

Try it online!

Contrary to most Brachylog answers, this takes the input through the Output variable ., and outputs the result through the Input variable ? (confusing, I know).

Explanation

ṁ              We expect a square matrix
 ↔ᵐ↔?          When we reverse the rows and then the matrix, we get the initial matrix back
    ?a         Take an adfix (prefix or suffix) of that square matrix
      aᵐ       Take an adfix of each row of that adfix matrix
        .      It must be the input matrix
         &≜    Assign values to cells which are still variables (will assign 0)
           ∧   (disable implicit unification between the input and the output)

8 bytes, gives all valid matrices

Technically, this program also works:

ṁ↔ᵐ↔?aaᵐ

But this will leave as variables the cells which can take any value (they show as _XXXXX, which is an internal Prolog variable name). So technically this is even better than what is asked, but I guess it's not what the challenge asks for.

Answer 2

JavaScript (ES6), 192 180 177 bytes

f=(m,v=[w=0],S=c=>v.some(c))=>S(Y=>S(X=>!m[w+1-Y]&!m[0][w+1-X]&!S(y=>S(x=>(k=(m[y-Y]||0)[x-X],g=y=>((r=a[y]=a[y]||[])[x]=r[x]||k|0)-k)(y)|g(w-y,x=w-x)),a=[])))?a:f(m,[...v,++w])

Try it online!

Algorithm

Starting with \$w=0\$:

• We consider a square container matrix \$M\$ of width \$w+1\$.

• We consider each pair \$(X,Y)\$ such that the input matrix \$m\$ can fit within the container matrix when it's inserted at these coordinates.

  Example:

$$\begin{align}w=2,&&(X,Y)=(0,1),&&m = \pmatrix{4,5,4\\1,2,3}\end{align}\\ M=\pmatrix{\color{gray}0,\color{gray}0,\color{gray}0\\4,5,4\\1,2,3}$$

• We test whether we can complete the matrix such that it's centrosymmetric.

  Example:

$$M^\prime=\pmatrix{\color{blue}3,\color{blue}2,\color{blue}1\\4,5,4\\1,2,3}$$

• We increment \$w\$ until we find such a valid configuration.

Answer 3

Python 2, 242 227 226 bytes

r=range
def f(m):
 w,h=len(m),len(m[0]);W=max(w,h)
 while 1:
	for x in r(1+W-w):
	 for y in r(1+W-h):
		n=n=eval(`[W*[0]]*W`);exec"for i in r(w):n[i+x][y:y+h]=m[i]\nN=n;n=[l[::-1]for l in n[::-1]]\n"*2
		if n==N:return n
	W+=1

Try it online!

---

Saved:

• -1 byte, thanks to Jonathan Frech

Answer 4

Jelly, 27 bytes

oZ0ṁz0o⁸ṚUŻ€Z$2¡LСo⁸ṚU$ƑƇḢ

Try it online!

Newlines added to actual output over TIO for clarity.

Answer 5

Clojure 254 bytes

(defn e[l m](let[a map v reverse r repeat t concat c count f #(v(a v %))h(fn[x](t(a #(t %(r(- l(c(first x)))0))x)(r(- l(c m))(r l 0))))k(fn[x](a(fn[v w](a #(if(= %2 0)%1 %2)v w))x(f x)))n(k(h m))o(k(h(f m)))z #(= %(f %))](if(z n)n(if(z o)o(e(inc l)m)))))

Jinkies, Scoob

Try it online!