Memutar Matriks 2D

30

Katakanlah saya memiliki matriks (2D) berikut:

[[1,  2,  3,  4 ],
 [5,  6,  7,  8 ],
 [9,  10, 11, 12],
 [13, 14, 15, 16]]

Putar matriks berlawanan arah jarum jam R (tidak dalam peningkatan 90 derajat, hanya dengan 1 angka setiap kali),

1  2  3  4             2 3   4  8         3   4   8  12
5  6  7  8    -->      1 7  11 12   -->   2  11  10  16 
9  10 11 12            5 6  10 16         1   7   6  15 
13 14 15 16            9 13 14 15         5   9  13  14

Contoh lengkap:

Memasukkan:

2
[[1,  2,  3,  4 ],
 [5,  6,  7,  8 ],
 [9,  10, 11, 12],
 [13, 14, 15, 16]]

Keluaran:

[[3,  4,  8, 12],
 [2, 11, 10, 16],
 [1,  7,  6, 15],
 [5,  9, 13, 14]]

(spasi aneh adalah untuk menyelaraskan angka dalam kolom yang bagus)

"Cincin" luar matriks berputar 2 berlawanan arah jarum jam, dan kanan dalam berputar 2 juga. Dalam matriks ini, hanya ada dua cincin.

Contoh dengan 1 "dering":

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

Haruskah output:

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

Tantangan Anda adalah mengambil matriks dan integer R, dan mengeluarkan versi terjemahan setelah Rrotasi.

Rotasi matriks 4x5 diwakili oleh gambar berikut: masukkan deskripsi gambar di sini

Kendala:

  • 2 ≤ M, N ≤ 100, di mana M dan N adalah dimensi dari matriks. Dijamin bahwa minimum M dan N akan genap.
  • 1 ≤ R ≤ 80, di mana r adalah jumlah rotasi.
  • Matriks hanya akan berisi bilangan bulat positif.
  • Nilai tidak selalu berbeda.
  • Input harus selalu berupa array 2D (jika Anda tidak dapat mengambil input runtime sebagai array 2D, maka Anda hanya perlu menemukan cara lain untuk mendapatkan input).

Test case lain, dengan nilai yang tidak berbeda:

1
[[1, 1],
 [2, 2],
 [3, 3]]

Output:

[[1, 2],
 [1, 3],
 [2, 3]]

Ini , jadi jawaban terpendek menang!

StepUp
sumber
Terkait
Peter Taylor
Terkait
Martin Ender
2
Terkait
Berhenti berputar balik pada
4
@ceasedtoturncounterclockwis Nama Anda sangat ironis untuk tantangan ini ...
HyperNeutrino
1
[[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 16], [5, 9, 13, 14]]16 tiba-tiba digandakan saya kira itu harus: [[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 15], [5, 9, 13, 14]]?
Christoph

Jawaban:

5

Oktaf, 210 byte

function M=F(M,R);f=@(z)[-z/2:-1 !eye(!!mod(z,2)) 1:z/2];t=angle(f([x y]=size(M))'+f(y)*i);B=!!M;B(2:x-1,2:y-1)=0;d=bwdist(B,'ch');[~,I]=sortrows([d(:) t(:)]);for k=0:max(d(:));M(h)=shift(M(h=I(d(I)==k)),R);end

Cobalah di Octave Online!

Versi tidak disatukan:

function M=F(M,R)
    [x y]=size(M);
    f=@(z)[-z/2:-1 !eye(!!mod(z,2)) 1:z/2];
    t=angle(f(x)'+f(y)*i);
    B=!!M;
    B(2:x-1,2:y-1)=0;
    d=bwdist(B,'chessboard');
    [~,I]=sortrows([d(:) t(:)]);
    for k=0:max(d(:))
        M(h)=shift(M(h=I(d(I)==k)),R);
    end
end
R=2;
M=randi(10,4,7)
F(M,R)

Penjelasan:

f=@(z)[-z/2:-1 !eye(!!mod(z,2)) 1:z/2]; 

Sebuah fungsi yang mendapat nomor dan menghasilkan kisaran yang diurutkan dan di tengah untuk input 4 -2 -1 1 2
(datar) menghasilkan untuk input 5 (ganjil) menghasilkan-2.5 -1.5 0 1 2
hanya itu harus dipesan dan di tengah

f(x)'+f(y)*i    

matriks kompleks yang dihasilkan dari rentang

(-2,-2.5) (-2,-1.5) (-2,0) (-2,1) (-2,2)
(-1,-2.5) (-1,-1.5) (-1,0) (-1,1) (-1,2)
(1,-2.5)  (1,-1.5)  (1,0)  (1,1)  (1,2)
(2,-2.5)  (2,-1.5)  (2,0)  (2,1)  (2,2)

t=angle(f(x)'+f(y)*i);                    

Konversi persegi panjang ke koordinat polar dan mengembalikan sudut sehingga untuk setiap sudut cincin diurutkan berlawanan arah jarum jam

-2.25  -2.50  3.14  2.68  2.36
-1.95  -2.16  3.14  2.36  2.03
-1.19  -0.98  0.00  0.79  1.11
-0.90  -0.64  0.00  0.46  0.79


B=!!M;
B(2:x-1,2:y-1)=0;

Matriks berikut dihasilkan

1   1   1   1   1
1   0   0   0   1
1   0   0   0   1
1   1   1   1   1

d=bwdist(B,'chessboard');

Menghitung transformasi jarak B menggunakan jarak papan catur untuk menghasilkan indeks cincin

0   0   0   0   0
0   1   1   1   0
0   1   1   1   0
0   0   0   0   0               

untuk matriks 6 * 7 kita akan memiliki matriks berikut

0   0   0   0   0   0   0
0   1   1   1   1   1   0
0   1   2   2   2   1   0
0   1   2   2   2   1   0
0   1   1   1   1   1   0
0   0   0   0   0   0   0   

[~,I]=sortrows([d(:) t(:)]);

pengurutan leksikografis pertama berdasarkan indeks cincin dan kemudian berdasarkan urutan sudut (indeks elemen yang diurutkan dikembalikan)

    for k=0:max(d(:))
        M(h)=shift(M(h=I(d(I)==k)),R);
    end

dan akhirnya melingkar menggeser setiap cincin.

rahnema1
sumber
4

Python 3, 292 288 byte

_=eval
a=input().split()
b,a=int(a[0]),_("".join(a[1:]))[::-1]
c=len(a)
d=len(a[0])
e=range
f="int((i>=j and i+j<c-1)|2*(i>=c/2and i+d>j+c)|3*(i<c/2and i+j<d))"
l=[-1,1,0,0],[0,0,1,-1]
g=lambda x:[[x[i+l[0][_(f)]][j+l[1][_(f)]]for j in e(d)]for i in e(c)]
print(_("g("*b+"a"+")"*b)[::-1])

Mengambil input dengan baris baru dihapus, tetapi menyisakan ruang setelah jumlah kenaikan untuk memutarnya.

Penjelasan:

Alih-alih memodelkan matriks sebagai serangkaian cincin konsentris sesuai saran OP, seseorang dapat membaginya menjadi empat wilayah di mana elemen bergerak baik naik, turun, kanan, atau kiri selama satu putaran tunggal. Ini adalah tujuan dari string yang telah lama dievaluasi f: untuk menentukan daerah mana dari setiap i,jkombinasi. Kemudian, hasil yang terlihat dua kali masuk l, memberikan elemen yang harus diputar ke posisi i,jpada langkah berikutnya. Fungsinyag yang melakukan semua ini dan membentuk matriks baru setelah satu langkah kemudian dipanggil berulang kali dengan mengelak dari string yang dihasilkan yang berisi representasi dari panggilan fungsi bersarang.

Ketika saya membuat ini awalnya, saya tidak sengaja menyebabkan matriks untuk memutar searah jarum jam, bukan berlawanan arah jarum jam. Daripada melakukan perbaikan yang tepat, saya menambahkan dua salinan yang ditempatkan secara strategis [::-1]untuk membalikkan matriks sebelum dan sesudah rotasi. Ini mungkin bisa golf ke ~ 280 276 byte, tapi aku terlalu malas untuk melakukan itu.

Juga, ini adalah port yang belum teruji cepat dari program Python 2 yang sedikit lebih lama, jadi maafkan saya jika tidak berfungsi dengan benar. Begini kode Python 2:

_=eval
a=raw_input().split()
b,a=int(a[0]),_("".join(a[1:]))[::-1]
c=len(a)
d=len(a[0])
e=xrange
f="int((i>=j and i+j<c-1)|2*(i>=c/2and i+d>j+c)|3*(i<c/2and i+j<d))"
l=[-1,1,0,0],[0,0,1,-1]
g=lambda x:[[x[i+l[0][_(f)]][j+l[1][_(f)]]for j in e(d)]for i in e(c)]
print _("g("*b+"a"+")"*b)[::-1]

EDIT: Golf off 4 byte dengan mengganti ordengan |dua kali. andtidak dapat membantu, sayangnya.

Aidan F. Pierce
sumber
Selamat datang di PPCG! Posting pertama yang bagus!
HyperNeutrino
Sebenarnya cerita lucu - di marching band sekolah menengah saya hari ini kami belajar formasi di mana semua orang bergerak dalam "cincin" konsentris persegi panjang yang mirip dengan pertanyaan ini, dan saya langsung memikirkan jawaban ini.
Aidan F. Pierce
1

Perl, 330 328 byte

sub f{($r,$m)=@_;$h=@m=@$m;for$s(0..(($w=$#{$m[0]})<--$h?$w:$h)/2-.5){@_=(@{$m[$s]}[@x=$s..($x=$w-$s)],(map$m[$_][$x],@y=1+$s..($y=$h-$s)-1),reverse(@{$m[$y]}[@x]),(map$m[$h-$_][$s],@y));push@_,shift
for 1..$r;@{$m[$s]}[@x]=map shift,@x;$m[$_][$x]=shift for@y;@{$m[$y]}[@x]=reverse map shift,@x;$m[$h-$_][$s]=shift for@y}@$m=@m}

Cobalah di Ideone .

Tidak Disatukan:

sub f {
    my ($r, $m) = @_;

    my @m = @$m;
    my $h = $#m;
    my $w = @{$m[0]} - 1;
    my $c = (($w < $h ? $w : $h) + 1) / 2 - 1;

    for my $s (0 .. $c) {
        my $x = $w - $s;
        my $y = $h - $s;
        my @x = $s .. $x;
        my @y = $s + 1 .. $y - 1;

        # One circle.
        @_ = (@{$m[$s]}[@x],
              (map { $m[$_][$x] } @y),
              reverse(@{$m[$y]}[@x]),
              (map { $m[$h - $_][$s] } @y));

        # Circular shift.
        push(@_, shift(@_)) for 1 .. $r;

        @{$m[$s]}[@x] = map { shift(@_) } @x;
        $m[$_][$x] = shift(@_) for @y;
        @{$m[$y]}[@x] = reverse(map { shift(@_) } @x);
        $m[$h - $_][$s] = shift(@_) for @y;
    }

    @$m = @m;
}
Denis Ibaev
sumber