Zigzagify a Matrix

43

Sebagai bagian dari algoritma kompresinya, standar JPEG membuka gulungan sebuah matriks ke dalam vektor di sepanjang antidiagonals dari arah yang bergantian:

masukkan deskripsi gambar di sini

Tugas Anda adalah mengambil matriks (belum tentu kuadrat) dan mengembalikannya dalam bentuk yang tidak terbuka. Sebagai contoh:

[1 2 3 4
 5 6 7 8
 9 1 2 3]

harus menghasilkan

[1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]

Aturan

Anda dapat mengasumsikan bahwa elemen matriks bilangan bulat positif kurang dari 10.

Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).

Matriks input dapat diberikan dalam format string atau string yang nyaman, tidak ambigu, bersarang, atau sebagai daftar datar bersama dengan kedua dimensi matriks. (Atau, tentu saja, sebagai jenis matriks jika bahasa Anda memilikinya.)

Vektor output mungkin dalam format string atau daftar yang mudah, tidak ambigu, datar.

Aturan standar berlaku.

Uji Kasus

[[1]]                                               => [1]
[[1 2] [3 1]]                                       => [1 2 3 1]
[[1 2 3 1]]                                         => [1 2 3 1]
[[1 2 3] [5 6 4] [9 7 8] [1 2 3]]                   => [1 2 5 9 6 3 4 7 1 2 8 3]
[[1 2 3 4] [5 6 7 8] [9 1 2 3]]                     => [1 2 5 9 6 3 4 7 1 2 8 3]
[[1 2 6 3 1 2] [5 9 4 7 8 3]]                       => [1 2 5 9 6 3 4 7 1 2 8 3]
[[1 2 5 9 6 3 4 7 1 2 8 3]]                         => [1 2 5 9 6 3 4 7 1 2 8 3]
[[1] [2] [5] [9] [6] [3] [4] [7] [1] [2] [8] [3]]   => [1 2 5 9 6 3 4 7 1 2 8 3]

Tantangan Terkait

Martin Ender
sumber
1
Bisakah input menjadi matriks aktual dalam J? Atau apakah perlu diubah dari daftar bersarang menjadi matriks sebagai bagian dari fungsi?
Gareth
4
Jika kita mengambil matriks sebagai array 2D, apakah kita masih dapat mengambil dimensi sebagai input?
xnor
1
@ Gareth ya Anda dapat mengambil jenis matriks sebagai input.
Martin Ender
1
@xnor Hmmm, yang ini agak rumit. Saya merasa seperti mengambil jumlah informasi yang redundan itu untuk memproses input.
Martin Ender
Bisakah daftar datar dalam urutan kolom-utama jika itu urutan asli bahasa?
Luis Mendo

Jawaban:

27

J, 31 30 14 12 11 byte

[:;<@|.`</.

Ych . Terlalu besar.

Mengambil matriks sebagai input.

Penjelasan

J memiliki keunggulan di sini. Ada perintah yang disebut oblique ( /.) yang mengambil garis miring pada gilirannya dan menerapkan kata kerja kepada mereka. Dalam hal ini saya menggunakan gerund untuk menerapkan dua kata kerja secara bergantian: <( kotak ) dan <@|.( terbalik dan kotak). Maka itu hanya masalah unboxing menggunakan segalanya ;( meruntuhkan ).

Gareth
sumber
26
J adalah satu-satunya bahasa yang membuat saya merasa saya perlu gelar lanjutan dalam bahasa Inggris untuk memahaminya.
Alex A.
2
@AlexA. btw, kata "perintah" seharusnya "kata keterangan".
Adám
11

Pyth, 24 23 21 20 19 18 17 byte

ssm_W=!Td.T+LaYkQ

Versi 17 byte alternatif: ssuL_G=!T.T+LaYkQ

                Q  input
           +L      prepend to each subarray...
             aYk   (Y += ''). Y is initialized to [], so this prepends [''] to
                     the first subarray, ['', ''] to the second, etc.
                   ['' 1  2  3  4
                    '' '' 5  6  7  8
                    '' '' '' 9  1  2  3]
         .T        transpose, giving us
                   ['' '' ''
                    1  '' ''
                    2  5  ''
                    3  6  9
                    4  7  1
                    8  2
                    3]
  m_W=!Td          black magic
 s                 join subarrays together
s                  join *everything* on empty string (which means ''s used for
                     padding disappear)

Terima kasih kepada @FryAmTheEggman untuk satu byte, @Jakube untuk 2 byte, dan @isaacg untuk satu byte!

Penjelasan "ilmu hitam" disinggung di atas: m_W=!Tdpada dasarnya membalikkan setiap subarray lainnya. Ini dilakukan dengan memetakan _W=!Tsetiap subarray; Wadalah aplikasi bersyarat, jadi itu _(membalikkan) semua subarrays mana =!Tyang benar. Tadalah variabel yang diinisialisasi ke sepuluh (kebenaran), dan =!Tberarti (T = !T). Jadi itu mengubah nilai variabel yang dimulai dengan kebenaran dan mengembalikan nilai baru, yang berarti bahwa itu akan bergantian antara mengembalikan kepalsuan, kebenaran, kepalsuan, kebenaran ... (kredit ke Jakube untuk ide ini)

Test suite di sini .

Gagang pintu
sumber
11

Jelly, 24 19 15 13 11 byte

pS€żị"¥pỤị⁵

Mengambil jumlah baris, jumlah kolom dan daftar datar sebagai argumen baris perintah yang terpisah.

Cobalah online!

Bagaimana itu bekerja

pS€żị"¥pỤị⁵  Main link. Argument: m (rows), n (columns), A (list, flat)

p            Compute the Cartesian product [1, ..., m] × [1, ..., n]. This yields
             the indices of the matrix M, i.e., [[1, 1], [1, 2], ..., [m, n]].
 S€          Compute the sums of all index pairs.
       p     Yield the Cartesian product.
      ¥      Dyadic chain. Arguments: Sums, Cartesian product.
    ị"       For each index pair in the Cartesian product, retrieve the coordinate
             at the index of its sum, i.e., map [i, j] to i if i + j is odd and to
             j if i + j is even.
   ż         Zip the sums with the retrieved indices.
       Ụ     Sort [1, ..., mn] by the corresponding item in the resulting list.
        ị⁵   Retrieve the corresponding items from A.
Dennis
sumber
Cih. Saya tidak yakin apakah saya bisa membuat milik saya lebih pendek sekarang. : -S
Gareth
Itu bukan untuk mengatakan saya tidak akan mencoba ...
Gareth
Mengapa Jelly belum mewarisi Oblique? Bolehkah saya menyarankan mesin terbang APL dan ? Atau mungkin Skandinavia ødan ǿ?
Adám
7

MATL , 28 27 byte

tZyZ}:w:!+-1y^7MGn/*-X:K#S)

Diadaptasi dari jawaban saya di sini . Gagasan umum adalah membuat array 2D dengan ukuran yang sama dengan input, diisi dengan nilai yang meningkat dalam urutan yang sama dengan jalur zig-zag. Kemudian versi linierisasi (diratakan) dari array itu diurutkan, dan indeksnya dari pengurutan itu disimpan. Itu adalah indeks yang perlu diterapkan pada input untuk menghasilkan jalur zig-zag.

Input ada dalam formulir

[1 2 3; 5 6 4; 9 7 8; 1 2 3]

Penjelasan

Cobalah online!

t       % input 2D array. Duplicate
ZyZ}    % get size as length-2 vector. Split into two numbers: r, c
:       % range [1,2,...,c] as a row vector
w:!     % swap, range [1;2;...;r] as a column vector
+       % add with broadcast. Gives a 2D array
-1      % push -1
y^      % duplicate previous 2D array. Compute -1 raised to that
7M      % push [1;2;...;r] again
Gn/     % divide by input matrix size, that is, r*c
*       % multiply
-       % subtract
X:      % linearize 2D array into column array
K#S     % sort and push the indices of the sorting. Gives a column vector
)       % index input matrix with that column vector
Luis Mendo
sumber
4

Matlab, 134 byte

Saya baru saja mencoba yang terbaik untuk mempersingkat kode saya di Matlab, seperti telegraphing.

function V=z(M)
[m,n]=size(M);
a=(1:m)'*ones(1,n);
b=ones(m,1)*(1:n);
A=a+b-1;
B=a-b;
C=(A.^2+(-1).^A.*B+1);
[~,I]=sort(C(:));
V=M(:);
V=V(I)';

Catatan:

  1. Madalah sebuah m×nmatriks.
  2. adan bkeduanya matriks ukuran yang sama M, masing-masing baris aterdiri dari angka yang sama dengan nomor barisnya, sedangkan setiap kolom bsama dengan nomor kolomnya. Dengan demikian, a+ badalah matriks yang elemennya sama dengan jumlah baris dan jumlah kolomnya, yaitu matrix(p,q)=p+q,.
  3. Demikian A(p,q)=p+q-1,; dan B(p,q)=p-q.
  4. Csecara matematis dinyatakan sebagai persamaan di bawah ini. Secara Zigz meningkat matriks dengan persamaan, matriks zigzagifiedly meningkat dapat dibuat seperti yang ditunjukkan di bawah ini.
C =
     1     2     6     7
     3     5     8    14
     4     9    13    18
    10    12    19    25
  1. Cmenunjukkan urutan elemen M dalam hasil zig-zag. Kemudian, [~,I]=sort(C(:));mengembalikan urutan, yaitu I, dengan demikian, V=V(I)'adalah hasilnya.
Guoyang Qin
sumber
Ya, saya baru saja menemukannya, sekarang saya memperbaruinya.
Guoyang Qin
@AlexA. Terima kasih, Alex. Karena saya baru dalam hal ini dan saya ingin mempersingkatnya sesingkat mungkin tetapi menjadikannya cuplikan. Sekarang saya telah memperbaiki kode saya.
Guoyang Qin
Kelihatan bagus. Posting pertama yang bagus! :)
Alex A.
3

JavaScript (SpiderMonkey 30+), 99 byte

x=>[for(y of[...x,...x[0]].keys())for(z of Array(y+1).keys())if(a=x[y%2?z:y-z])if(b=a[y%2?y-z:z])b]

Diuji dalam Firefox 44. Mengambil input sebagai array 2D.

Produksi ETH
sumber
3

Python 2, 84 byte

lambda N,w,h:[N[i*w+s-i]for s in range(w+h+1)for i in range(h)[::s%2*2-1]if-1<s-i<w]

Porting jawaban nimi . Mengambil array datar dengan lebar dan tinggi yang diberikan. xsot menyimpan byte.


88 byte:

lambda M,w,h:[M[i]for i in sorted(range(w*h),key=lambda i:(i/w+i%w,-i*(-1)**(i/w+i%w)))]

Mengambil array datar dengan lebar dan tinggi yang diberikan. Urutkan koordinat 2D yang sesuai (i/w,i%w)dalam urutan zigzag untuk meningkatkan jumlah untuk mendapatkan diagonal, yang ditambahkan dengan menambah atau mengurangi nilai baris, berdasarkan apakah kolom plus baris itu ganjil atau genap.

Tidak
sumber
Itu kalau kondisinya bisa diperpendek.
xsot
@ xsot Tangkapan bagus.
xnor
3

Haskell, 79 78 73 byte

(m#h)w=[m!!(y*w+x-y)|x<-[0..h+w],y<-g!!x$[0..x],y<h,x-y<w]
g=reverse:id:g

Input adalah daftar datar dengan jumlah baris dan kolom, misalnya ( [1,2,6,3,1,2,5,9,4,7,8,3] # 2) 6->[1,2,5,9,6,3,4,7,1,2,8,3] .

Cara kerjanya: berjalan melalui koordinat x dan y dari matriks ( hbaris, wkolom) dalam dua loop bersarang:

  | 0 1 2 3 4 5 6 7 8    outer loop               Index is y*w+x-y, i.e.
--+------------------    x from 0 to h+w          the elements are accessed
0 | 1 2 6 3 1 2                                   in the following order:
1 | 5 9 4 7 8 3
2 |                                               1 2 4 6  8 10 
3 |                                               3 5 7 9 11 12
4 |
5 |
6 |
7 | inner loop:
8 | y from 0 to x

yaitu dari atas / kanan ke bawah / kiri, melompati indeks terikat ( ydan xharus memenuhi y<hdan x-y<w). Kapan xgenap, urutan loop dalam terbalik: yberalih dari xke 0. Saya melakukan ini dengan memilih fungsi modifikasi untuk y-range [0..x]yang merupakan xelemen ke-10 [reverse,id,reverse,id,...].

Sunting: @xnatau atur ulang loop dan simpan 5 byte. Terima kasih!

nimi
sumber
Saya pikir Anda bisa melakukannya g=id:reverse:g.
xnor
Parens di multication yang (y-x)*wdapat dipotong oleh transposing masalah: (m#h)w=[m!!(x*w+y-x)|y<-[0..h+w],x<-g!!y$[0..y],x<h,y-x<w] g=reverse:id:g. Menerjemahkan ke dalam Python menghemat 3 karakter atas apa yang saya miliki.
xnor
1

Python 2 + NumPy, 122 byte

Aku mengakuinya. Saya bekerja di depan. Sayangnya, metode yang sama ini tidak dapat dengan mudah dimodifikasi untuk menyelesaikan 2 tantangan terkait lainnya ...

import numpy
def f(m):w=len(m);print sum([list(m[::-1,:].diagonal(i)[::(i+w+1)%2*-2+1])for i in range(-w,w+len(m[0]))],[])

Mengambil array numpy sebagai input. Menghasilkan daftar.

Cobalah online

Penjelasan:

def f(m):
    w=len(m)    # the height of the matrix, (at one point I thought it was the width)
    # get the anti-diagonals of the matrix. Reverse them if odd by mapping odd to -1
    d=[list(m[::-1,:].diagonal(i)[::(i+w+1)%2*-2+1])for i in range(-w,w+len(m[0]))]
            # w+len(m[0]) accounts for the width of the matrix. Works if it's too large.
    print sum(d,[]) # join the lists

Sebuah lambda memiliki panjang yang sama:

import numpy
lambda m:sum([list(m[::-1,:].diagonal(i)[::(i+len(m)+1)%2*-2+1])for i in range(-len(m),len(m)+len(m[0]))],[])
mbomb007
sumber
1

Python 3, 131 118 115 107 byte

Berdasarkan principe yang sama seperti saya jawaban dari tantangan Deusovi ini

Saya berasumsi kita tidak dapat memiliki nol di matrik input

e=enumerate
lambda s:[k for j,i in e(zip(*[([0]*n+i+[0]*len(s))for n,i in e(s)]))for k in i[::j%2*2-1]if k]

Penjelasan

bagaimana itu bekerja :

            pad with 0      transpose    remove 0    reverse line           concatenate 
                                                     with even index
1 2 3       1 2 3 0 0        1 0 0        1            1                
4 5 6   --> 0 4 5 6 0    --> 2 4 0    --> 2 4     -->  2 4              -->  1 2 4 7 5 3 6 8 9
7 8 9       0 0 7 8 9        3 5 7        3 5 7        7 5 3             
                             0 6 8        6 8          6 8               
                             0 0 9        9            9

Hasil

>>> [print([i,f(i)]) for i in [[[1]], [[1, 2], [3, 1]], [[1, 2, 3, 1]], [[1, 2, 3], [5, 6, 4], [9, 7, 8], [1, 2, 3]], [[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]], [[1, 2, 6, 3, 1, 2], [5, 9, 4, 7, 8, 3]], [[1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]], [[1], [2], [5], [9], [6], [3], [4], [7], [1], [2], [8], [3]]]]
# [input,                                                          output]
[[[1]],                                                            [1]]
[[[1, 2], [3, 1]],                                                 [1, 2, 3, 1]]
[[[1, 2, 3, 1]],                                                   [1, 2, 3, 1]]
[[[1, 2, 3], [5, 6, 4], [9, 7, 8], [1, 2, 3]],                     [1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]]
[[[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]],                       [1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]]
[[[1, 2, 6, 3, 1, 2], [5, 9, 4, 7, 8, 3]],                         [1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]]
[[[1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]],                           [1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]]
[[[1], [2], [5], [9], [6], [3], [4], [7], [1], [2], [8], [3]],     [1, 2, 5, 9, 6, 3, 4, 7, 1, 2, 8, 3]]
Erwan
sumber
Harus reverse even linemenjadi reverse odd linessebaliknya?
nwp
Indeks @nwp mulai dari 0 ^^
Erwan
Ah, Anda berbicara tentang nomor baris, bukan panjang baris. Saya bingung itu, maaf.
nwp
@ nwp np, btw saya mengubahnya untuk menghindari kebingungan
Erwan