Minimal Sentrosimetriisasi

11

Terkait secara topikal.

Tujuan: Diberikan matriks bilangan bulat positif , menghasilkan matriks sentrosimetri terkecil yang mengandung (matriks ini juga mengandung bilangan bulat tidak positif).M.MM

Matriks centrosymmetric adalah matriks persegi dengan simetri rotasi orde 2 — yaitu tetap matriks yang sama setelah diputar dua kali. Misalnya, matriks centrosymmetric memiliki elemen kiri atas sama dengan kanan bawah, dan elemen di atas pusat sama dengan yang di bawah pusat. Visualisasi yang bermanfaat dapat ditemukan di sini .

Lebih formal, diberikan matriks , menghasilkan matriks persegi sehingga adalah centrosymmetric dan , dan tidak ada matriks persegi lain sehingga .N N M N K redup K < redup NMNNMNKdimK<dimN

B A B A i , j B i + i , j + j ( i , j )A adalah himpunan bagian dari (notasi: ) jika dan hanya jika setiap nilai muncul di indeks untuk beberapa pasang bilangan bulat .BABAi,jBi+i,j+j(i,j)

Catatan : beberapa matriks memiliki beberapa solusi (misalnya [[3,3],[1,2]]diselesaikan sebagai [[2,1,0],[3,3,3],[0,1,2]]atau [[3,3,3],[1,2,1],[3,3,3]]); Anda harus mengeluarkan setidaknya satu dari solusi yang valid.

Uji kasus

input
example output

[[1, 2, 3],
 [4, 5, 6]]
[[1, 2, 3, 0],
 [4, 5, 6, 0],
 [0, 6, 5, 4],
 [0, 3, 2, 1]]

[[9]]
[[9]]

[[9, 10]]
[[9, 10],
 [10, 9]]

[[100, 200, 300]]
[[100, 200, 300],
 [  0,   0,   0],
 [300, 200, 100]]

[[1, 2, 3],
 [4, 5, 4]]
[[1, 2, 3],
 [4, 5, 4]
 [3, 2, 1]]

[[1, 2, 3],
 [5, 6, 5],
 [3, 2, 1]]
[[1, 2, 3],
 [5, 6, 5],
 [3, 2, 1]]

[[4, 5, 4],
 [1, 2, 3]]
[[3, 2, 1],
 [4, 5, 4],
 [1, 2, 3]]

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1]]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [1, 1, 1, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 9, 9, 9, 9, 9, 9, 9, 1, 1, 1],
 [9, 9, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
Conor O'Brien
sumber
Mengapa matriks Centrosymmetric harus persegi?
Ad Hoc Garf Hunter
@ HP secara umum, saya kira tidak harus begitu. Untuk pertanyaan ini, bagaimanapun, mereka harus kuadrat menurut definisi
Conor O'Brien
Saya bertanya-tanya mengapa Anda membuat pilihan itu
Ad Hoc Garf Hunter
2
@WW itu adalah penyederhanaan yang saya pikir berguna untuk kejelasan
Conor O'Brien

Jawaban:

8

Brachylog , 12 byte

ṁ↔ᵐ↔?aaᵐ.&≜∧

Cobalah online!

Berlawanan dengan sebagian besar jawaban Brachylog, ini mengambil input melalui variabel Output ., dan output hasilnya melalui variabel Input ?(membingungkan, saya tahu).

Penjelasan

ṁ              We expect a square matrix
 ↔ᵐ↔?          When we reverse the rows and then the matrix, we get the initial matrix back
    ?a         Take an adfix (prefix or suffix) of that square matrix
      aᵐ       Take an adfix of each row of that adfix matrix
        .      It must be the input matrix
         &≜    Assign values to cells which are still variables (will assign 0)
           ∧   (disable implicit unification between the input and the output)

8 byte, memberikan semua matriks yang valid

Secara teknis, program ini juga berfungsi:

ṁ↔ᵐ↔?aaᵐ

Tapi ini akan meninggalkan sebagai sel-sel variabel yang dapat mengambil nilai apa pun (mereka menunjukkan _XXXXX, yang merupakan nama variabel Prolog internal). Jadi secara teknis ini bahkan lebih baik daripada apa yang diminta, tapi saya kira itu bukan tantangan yang diminta.

Fatalisasi
sumber
Saya berharap tidak menunda pelabelan ...
Erik the Outgolfer
@EriktheOutgolfer Pelabelan instan masih berguna ketika kita perlu menghitung hal-hal, jadi idealnya kita membutuhkan dua predikat yang berbeda ...
Fatalize
4

JavaScript (ES6), 192 180 177 byte

f=(m,v=[w=0],S=c=>v.some(c))=>S(Y=>S(X=>!m[w+1-Y]&!m[0][w+1-X]&!S(y=>S(x=>(k=(m[y-Y]||0)[x-X],g=y=>((r=a[y]=a[y]||[])[x]=r[x]||k|0)-k)(y)|g(w-y,x=w-x)),a=[])))?a:f(m,[...v,++w])

Cobalah online!

Algoritma

Dimulai dengan :w=0

  • Kami menganggap matriks kontainer persegi dengan lebar .Mw+1
  • Kami menganggap setiap pasangan sedemikian rupa sehingga matriks input dapat masuk dalam matriks wadah ketika dimasukkan pada koordinat ini.(X,Y)m

    Contoh:

w=2,(X,Y)=(0,1),m=(4,5,41,2,3)M=(0,0,04,5,41,2,3)
  • Kami menguji apakah kami dapat menyelesaikan matriks sedemikian rupa sehingga bersifat centrosymmetric.

    Contoh:

M=(3,2,14,5,41,2,3)
  • Kami kenaikan sampai kami menemukan konfigurasi seperti valid.w
Arnauld
sumber
1

Jelly , 27 byte

oZ0ṁz0o⁸ṚUŻ€Z$2¡LСo⁸ṚU$ƑƇḢ

Cobalah online!

Baris baru ditambahkan ke output aktual daripada TIO untuk kejelasan.

Erik the Outgolfer
sumber
1

Python 2 , 242 227 226 byte

r=range
def f(m):
 w,h=len(m),len(m[0]);W=max(w,h)
 while 1:
	for x in r(1+W-w):
	 for y in r(1+W-h):
		n=n=eval(`[W*[0]]*W`);exec"for i in r(w):n[i+x][y:y+h]=m[i]\nN=n;n=[l[::-1]for l in n[::-1]]\n"*2
		if n==N:return n
	W+=1

Cobalah online!


Diselamatkan:

  • -1 byte, terima kasih kepada Jonathan Frech
TFeld
sumber
n=[W*[0]for _ in r(W)]bisa n=eval(`[W*[0]]*W`).
Jonathan Frech
@JonathanFrech Terima kasih :)
TFeld
1

Clojure 254 byte

(defn e[l m](let[a map v reverse r repeat t concat c count f #(v(a v %))h(fn[x](t(a #(t %(r(- l(c(first x)))0))x)(r(- l(c m))(r l 0))))k(fn[x](a(fn[v w](a #(if(= %2 0)%1 %2)v w))x(f x)))n(k(h m))o(k(h(f m)))z #(= %(f %))](if(z n)n(if(z o)o(e(inc l)m)))))

Jinkies, Scoob

Cobalah online!

Lispy Louie
sumber