# Minimal Centrosymmetrization

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

• Why do Centrosymmetric matrices have to be square? – Post Rock Garf Hunter Aug 6 '18 at 5:24
• @WW in a general sense, I don't suppose it has to be. For this question, however, they must be square by definition – Conor O'Brien Aug 6 '18 at 5:28
• I was wondering why you made that choice – Post Rock Garf Hunter Aug 6 '18 at 5:29
• @WW it was a simplification I thought to be useful for clarity – Conor O'Brien Aug 6 '18 at 5:30

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

• I wish ≜ did delayed labeling... – Erik the Outgolfer Aug 6 '18 at 12:17
• @EriktheOutgolfer Instant labeling is still useful when we need to enumerate things, so ideally we would need two different predicates… – Fatalize Aug 6 '18 at 12:18

# JavaScript (ES6), 192180 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.

# Jelly, 27 bytes

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


Try it online!

Newlines added to actual output over TIO for clarity.

# Python 2, 242227 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
• n=[W*[0]for _ in r(W)] can be n=eval([W*[0]]*W). – Jonathan Frech Aug 8 '18 at 7:46
• @JonathanFrech Thanks :) – TFeld Aug 8 '18 at 9:28

# 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!