Centrosymmetrización mínima

11

Tópicamente relacionado.

Objetivo: Dada una matriz de enteros positivos , genera la matriz centrosimétrica más pequeña que contiene M (esta matriz también puede contener enteros no positivos).MM

Una matriz centrosimétrica es una matriz cuadrada con simetría rotacional de orden 2, es decir, permanece la misma matriz después de rotarla dos veces. Por ejemplo, una matriz centrosimétrica tiene el elemento superior izquierdo igual que el inferior derecho, y el elemento sobre el centro igual que el que está debajo del centro. Una visualización útil se puede encontrar aquí .

Más formalmente, dada una matriz , producen una matriz cuadrada N tal que N es centrosimétrico y M N , y no hay otra matriz cuadrada K tal que dim K < dim N .MNNMNKdimK<dimN

es un subconjunto de B (notación: A B ) si y solo si cada valor A i , j aparece en el índice B i + i , j + j para algún par de enteros ( i , j ) .ABABAi,jBi+i,j+j(i,j)

Nota : algunas matrices tienen múltiples soluciones (por ejemplo, [[3,3],[1,2]]se resuelven como [[2,1,0],[3,3,3],[0,1,2]]o [[3,3,3],[1,2,1],[3,3,3]]); debe generar al menos una de las soluciones válidas.

Casos de prueba

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]]
Conor O'Brien
fuente
¿Por qué las matrices Centrosymmetric tienen que ser cuadradas?
Ad Hoc Garf Hunter
@WW en un sentido general, no creo que tenga que ser así. Sin embargo, para esta pregunta, deben ser cuadrados por definición
Conor O'Brien el
Me preguntaba por qué tomaste esa decisión
Ad Hoc Garf Hunter
2
@WW fue una simplificación que pensé que sería útil para mayor claridad
Conor O'Brien

Respuestas:

8

Brachylog , 12 bytes

ṁ↔ᵐ↔?aaᵐ.&≜∧

Pruébalo en línea!

Contrariamente a la mayoría de las respuestas de Brachylog, esto lleva la entrada a través de la variable Salida .y genera el resultado a través de la variable Entrada ?(confuso, lo sé).

Explicación

ṁ              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, da todas las matrices válidas

Técnicamente, este programa también funciona:

ṁ↔ᵐ↔?aaᵐ

Pero esto dejará como variables las celdas que pueden tomar cualquier valor (se muestran como _XXXXX, que es un nombre interno de variable Prolog). Entonces, técnicamente, esto es incluso mejor de lo que se pide, pero supongo que no es lo que pide el desafío.

Fatalizar
fuente
Desearía haber retrasado el etiquetado ...
Erik the Outgolfer
@EriktheOutgolfer El etiquetado instantáneo sigue siendo útil cuando necesitamos enumerar cosas, por lo que idealmente necesitaríamos dos predicados diferentes ...
Fatalize
4

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

Pruébalo en línea!

Algoritmo

w=0

  • Mw+1
  • (X,Y)m

    Ejemplo:

w=2,(X,Y)=(0,1),m=(4,5,41,2,3)M=(0,0,04,5,41,2,3)
  • Probamos si podemos completar la matriz de modo que sea centrosimétrica.

    Ejemplo:

M=(3,2,14,5,41,2,3)
  • w
Arnauld
fuente
1

Jalea , 27 bytes

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

Pruébalo en línea!

Se agregaron nuevas líneas a la salida real sobre TIO para mayor claridad.

Erik el Outgolfer
fuente
1

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

Pruébalo en línea!


Salvado:

  • -1 byte, gracias a Jonathan Frech
TFeld
fuente
n=[W*[0]for _ in r(W)]puede ser n=eval(`[W*[0]]*W`).
Jonathan Frech
@JonathanFrech Gracias :)
TFeld
1

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

Pruébalo en línea!

Lispy Louie
fuente