11
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ Why do Centrosymmetric matrices have to be square? \$\endgroup\$ – Sriotchilism O'Zaic Aug 6 '18 at 5:24
  • \$\begingroup\$ @WW in a general sense, I don't suppose it has to be. For this question, however, they must be square by definition \$\endgroup\$ – Conor O'Brien Aug 6 '18 at 5:28
  • \$\begingroup\$ I was wondering why you made that choice \$\endgroup\$ – Sriotchilism O'Zaic Aug 6 '18 at 5:29
  • 2
    \$\begingroup\$ @WW it was a simplification I thought to be useful for clarity \$\endgroup\$ – Conor O'Brien Aug 6 '18 at 5:30
8
+50
\$\begingroup\$

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.

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

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

Jelly, 27 bytes

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

Try it online!

Newlines added to actual output over TIO for clarity.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ n=[W*[0]for _ in r(W)] can be n=eval(`[W*[0]]*W`). \$\endgroup\$ – Jonathan Frech Aug 8 '18 at 7:46
  • \$\begingroup\$ @JonathanFrech Thanks :) \$\endgroup\$ – TFeld Aug 8 '18 at 9:28
1
\$\begingroup\$

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!

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