Générer des matrices binaires distinctes jusqu'aux réflexions

14

Voici toutes les matrices binaires 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  

Deux matrices carrées binaires sont équivalentes sous la relation ~si l'une peut être mappée sur l'autre par un nombre quelconque de réflexions dans les axes horizontal ou vertical .

#1 ~ #2en réflexion dans l'axe vertical, il suffit donc d'en garder un (peu importe lequel). De même #3 ~ #12, #6 ~ #9et ainsi de suite.

L'OBJECTIF est de produire un programme qui prend une seule entrée Net imprime autant de N x Nmatrices binaires qu'il en existe de sorte que toutes les matrices en sortie soient distinctes sous la relation ci-dessus.

Dans un pseudocode ondulé à la main, une solution admissible serait

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

Pour l'entrée, N=2une sortie valide serait

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

Mais en sélectionnant différentes matrices de la même classe d'équivalence, une autre sortie valide serait

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

L'ordre des matrices n'a pas d'importance, le choix particulier parmi les matrices équivalentes n'a pas d'importance et les espaces n'ont pas d'importance, affichez les matrices comme vous le souhaitez tant qu'elles sont lisibles par l'homme.

La sortie doit être exhaustive.

Le code le plus court gagne.

EDIT: ceci est mon premier article de golf et j'ai changé d'avis sur les critères gagnants.

Code le plus court dans une langue non spécifiquement conçue pour la concision / le golf gains de .

J'espère que ce n'est pas une mauvaise étiquette de changer ce critère post-hoc, mais je pense que le faire dans un langage "normal" est une proposition beaucoup plus intéressante .

vaporiser
la source
5
Bienvenue chez PPCG! C'est un beau premier défi, mais je recommanderais de laisser les gens produire le résultat dans un format flexible (par exemple, chaque matrice comme une liste de listes). De cette façon, les gens peuvent se concentrer sur le cœur très intéressant du défi (trouver les matrices uniques jusqu'aux symétries) au lieu d'avoir également à se soucier du formatage de la sortie (ce qui pourrait facilement prendre autant d'octets et rendre le golf du défi principal moins important).
Martin Ender
Merci pour vos commentaires, vous deux, j'ai modifié la question en conséquence.
pulvérisation
2
J'ai été tenté d'inclure les rotations comme équivalence. J'ai également été tenté d'inclure l'inversion de chaque bit comme équivalence. J'ai également été tenté d'inclure des permutations de lignes / colonnes comme équivalence. Au final, j'ai pris la décision arbitraire de garder les exigences assez simples. N'hésitez pas à poster une variation.
spraff
1
Nous avons discuté de cela dans le passé et avons décidé de ne pas exclure ou pénaliser certaines langues dans les compétitions de golf de code, ce qui signifie que le défi qui le fait devrait être considéré hors sujet. En outre, la réponse acceptée est la réponse qui remporte le défi , ce qui signifie le code le plus court pour les questions de golf de code. En résumé: si vous ne voulez pas accepter de réponse du tout , alors ne le faites pas. Cependant, si vous acceptez une réponse, elle doit être la plus courte.
Dennis
1
Enfin, le langage J n'est pas un langage de golf, mais un langage de programmation de haut niveau, polyvalent et performant qui existe depuis 25 ans. Même avec vos règles actuelles, vous avez toujours accepté la mauvaise réponse.
Dennis

Réponses:

1

J, 66 56 53 octets

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

Recherche par force brute.

Usage

   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

Explication

[:~.,~{.@/:~@(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
miles
la source
4

Gelée , 19 octets

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

Essayez-le en ligne!

Comment ça fonctionne

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
la source
2

Pyth - 24 23 21 octets

Je veux chercher un meilleur moyen d'obtenir toutes les réflexions.

Merci à @ Pietu1998 pour m'avoir joué au golf 2 octets!

hM.gS+K_Bk_MMKcRQ^`T*

Essayez-le en ligne ici .

Aller attendre le golf avant de faire une explication complète, mais cela fait essentiellement toutes les matrices binaires possibles, puis les .gregroupe par la liste triée de toutes les réflexions possibles, puis n'en prend qu'une dans chaque groupe.

Maltysen
la source
Si je lance cela avec un argument, 3la sortie commence à [['000', '000', '00'],noter le zéro manquant à la fin.
pulvérisation
@spraff whoops, je l'ai fait à la ^2Qplace de Q^2. correctif me fait gagner un octet aussi: D
Maltysen
@spraff l'a corrigé.
Maltysen
Je suis presque sûr que tu peux faire à la _MMplace de mC_Cd.
PurkkaKoodari
@ Pietu1998 oh ouais, merci!
Maltysen
1

Haskell, 100 octets

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

Exemple d'utilisation: f 2-> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

Comment ça fonctionne:

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
la source
1

JavaScript (ES6), 195 octets

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

Renvoie des chaînes représentant toutes les entrées de matrice concaténées, par exemple, 111101111représente une matrice 3 × 3 de 1s avec un 0au milieu. Explication:

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
la source
Une fonction récursive nombre-binaire a exactement la même longueur:.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
ETHproductions
1

Mathematica, 94 octets

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
JungHwan Min
la source
1
Salut JHM! Merci d'avoir répondu. Je ne comprends pas très bien Mathematica, pourriez-vous ajouter quelques explications sur ce qui se passe? (J'ai posté la même chose sur votre autre réponse récente. Donner quelques explications est une forte attente de réponses sur ce site)
isaacg
0

JavaScript (ES6), 184

Cela s'est avéré être assez similaire à celui de Neil, mais dans l'ensemble, le sac d'astuces en javascript n'est pas si diversifié.

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`")

Moins 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 Attention, même pour l' entrée 4 le temps d' exécution est trop long

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
la source