Zigzagificar una matriz

43

Como parte de su algoritmo de compresión, el estándar JPEG desenrolla una matriz en un vector a lo largo de antidiagonales de dirección alterna:

ingrese la descripción de la imagen aquí

Su tarea es tomar una matriz (no necesariamente cuadrada) y devolverla en forma desenrollada. Como ejemplo:

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

debería rendir

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

Reglas

Puede suponer que los elementos de la matriz son enteros positivos menores que 10.

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

La matriz de entrada se puede proporcionar en cualquier lista conveniente o inequívoca, anidada o en formato de cadena, o como una lista plana junto con ambas dimensiones de la matriz. (O, por supuesto, como un tipo de matriz si su idioma los tiene).

El vector de salida puede estar en cualquier formato de cadena o lista conveniente, inequívoca y plana.

Se aplican reglas estándar de .

Casos de prueba

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

Desafíos relacionados

Martin Ender
fuente
1
¿Puede la entrada ser una matriz real en J? ¿O tendría que pasar de listas anidadas a una matriz como parte de la función?
Gareth
44
Si tomamos la matriz como una matriz 2D, ¿podemos tomar las dimensiones como entradas?
xnor
1
@Gareth sí, puede tomar un tipo de matriz como entrada.
Martin Ender
1
@xnor Hmmm, eso es un poco más complicado. Siento que tomar esa cantidad de información redundante va un poco al preprocesamiento de la entrada.
Martin Ender
¿Puede la lista plana estar en orden de columna principal si ese es el orden nativo del idioma?
Luis Mendo

Respuestas:

27

J, 31 30 14 12 11 bytes

[:;<@|.`</.

Ych . Demasiado grande.

Toma una matriz como entrada.

Explicación

J tiene una ventaja aquí. Hay un comando llamado oblicuo ( /.) que toma las líneas oblicuas a su vez y les aplica un verbo. En este caso, estoy usando un gerundio para aplicar dos verbos alternativamente: <( recuadro ) y <@|.( reverso y recuadro). Entonces es solo cuestión de desempaquetar todo usando ;( raze ).

Gareth
fuente
26
J es el único idioma que me hace sentir que necesito un título avanzado en inglés para entenderlo.
Alex A.
2
@AlexA. por cierto, la palabra "comando" debería haber sido "adverbio".
Adám
11

Pyth, 24 23 21 20 19 18 17 bytes

ssm_W=!Td.T+LaYkQ

Versión alternativa de 17 bytes: 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)

¡Gracias a @FryAmTheEggman por un byte, @Jakube por 2 bytes y @isaacg por un byte!

Explicación de la "magia negra" aludida anteriormente: m_W=!Tdesencialmente invierte cualquier otro subconjunto. Lo hace mediante el mapeo _W=!Tsobre cada submatriz; Wes una aplicación condicional, por lo que _s (invierte) todas las submatrices donde =!Tes verdadero. Tes una variable preinicializada a diez (verdad), y =!Tsignifica (T = !T). Por lo tanto, alterna el valor de una variable que comienza con la verdad y devuelve el nuevo valor, lo que significa que alternará entre devolver falso, verdadero, falso, verdadero ... (crédito a Jakube por esta idea)

Prueba de suite aquí .

Pomo de la puerta
fuente
11

Jalea, 24 19 15 13 11 bytes

pS€żị"¥pỤị⁵

Toma el número de filas, el número de columnas y una lista plana como argumentos separados de la línea de comandos.

Pruébalo en línea!

Cómo funciona

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
fuente
Tsk. No estoy seguro si puedo acortar el mío ahora. : -S
Gareth
Sin embargo, eso no quiere decir que no lo intentaré ...
Gareth
¿Por qué Jelly aún no ha heredado Oblique? ¿Puedo sugerir los glifos APL y ? O tal vez escandinavo øy ǿ?
Adám
7

MATL , 28 27 bytes

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

Adaptado de mi respuesta aquí . La idea general es crear una matriz 2D del mismo tamaño que la entrada, llena de valores que aumentan en el mismo orden que la ruta en zig-zag. Luego, se ordena la versión linealizada (aplanada) de esa matriz y se mantienen los índices de esa clasificación. Esos son los índices que deben aplicarse a la entrada para producir la ruta en zig-zag.

La entrada está en la forma

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

Explicación

Pruébalo en línea!

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
fuente
4

Matlab, 134 bytes

Solo hice mi mejor esfuerzo para acortar mi código en Matlab, como telegrafiarlo.

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

Notas:

  1. MEs una m×nmatriz.
  2. ay bson ambas matrices del mismo tamaño M, cada fila de aconsta de números iguales a su número de fila, mientras que cada columna de bes igual a su número de columna. Por lo tanto, a+ bes una matriz cuyo elemento es igual a la suma de su fila y columna de número, es decir, matrix(p,q)=p+q.
  3. Por lo tanto, A(p,q)=p+q-1; y B(p,q)=p-q.
  4. Cse establece matemáticamente como la ecuación a continuación. Matriz creciente en zigzag con la ecuación, se puede hacer una matriz que aumenta en zigzag como se muestra a continuación.
C =
     1     2     6     7
     3     5     8    14
     4     9    13    18
    10    12    19    25
  1. Cindica el orden de los elementos de M en resultados zigzagificados. Luego, [~,I]=sort(C(:));devuelve el orden, es decir I, V=V(I)'es el resultado.
Guoyang Qin
fuente
Sí, lo acabo de encontrar, ahora lo actualizo.
Guoyang Qin
@AlexA. Gracias Alex. Soy nuevo en esto y quiero acortarlo lo más corto posible, pero convertirlo en un fragmento. Ahora ya he arreglado mi código.
Guoyang Qin
Se ve bien. Bonito primer post! :)
Alex A.
3

JavaScript (SpiderMonkey 30+), 99 bytes

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]

Probado en Firefox 44. Toma datos como una matriz 2D.

ETHproducciones
fuente
3

Python 2, 84 bytes

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]

Portando la respuesta de nimi . Toma una matriz plana con ancho y alto dados. xsot guardó un byte.


88 bytes:

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

Toma una matriz plana con ancho y alto dados. Ordena las coordenadas 2D correspondientes (i/w,i%w)en orden de zigzag de suma creciente para obtener diagonales, separadas por el aumento o la disminución del valor de la fila, en función de si la fila más la columna es impar o par.

xnor
fuente
Eso si la condición puede acortarse aún más.
xsot
@xsot Buena captura.
xnor
3

Haskell, 79 78 73 bytes

(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

La entrada es una lista plana con el número de filas y columnas, por ejemplo, ( [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].

Cómo funciona: recorra las coordenadas xey de la matriz ( hfilas, wcolumnas) en dos bucles anidados:

  | 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

es decir, de arriba / derecha a abajo / izquierda, omitiendo los índices encuadernados ( yy xdebe satisfacer y<hy x-y<w). Cuando xes par, el orden del bucle interno se invierte: yva de xa 0. Hago esto eligiendo una función de modificación para el rango y [0..x]que es el xelemento th de [reverse,id,reverse,id,...].

Editar: @xnor reorganizó los bucles y guardó 5 bytes. ¡Gracias!

nimi
fuente
Creo que puedes hacer g=id:reverse:g.
xnor
Los parens en la multication (y-x)*wse pueden cortar mediante la transposición del problema: (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. La traducción a Python ahorra 3 caracteres sobre lo que tenía.
xnor
1

Python 2 + NumPy, 122 bytes

Lo admito. Trabajé por delante. Desafortunadamente, este mismo método no puede modificarse fácilmente para resolver los otros 2 desafíos relacionados ...

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

Toma una matriz numpy como entrada. Emite una lista.

Pruébalo en línea

Explicación:

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

Una lambda tiene la misma longitud:

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
fuente
1

Python 3, 131 118 115 107 bytes

Basado en el mismo principio que mi respuesta al desafío de Deusovi

Supongo que no podemos tener cero en la matriz de entrada

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]

Explicación

cómo funciona :

            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

Resultados

>>> [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
fuente
Debería reverse even lineser reverse odd linesen su lugar?
nwp
El índice @nwp comienza en 0 ^^
Erwan
Ah, estás hablando de los números de línea, no de la longitud de la línea. Los confundí, lo siento.
nwp
@nwp np, por cierto lo cambié para evitar confusiones
Erwan