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

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 gry w golfa .

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

• Zrekonstruuj zygzakowatą matrycę (nieco trudniejszą odwrotną transformację)
• Obróć anty-przekątne

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

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 .

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.

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

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. 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

5. 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.

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.

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.

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!

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

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