Aquí están todas las matrices binarias 2x2
#0 #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13 #14 #15
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11
Dos matrices cuadradas binarias son equivalentes bajo la relación ~
si una puede mapearse sobre la otra por cualquier número de reflexiones en los ejes horizontal o vertical .
#1 ~ #2
bajo reflexión en el eje vertical, por lo que solo necesitamos mantener uno de estos (no importa cuál). Del mismo modo #3 ~ #12
, #6 ~ #9
y así sucesivamente.
EL OBJETIVO es producir un programa que tome una sola entrada N
e imprima tantas N x N
matrices binarias como existan, de modo que todas las matrices en la salida sean distintas bajo la relación anterior.
En el pseudocódigo wavey manual, una solución admisible sería
define M[i] = N by N matrix with bit pattern equal to i
for i = 0 to (2^(N^2)) - 1
valid = true
for j = i+1 to (2^(N^2)) - 1
if (equivalent(M[i], M[j]))
valid = false
break
if (valid)
print (M[i])
Para la entrada, N=2
una salida válida sería
00 00 00 01 10 01 11
00 01 11 01 01 11 11
Pero al seleccionar diferentes matrices de la misma clase de equivalencia, otra salida válida sería
00 10 11 11 11 10 01
00 00 00 10 11 10 10
El orden de las matrices no importa, la elección particular de las matrices equivalentes no importa, y el espacio en blanco no importa, genera las matrices como quieras, siempre y cuando sea legible para los humanos.
La salida debe ser exhaustiva.
El código más corto gana.
EDITAR: esta es mi primera publicación de golf y he cambiado de opinión sobre los criterios ganadores.
El código más corto en un idioma no diseñado específicamente para la concisión / el golf gana.
Espero que no sea una mala etiqueta cambiar este criterio post-hoc, pero creo que hacerlo en un lenguaje "normal" es una propuesta mucho más interesante .
Respuestas:
J,
665653 bytesBúsqueda de fuerza bruta.
Uso
Explicación
fuente
Jalea , 19 bytes
Pruébalo en línea!
Cómo funciona
fuente
Pyth -
242321 bytes¿Quieres buscar una mejor manera de obtener todos los reflejos?¡Gracias a @ Pietu1998 por jugarme 2 bytes!
Pruébelo en línea aquí .
Espera a jugar al golf antes de hacer una explicación completa, pero esencialmente hace todas las matrices binarias posibles, luego las
.g
enruta por la lista ordenada de todas las reflexiones posibles, luego solo toma una de cada grupo.fuente
3
la salida comienza,[['000', '000', '00'],
observe el cero faltante al final.^2Q
lugar deQ^2
. arreglar también me ahorra un byte: D_MM
lugar demC_Cd
.Haskell, 100 bytes
Ejemplo de uso:
f 2
->[["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]]
.Cómo funciona:
fuente
JavaScript (ES6), 195 bytes
Devuelve cadenas que representan todas las entradas de matriz concatenadas, por ejemplo,
111101111
representa una matriz de 3 × 3 de1
s con un0
en el medio. Explicación:fuente
.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
Mathematica, 94 bytes
fuente
JavaScript (ES6), 184
Esto resultó ser bastante similar al de Neil, pero en general, la bolsa de trucos en JavaScript no es tan diversa.
Menos golf
Test Beware, incluso para la entrada 4, el tiempo de ejecución es demasiado largo
fuente