Generar matrices binarias que son distintas a las reflexiones.

14

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 ~ #2bajo 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 ~ #9y así sucesivamente.

EL OBJETIVO es producir un programa que tome una sola entrada Ne imprima tantas N x Nmatrices 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=2una 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 .

rociar
fuente
55
Bienvenido a PPCG! Este es un buen primer desafío, pero recomendaría dejar que las personas muestren el resultado en un formato flexible (por ejemplo, cada matriz como una lista de listas). De esa manera, las personas pueden centrarse en el núcleo muy interesante del desafío (encontrar matrices únicas hasta simetrías) en lugar de tener que preocuparse por formatear la salida (que fácilmente podría tomar la misma cantidad de bytes y reducir el desafío principal. importante).
Martin Ender
Gracias por los comentarios, los dos, he editado la pregunta en consecuencia.
rociar el
2
Estuve tentado de incluir rotaciones como una equivalencia. También tuve la tentación de incluir la inversión de cada bit como una equivalencia. También tuve la tentación de incluir permutaciones de filas / columnas como una equivalencia. Al final, tomé una decisión arbitraria de mantener los requisitos bastante simples. Siéntase libre de publicar una variación.
rociar
1
Hemos discutido esto en el pasado y dictaminamos en contra de excluir o penalizar ciertos idiomas en las competiciones de golf de código, lo que significa que el desafío que debe hacerse debe considerarse fuera de tema. Además, la respuesta aceptada es la respuesta que gana el desafío , lo que significa el código más corto para las preguntas de código de golf. Resumiendo: Si no desea aceptar ninguna respuesta en absoluto , entonces no. Sin embargo, si acepta una respuesta, debe ser la más corta.
Dennis
1
Finalmente, el lenguaje J no es un lenguaje de golf, sino un lenguaje de programación de alto nivel, propósito general y alto rendimiento que ha existido durante 25 años. Incluso con sus reglas actuales, aún ha aceptado la respuesta incorrecta.
Dennis

Respuestas:

1

J, 66 56 53 bytes

[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:

Búsqueda de fuerza bruta.

Uso

   f =: [:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:
   f 2
┌───┬───┬───┬───┬───┬───┬───┐
│0 0│0 0│0 0│0 1│0 1│0 1│1 1│
│0 0│0 1│1 1│0 1│1 0│1 1│1 1│
└───┴───┴───┴───┴───┴───┴───┘
   # f 3
168
   # f 4
16576

Explicación

[:~.,~{.@/:~@(2:_&(][:,(;|.;|."1)&>)<)@$"#.2#:@i.@^*:  Input: integer n
                                                   *:  Square n
                                           2      ^    Compute m = 2 ^ (n ^ 2)
                                               i.@     Make a range [0, m)
                                            #:@        Convert each to binary digits
    ,~                                                    Pair, make [n, n]
                                       $"#.            Reshape each binary list
                                                          to a matrix with size [n, n]
             (                       )@                Operate on each
                                    <                    Box it, call x
              2:                                         The constant 2
                _&(                )                     Repeat that many times on x
                       (        )&>                        For each box
                            |."1                             Reverse by column
                         |.                                  Reverse by row
                           ;                                 Join them
                        ;                                    Join with initial
                    [:,                                    Flatten
                   ]                                       Return that as the new x
         /:~@                                          Sort each
      {.@                                              Take the head of each
[:~.                                                   Unique and return
millas
fuente
4

Jalea , 19 bytes

Ṛ€;U;
2ḶṗṗµWdz¡Ṃµ€Q

Pruébalo en línea!

Cómo funciona

2ḶṗṗµWdz¡Ṃµ€Q  Main link. Argument: n (integer)

2Ḷ             Unlength 2; yield [0, 1].
  ṗ            Cartesian product; construct all vectors of {0, 1}^n.
   ṗ           Cartesian product; construct all vectors of ({0, 1}^n)^n.
               This yields A, the array of all binary n×n matrices.
    µ     µ€   Begin a new, monadic chain and apply it to all matrices M in A.
     W           Wrap; yield [M].
      dz¡        Call the helper link n times, initially with argument [M], then
                 on the previous return value.
         Ṃ       Take the minimum of the results.
               This replaces all matrices with the lexicographical minimum of their
               equivalence classes, mapping equivalent matrices to the same matrix.
            Q  Unique; deduplicate the resulting array of matrices.

Ṛ€;U;          Helper link. Argument: L (array of matrices)

Ṛ€             Reverse the order of the rows of each M in L.
   U           Reverse the order of the columns of each M in L.
  ;            Concatenate the resulting matrix arrays.
    ;          Concatenate the result with L.
Dennis
fuente
2

Pyth - 24 23 21 bytes

¿Quieres buscar una mejor manera de obtener todos los reflejos?

¡Gracias a @ Pietu1998 por jugarme 2 bytes!

hM.gS+K_Bk_MMKcRQ^`T*

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 .genruta por la lista ordenada de todas las reflexiones posibles, luego solo toma una de cada grupo.

Maltysen
fuente
Si ejecuto eso con argumento, 3la salida comienza, [['000', '000', '00'],observe el cero faltante al final.
rociar el
@spraff whoops, lo hice en ^2Qlugar de Q^2. arreglar también me ahorra un byte: D
Maltysen
@spraff lo arregló.
Maltysen
Estoy bastante seguro de que puedes hacer en _MMlugar de mC_Cd.
PurkkaKoodari
@ Pietu1998 oh si, gracias!
Maltysen
1

Haskell, 100 bytes

import Data.List
r=reverse
e#n=mapM id$e<$[1..n]
f n=nubBy(\a b->elem a[r b,r<$>b,r$r<$>b])$"01"#n#n

Ejemplo de uso: f 2-> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

Cómo funciona:

e#n=mapM id$e<$[1..n]        -- helper function: creates a list of all combinations
                             -- of the elements of e of length n
                             -- "01" # 2 -> ["00","01","10","11"]

                   "01"#n#n  -- creates all binary n x n matrices
nubBy                        -- remove duplicates according to the equivalence
                             -- relation
   \a b ->                   -- a equals b if
       a elem                -- a is an element of
         [r b,r<$>b,r$r<$>b] -- the list of reflections of b 
nimi
fuente
1

JavaScript (ES6), 195 bytes

n=>[...Array(p=1<<n*n)].map(_=>(p++).toString(2).slice(1)).filter((s,i,a)=>![1,0,1].some(c=>a.indexOf((c?b.reverse():b=b.map(s=>[...s].reverse().join``)).join``)<i,b=s.match(eval(`/.{${n}}/g`))))

Devuelve cadenas que representan todas las entradas de matriz concatenadas, por ejemplo, 111101111representa una matriz de 3 × 3 de 1s con un 0en el medio. Explicación:

n=>[...Array(p=1<<n*n)].map(            Enumerate all binary matrices
 _=>(p++).toString(2).slice(1)          Convert to padded binary
).filter((s,i,a)=>![1,0,1].some(        Check reflections of each matrix
 c=>a.indexOf((c?b.reverse():           Reverse the order of lines
  b=b.map(s=>[...s].reverse().join``    Or reverse each line
  )).join``)<i,                         Has this been seen before?
 b=s.match(eval(`/.{${n}}/g`))))        Reshape string into a square
Neil
fuente
Una función recursiva de número a binario tiene exactamente la misma longitud:.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
ETHproductions
1

Mathematica, 94 bytes

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
JungHwan Min
fuente
1
Hola jhm Gracias por la respuesta. No entiendo muy bien Mathematica, ¿podría agregar un poco de explicación sobre lo que está pasando? (Publiqué lo mismo en su otra respuesta reciente. Dar alguna explicación es una gran expectativa de respuestas en este sitio)
isaacg
0

JavaScript (ES6), 184

Esto resultó ser bastante similar al de Neil, pero en general, la bolsa de trucos en JavaScript no es tan diversa.

n=>eval("r=x=>[...x].reverse();for(l='',i=m=1<<n*n;i<m+m;i++)a=i.toString(2).slice(1).match(eval(`/.{${n}}/g`)),[b=a.map(x=>r(x).join``),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+`\n`")

Menos golf

n=>{
  r = x =>[...x].reverse();
  for(l = '', i = m = 1<<n*n; i < m+m; i++)
    a = i.toString(2).slice(1).match(eval(`/.{${n}}/g`)), // base matrix as an array of strings
    b = a.map(x => r(x).join``), // horizontal reflection
    c = r(a), // vertical reflection
    d = r(b), // both reflections
    // check if already found 
    [b, c, d].some(x => ~l.search(x)) // using search, arrays are converted to comma separated strings 
      ? 0 
      : l += a+`\n` // add new found to list (again as a comma separated string)
  return l
}

Test Beware, incluso para la entrada 4, el tiempo de ejecución es demasiado largo

f=n=>eval("r=x=>[...x].reverse();for(l='',i=m=1<<n*n;i<m+m;i++)a=i.toString(2).slice(1).match(eval(`/.{${n}}/g`)),[b=a.map(x=>r(x).join``),r(a),r(b)].some(x=>~l.search(x))?0:l+=a+`\n`")

function update() {
  var i=+I.value;
  
  result = f(i)
  count = result.split('\n').length
  O.textContent = count+'\n'+result
}

update()
Input <select id=I onchange="update()"><option>2<option>3<option>4<option>5</select>
<pre id=O></pre>

edc65
fuente