Hasilkan matriks biner yang berbeda hingga refleksi

14

Berikut adalah semua matriks biner 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  

Dua matriks persegi biner setara di bawah relasi ~jika satu dapat dipetakan ke yang lain dengan sejumlah pantulan dalam sumbu horizontal atau vertikal .

#1 ~ #2di bawah refleksi dalam sumbu vertikal sehingga kita hanya perlu menyimpan salah satunya (tidak masalah yang mana). Demikian juga #3 ~ #12, #6 ~ #9dan seterusnya.

TUJUANnya adalah untuk menghasilkan program yang mengambil input tunggal Ndan mencetak N x Nmatriks biner sebanyak yang ada sehingga semua matriks dalam output berbeda di bawah hubungan di atas.

Dalam pseudocode gelombang tangan, solusi yang dapat diterima adalah

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

Untuk input, N=2satu output yang valid adalah

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

Tetapi dengan memilih matriks yang berbeda dari kelas ekivalensi yang sama output yang valid akan menjadi

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

Urutan matriks tidak masalah, pilihan khusus dari matriks setara tidak masalah, dan spasi putih tidak masalah, output matriks sesuka Anda selama itu dapat dibaca oleh manusia.

Outputnya harus lengkap.

Kode terpendek menang.

EDIT: ini adalah posting golf pertama saya dan saya berubah pikiran tentang kriteria kemenangan.

Kode terpendek dalam bahasa yang tidak dirancang khusus untuk kemenangan singkat / bermain golf .

Saya harap itu bukan etiket buruk untuk mengubah kriteria ini post-hoc, tapi saya pikir melakukannya dalam bahasa "normal" adalah proposisi yang jauh lebih menarik .

Spraff
sumber
5
Selamat datang di PPCG! Ini adalah tantangan pertama yang bagus, tetapi saya akan merekomendasikan membiarkan orang menampilkan hasilnya dalam format yang fleksibel (misalnya setiap matriks sebagai daftar daftar). Dengan begitu orang dapat fokus pada inti tantangan yang sangat menarik (menemukan matriks unik hingga simetri) alih-alih juga harus khawatir tentang memformat output (yang dapat dengan mudah mengambil banyak byte dan membuat bermain golf dari tantangan utama kurang penting).
Martin Ender
Terima kasih atas umpan baliknya, Anda berdua, saya telah mengedit pertanyaan yang sesuai.
spraff
2
Saya tergoda untuk memasukkan rotasi sebagai kesetaraan. Saya juga tergoda untuk memasukkan pembalik setiap bit sebagai persamaan. Saya juga tergoda untuk memasukkan permutasi baris / kolom sebagai kesetaraan. Pada akhirnya, saya membuat keputusan sewenang-wenang untuk menjaga persyaratannya tetap sederhana. Jangan ragu untuk mengirim variasi.
spraff
1
Kami telah membahas ini di masa lalu dan memutuskan untuk tidak memasukkan atau menghukum bahasa tertentu dalam kompetisi golf kode, yang berarti bahwa tantangan yang melakukannya harus dianggap di luar topik. Selanjutnya, jawaban yang diterima adalah jawaban yang memenangkan tantangan , yang berarti kode terpendek untuk pertanyaan golf kode. Meringkas: Jika Anda tidak ingin menerima jawaban sama sekali , maka jangan. Namun, jika Anda menerima jawaban, itu harus yang paling pendek.
Dennis
1
Akhirnya, bahasa J adalah tidak bahasa golf, tetapi tingkat tinggi, tujuan umum, kinerja tinggi bahasa pemrograman yang telah ada selama 25 tahun. Bahkan dengan aturan Anda saat ini, Anda masih menerima jawaban yang salah.
Dennis

Jawaban:

1

J, 66 56 53 byte

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

Pencarian dengan kekerasan.

Pemakaian

   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

Penjelasan

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

Jelly , 19 byte

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

Cobalah online!

Bagaimana itu bekerja

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
sumber
2

Pyth - 24 23 21 byte

Ingin mencari cara yang lebih baik untuk mendapatkan semua refleksi.

Terima kasih kepada @ Pietu1998 karena golf saya 2 byte!

hM.gS+K_Bk_MMKcRQ^`T*

Cobalah online di sini .

Pergi menunggu untuk bermain golf sebelum melakukan penjelasan lengkap, tetapi pada dasarnya membuat semua matriks biner yang mungkin, kemudian .gmemperbaiki mereka dengan daftar diurutkan dari semua refleksi yang mungkin, kemudian hanya mengambil satu dari masing-masing kelompok.

Maltysen
sumber
Jika saya menjalankannya dengan argumen 3, output mulai [['000', '000', '00'],mencatat nol yang hilang di akhir.
spraff
@spraff ups, saya lakukan ^2Qbukan Q^2. memperbaiki menyelamatkan saya byte juga: D
Maltysen
@spraff memperbaikinya.
Maltysen
Aku cukup yakin Anda dapat melakukan _MMbukan mC_Cd.
PurkkaKoodari
@ Pietu1998 oh yeah, terima kasih!
Maltysen
1

Haskell, 100 byte

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

Contoh penggunaan: f 2-> [["00","00"],["00","01"],["00","11"],["01","01"],["01","10"],["01","11"],["11","11"]].

Bagaimana itu bekerja:

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
sumber
1

JavaScript (ES6), 195 byte

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

Mengembalikan string yang mewakili semua entri matriks yang disatukan misalnya 111101111mewakili matriks 3 × 3 1s dengan a 0di tengah. Penjelasan:

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
sumber
Fungsi bilangan-ke-biner rekursif memiliki panjang yang persis sama:.map(f=(x=p++)=>x>1?f(x>>1)+x%2:"")
ETHproduksi
1

Mathematica, 94 byte

DeleteDuplicatesBy[{0,1}~Tuples~{#,#},Sort@Join[Join@@Outer[Reverse,{#},{1,2,{1,2}},1],{#}]&]&
JungHwan Min
sumber
1
Hai JHM! Terima kasih atas jawabannya. Saya tidak mengerti Mathematica dengan baik, jadi bisakah Anda menambahkan sedikit penjelasan tentang apa yang terjadi? (Saya memposting hal yang sama pada jawaban terakhir Anda yang lain. Memberi penjelasan adalah harapan yang kuat untuk jawaban di situs ini)
isaacg
0

JavaScript (ES6), 184

Ini ternyata sangat mirip dengan Neil, tetapi semuanya trik javascript tidak begitu beragam.

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

Kurang 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
}

Uji Hati-hati, bahkan untuk input 4 waktu berjalan terlalu lama

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
sumber