Gere matrizes binárias que são distintas até reflexões

14

Aqui estão todas as matrizes binárias 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  

Duas matrizes quadradas binárias são equivalentes sob a relação ~se uma puder ser mapeada na outra por qualquer número de reflexões nos eixos horizontal ou vertical .

#1 ~ #2sob reflexão no eixo vertical, portanto, precisamos manter apenas um deles (não importa qual). Da mesma forma #3 ~ #12, #6 ~ #9e assim por diante.

O objetivo é produzir um programa que use uma única entrada Ne imprima quantas N x Nmatrizes binárias existirem, de modo que todas as matrizes na saída sejam distintas na relação acima.

No pseudocódigo de onda manual, uma solução admissível seria

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 a entrada, N=2uma saída válida seria

00  00  00  01  10  01  11
00  01  11  01  01  11  11

Mas, selecionando matrizes diferentes da mesma classe de equivalência, outra saída válida seria

00  10  11  11  11  10  01
00  00  00  10  11  10  10

A ordem das matrizes não importa, a escolha específica de matrizes equivalentes não importa e o espaço em branco não importa, produz as matrizes da maneira que você quiser, desde que seja legível por humanos.

A saída deve ser exaustiva.

O menor código vence.

EDIT: este é o meu primeiro post de golfe e mudei de idéia sobre os critérios de vitória.

Código mais curto em um idioma não projetado especificamente para ganhos de concisão / golfe .

Espero que não seja má etiqueta mudar esse critério post-hoc, mas acho que fazê-lo em uma linguagem "normal" é uma proposta muito mais interessante .

spraff
fonte
5
Bem-vindo ao PPCG! Esse é um bom primeiro desafio, mas eu recomendo deixar que as pessoas produzam o resultado em um formato flexível (por exemplo, cada matriz como uma lista de listas). Dessa forma, as pessoas podem se concentrar no núcleo muito interessante do desafio (encontrar as matrizes únicas até simetrias), em vez de também terem que se preocupar em formatar a saída (o que poderia facilmente levar tantos bytes e tornar o golfe do desafio principal menos importante).
Martin Ender
Obrigado pelo feedback, vocês dois, editei a pergunta de acordo.
spraff
2
Fiquei tentado a incluir rotações como equivalência. Também fiquei tentado a incluir a inversão de cada bit como uma equivalência. Também fiquei tentado a incluir permutações de linhas / colunas como equivalência. No final, tomei uma decisão arbitrária para manter os requisitos bastante simples. Sinta-se livre para postar uma variação.
spraff
1
Discutimos isso no passado e decidimos não excluir ou penalizar determinados idiomas em competições de código de golfe, o que significa que o desafio que o faz deve ser considerado fora de tópico. Além disso, a resposta aceita é a resposta que vence o desafio , o que significa o menor código para as perguntas sobre códigos de golfe. Resumindo: Se você não quer aceitar nenhuma resposta em tudo , então não. No entanto, se você aceitar uma resposta, ela deverá ser a mais curta.
Dennis
1
Finalmente, a linguagem J não é uma linguagem de golfe, mas uma linguagem de programação de alto nível, de uso geral e de alto desempenho, que existe há 25 anos. Mesmo com suas regras atuais, você ainda aceitou a resposta errada.
Dennis

Respostas:

1

J, 66 56 53 bytes

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

Pesquisa por força 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

Explicação

[:~.,~{.@/:~@(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
milhas
fonte
4

Geléia , 19 bytes

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

Experimente online!

Como 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
fonte
2

Pyth - 24 23 21 bytes

Quero procurar uma maneira melhor de obter todas as reflexões.

Graças a @ Pietu1998 por me jogar 2 bytes!

hM.gS+K_Bk_MMKcRQ^`T*

Experimente online aqui .

Esperar pelo golfe antes de fazer uma explicação completa, mas essencialmente cria todas as matrizes binárias possíveis, depois as .grouba pela lista ordenada de todas as reflexões possíveis e, em seguida, leva apenas uma de cada grupo.

Maltysen
fonte
Se eu executar isso com argumento, 3a saída começará, [['000', '000', '00'],observe o zero ausente no final.
spraff
gritos @spraff, eu fiz em ^2Qvez de Q^2. A correção também me salva um byte: D
Maltysen 4/16
@spraff corrigiu.
Maltysen 4/10
Tenho certeza que você pode fazer em _MMvez de mC_Cd.
PurkkaKoodari #
@ Pietu1998 oh sim, obrigado!
Maltysen 5/10
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

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

Como 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
fonte
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`))))

Retorna strings representando todas as entradas da matriz concatenadas, por exemplo, 111101111representa uma matriz 3 × 3 de 1s com a 0no meio. Explicação:

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
fonte
Uma função número-binário recursiva tem exatamente o mesmo comprimento:.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
fonte
1
Oi JHM! Obrigado pela resposta. Eu não entendo muito bem o Mathematica, então você poderia adicionar um pouco de explicação sobre o que está acontecendo? (Eu postei a mesma coisa em sua outra resposta recente Dando alguma explicação é uma forte expectativa de respostas neste site.)
isaacg
0

JavaScript (ES6), 184

Isso acabou sendo bem parecido com o de Neil, mas no conjunto de truques em javascript não é tão diverso.

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 golfe

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
}

Teste Cuidado, mesmo para a entrada 4, o tempo de execução é excessivamente longo

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
fonte