Zygzakować matrycę

43

W ramach algorytmu kompresji standard JPEG rozwija matrycę do wektora wzdłuż przeciwbieżnych zmiennych kierunków:

wprowadź opis zdjęcia tutaj

Twoim zadaniem jest pobranie matrycy (niekoniecznie kwadratowej) i zwrócenie jej w rozwiniętej formie. Jako przykład:

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

powinien ustąpić

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

Zasady

Możesz założyć, że elementy macierzy są dodatnimi liczbami całkowitymi mniejszymi niż 10.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Matryca wejściowa może być podana w dowolnej wygodnej, jednoznacznej, zagnieżdżonej liście lub formacie łańcuchowym, lub jako płaska lista wraz z oboma wymiarami macierzy. (Lub, oczywiście, jako typ matrycy, jeśli Twój język je ma.)

Wektor wyjściowy może mieć dowolny dogodny, jednoznaczny, płaski format lub ciąg znaków.

Obowiązują standardowe zasady .

Przypadki testowe

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

Powiązane wyzwania

Martin Ender
źródło
1
Czy dane wejściowe mogą być rzeczywistą macierzą w J? Czy też należałoby go przekształcić z list zagnieżdżonych w macierz jako część funkcji?
Gareth,
4
Jeśli weźmiemy matrycę jako tablicę 2D, czy nadal możemy przyjmować wymiary jako dane wejściowe?
xnor
1
@Gareth tak, możesz wziąć typ macierzy jako dane wejściowe.
Martin Ender
1
@xnor Hmmm, to trochę trudniejsze. Wydaje mi się, że wzięcie takiej ilości zbędnych informacji trochę przyczynia się do wstępnego przetwarzania danych wejściowych.
Martin Ender
Czy płaska lista może być uporządkowana według kolumny, jeśli jest to natywna kolejność języka?
Luis Mendo,

Odpowiedzi:

27

J, 31 30 14 12 11 bajtów

[:;<@|.`</.

Ych . Za duży.

Pobiera macierz jako dane wejściowe.

Wyjaśnienie

J ma tutaj przewagę. Istnieje polecenie o nazwie oblique ( /.), które pobiera kolejno linie ukośne i stosuje do nich czasownik. W tym przypadku używam gerunda do stosowania naprzemiennie dwóch czasowników: <( pole ) i <@|.( odwrotność i pole). To jest po prostu kwestia rozpakowania wszystkiego przy użyciu ;( Raze ).

Gareth
źródło
26
J to jedyny język, który sprawia, że ​​czuję, że potrzebuję zaawansowanego dyplomu z języka angielskiego, aby go zrozumieć.
Alex A.,
2
@AlexA. btw, słowo „polecenie” powinno być „przysłówkiem”.
Adám
11

Pyth, 24 23 21 20 19 18 17 bajtów

ssm_W=!Td.T+LaYkQ

Alternatywna 17-bajtowa wersja: 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)

Dzięki @FryAmTheEggman za bajt, @Jakube za 2 bajty i @isaacg za bajt!

Wyjaśnienie „czarnej magii”, o której mowa powyżej: m_W=!Tdzasadniczo odwraca każdą inną podtablicę. Odbywa się to poprzez mapowanie _W=!Tkażdej podtablicy; Wjest aplikacją warunkową, więc _s (odwraca) wszystkie podpowierzchnie, w których =!Tjest to prawda. Tjest zmienną wstępnie zainicjalizowaną na dziesięć (prawdę) i =!Toznacza (T = !T). Przełącza więc wartość zmiennej, która zaczyna prawdę i zwraca nową wartość, co oznacza, że ​​będzie naprzemiennie powracać do fałszu, prawdy, fałszu, prawdy ... (podziękowania dla Jakube za ten pomysł)

Zestaw testowy tutaj .

Klamka
źródło
11

Galaretka, 24 19 15 13 11 bajtów

pS€żị"¥pỤị⁵

Pobiera liczbę wierszy, liczbę kolumn i płaską listę jako osobne argumenty wiersza polecenia.

Wypróbuj online!

Jak to działa

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
źródło
Tsk. Nie jestem pewien, czy mogę teraz skrócić mój. : -S
Gareth
Nie oznacza to jednak, że nie spróbuję ...
Gareth
Dlaczego Jelly nie odziedziczył jeszcze Oblique? Czy mogę zasugerować glify APL i ? A może skandynawski øi ǿ?
Adám
7

MATL , 28 27 bajtów

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

Na podstawie mojej odpowiedzi tutaj . Ogólna idea polega na utworzeniu tablicy 2D o tym samym rozmiarze co dane wejściowe, wypełnionej wartościami, które rosną w tej samej kolejności co zygzakowata ścieżka. Następnie linearyzowana (spłaszczona) wersja tej tablicy jest sortowana, a wskaźniki tego sortowania są zachowywane. Są to wskaźniki, które należy zastosować do danych wejściowych, aby uzyskać ścieżkę zygzakowatą.

Dane wejściowe są w formie

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

Wyjaśnienie

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

Matlab, 134 bajty

Po prostu starałem się skrócić mój kod w Matlabie, jak telegrafowanie.

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)';

Uwagi:

  1. Mjest m×nmatrycą.
  2. ai bobie macierze są tego samego rozmiaru M, każdy wiersz askłada się z liczb równych jego numerowi wiersza, podczas gdy każda kolumna bjest równa jego numerowi kolumny. Zatem a+ bjest macierzą, której element jest równy sumie jego numeru wiersza i kolumny, tj matrix(p,q)=p+q.
  3. Tak więc A(p,q)=p+q-1; a B(p,q)=p-q.
  4. Cjest wyrażone matematycznie jako równanie poniżej. Zygzakowato rosnąca matryca za pomocą równania można wykonać zygzakowato rosnącą matrycę, jak pokazano poniżej.
C =
     1     2     6     7
     3     5     8    14
     4     9    13    18
    10    12    19    25
  1. Cwskazuje kolejność elementów M w zygzakowatych wynikach. Następnie [~,I]=sort(C(:));zwraca kolejność, czyli Iw ten sposób, V=V(I)'to wynik.
Guoyang Qin
źródło
Tak, właśnie go znalazłem, teraz go aktualizuję.
Guoyang Qin,
@AlexA. Dziękuję Alex. Bo jestem w tym nowy i chcę go skrócić tak krótko, jak to możliwe, ale uczyńcie go snippetem. Teraz poprawiłem swój kod.
Guoyang Qin,
Wygląda dobrze. Miły pierwszy post! :)
Alex A.,
3

JavaScript (SpiderMonkey 30+), 99 bajtów

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]

Testowane w przeglądarce Firefox 44. Pobiera dane wejściowe jako tablicę 2D.

ETHprodukcje
źródło
3

Python 2, 84 bajtów

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]

Przeniesienie odpowiedzi na nich . Przyjmuje płaski układ o określonej szerokości i wysokości. xsot zapisał bajt.


88 bajtów:

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

Przyjmuje płaski układ o określonej szerokości i wysokości. Sortuje odpowiadające współrzędne 2D (i/w,i%w)w kolejności zygzakowatej, zwiększając sumę, aby uzyskać przekątne, przerwane przez zwiększenie lub zmniejszenie wartości wiersza, na podstawie tego, czy wiersz plus kolumna jest nieparzysty, czy parzysty.

xnor
źródło
Że jeśli warunek można dalej skrócić.
xsot
@xsot Nice catch.
xnor
3

Haskell, 79 78 73 bajtów

(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

Dane wejściowe to płaska lista z liczbą wierszy i kolumn, np. ( [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].

Jak to działa: przejdź przez współrzędne xiy matrycy ( hwiersze, wkolumny) w dwóch zagnieżdżonych pętlach:

  | 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

tj. od góry / prawo do dołu / lewo, pomijanie powiązanych indeksów ( yi xmusi spełniać y<hi x-y<w). Kiedy xjest parzysty, kolejność pętli wewnętrznej jest odwrócona: yprzechodzi z xna 0. Robię to, wybierając funkcję modyfikującą dla zakresu y, [0..x]który jest tym xelementem [reverse,id,reverse,id,...].

Edycja: @xnor zmienił układ pętli i zapisał 5 bajtów. Dzięki!

nimi
źródło
Myślę, że możesz g=id:reverse:g.
xnor
Parens na multication (y-x)*wmogą być cięte przez transpozycję problem: (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. Tłumaczenie na Python pozwala zaoszczędzić 3 znaki w porównaniu do tego, co miałem.
xnor
1

Python 2 + NumPy, 122 bajty

Przyznaję. Pracowałem naprzód. Niestety tej samej metody nie można łatwo zmodyfikować, aby rozwiązać pozostałe 2 powiązane wyzwania ...

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

Pobiera na wejściu tablicę numpy. Wyświetla listę.

Wypróbuj online

Wyjaśnienie:

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

Lambda ma tę samą długość:

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

Python 3, 131 118 115 107 bajtów

Opierając się na tej samej Książęcej jako moją odpowiedź na wyzwanie Deusovi za

Zakładam, że nie możemy mieć zera w macierzy wejściowej

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]

Wyjaśnienie

jak to działa :

            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

Wyniki

>>> [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
źródło
Powinien reverse even linebyć reverse odd lineszamiast tego?
nwp
Indeks @nwp zaczyna się od 0 ^^
Erwan
Ach, mówisz o numerach linii, a nie o długości linii. Przepraszam, pomyliłem je.
nwp
@nwp np, btw Zmieniłem to, aby uniknąć zamieszania
Erwan