Generuj macierze binarne, które są odrębne aż do odbić

14

Oto wszystkie macierze binarne 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  

Dwie binarne macierze kwadratowe są równoważne pod tą relacją, ~jeśli jedną można odwzorować na drugiej za pomocą dowolnej liczby odbić w osiach poziomych lub pionowych .

#1 ~ #2odbijane w osi pionowej, więc musimy zachować tylko jeden z nich (nie ma znaczenia, który). Podobnie #3 ~ #12, #6 ~ #9i tak dalej.

CELEM jest stworzenie programu, który pobiera jedno wejście Ni wypisuje tyle N x Nistniejących macierzy binarnych, że wszystkie macierze na wyjściu są różne w powyższej relacji.

W pseudokodzie pofalowanym ręką byłoby dopuszczalne rozwiązanie

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

Dla danych wejściowych N=2jednym prawidłowym wyjściem byłoby

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

Ale wybierając różne macierze z tej samej klasy równoważności, uzyskałoby inne prawidłowe dane wyjściowe

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

Kolejność macierzy nie ma znaczenia, szczególny wybór z ekwiwalentnych macierzy nie ma znaczenia, a białe znaki nie mają znaczenia, wysyłaj macierze tak, jak chcesz, o ile jest to czytelne dla człowieka.

Dane wyjściowe muszą być wyczerpujące.

Najkrótszy kod wygrywa.

EDYCJA: to jest mój pierwszy post golfowy i zmieniłem zdanie na temat kryteriów wygranej.

Najkrótszy kod w języku nieprzeznaczonym specjalnie dla zwięzłości / gry w golfa wygrywa.

Mam nadzieję, że zmiana tego kryterium post hoc nie jest złą etykietą, ale myślę, że zrobienie tego w „normalnym” języku jest znacznie ciekawszą propozycją.

spraff
źródło
5
Witamy w PPCG! To miłe pierwsze wyzwanie, ale zalecam, aby ludzie wypisywali wynik w elastycznym formacie (np. Każda macierz jako lista list). W ten sposób ludzie mogą skoncentrować się na bardzo interesującym rdzeniu wyzwania (znajdowaniu unikalnych matryc aż do symetrii) zamiast martwić się także o sformatowanie danych wyjściowych (co może zająć tyle samo bajtów i sprawić, że gra w golfa w głównym wyzwaniu będzie mniejsza ważny).
Martin Ender
Dziękuję za opinię, odpowiednio zmodyfikowałem pytanie.
spraff
2
Kusiło mnie, aby uwzględnić rotacje jako równoważność. Kusiło mnie również, aby włączyć odwracanie każdego bitu jako ekwiwalentu. Kusiło mnie również, aby uwzględnić permutacje wierszy / kolumn jako równoważność. Ostatecznie podjąłem arbitralną decyzję, aby wymagania były dość proste. Możesz opublikować odmianę.
spraff
1
Omówiliśmy to w przeszłości i rządził przed wyłączeniem lub karania niektórych języków w konkursach kod golfowych, co oznacza, że wyzwanie to zrobić należy uznać za off topic. Co więcej, przyjęta odpowiedź jest odpowiedzią, która wygrywa wyzwanie , co oznacza najkrótszy kod pytań golfowych. Podsumowując: Jeśli nie chcesz przyjąć żadnej odpowiedzi w ogóle , to nie. Jeśli jednak zaakceptujesz odpowiedź, musi ona być najkrótsza.
Dennis,
1
Wreszcie język J to nie język golfa, ale na wysokim poziomie, ogólnego przeznaczenia, wysoka wydajność język programowania, który istnieje od 25 lat. Nawet przy obecnych zasadach nadal przyjmujesz złą odpowiedź.
Dennis,

Odpowiedzi:

1

J, 66 56 53 bajtów

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

Poszukiwanie siły brutalnej.

Stosowanie

   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

Wyjaśnienie

[:~.,~{.@/:~@(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
mile
źródło
4

Galaretka , 19 bajtów

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

Wypróbuj online!

Jak to działa

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
źródło
2

Pyth - 24 23 21 bajtów

Chcę poszukać lepszego sposobu na uzyskanie wszystkich odbić.

Dzięki @ Pietu1998 za grę w golfa 2 bajty!

hM.gS+K_Bk_MMKcRQ^`T*

Wypróbuj online tutaj .

.gCzekasz na grę w golfa, zanim zrobisz pełne wyjaśnienie, ale zasadniczo tworzy wszystkie możliwe macierze binarne, a następnie routuje je według posortowanej listy wszystkich możliwych odbić, a następnie bierze tylko jedną z każdej grupy.

Maltysen
źródło
Jeśli uruchomię to z argumentem, 3wyjście zaczyna [['000', '000', '00'],zanotować brakujące zero na końcu.
spraff
@spraff ups, zrobiłem ^2Qzamiast Q^2. fix oszczędza mi też bajt: D
Maltysen
@spraff to naprawił.
Maltysen
Jestem pewien, że możesz to zrobić _MMzamiast mC_Cd.
PurkkaKoodari
@ Pietu1998 o tak, dzięki!
Maltysen
1

Haskell, 100 bajtów

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

Przykład użycia: f 2-> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

Jak to działa:

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
źródło
1

JavaScript (ES6), 195 bajtów

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

Zwraca łańcuchy reprezentujące wszystkie pozycje macierzy skonkatenowane, np. 111101111Reprezentuje macierz 3 × 3 1s 0zw środku. Wyjaśnienie:

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
źródło
Rekurencyjna funkcja numer do binarnej ma dokładnie tę samą długość:.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
ETHproductions
1

Mathematica, 94 bajty

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
JungHwan Min
źródło
1
Cześć JHM! Dziękuję za odpowiedź. Nie rozumiem dobrze Mathematiki, więc czy mógłbyś dodać trochę wyjaśnienia, co się dzieje? (Zamieściłem to samo w innej ostatniej odpowiedzi. Podanie wyjaśnienia jest dużym oczekiwaniem na odpowiedzi na tej stronie)
isaacg
0

JavaScript (ES6), 184

Okazało się, że jest dość podobny do Neila, ale cała masa sztuczek w javascript nie jest tak różnorodna.

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

Mniej golfa

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 Uwaga, nawet dla wejścia 4 czas działania jest zbyt długi

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
źródło