Rotación de una matriz 2D

30

Digamos que tengo la siguiente matriz (2D):

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

Gire la matriz en sentido antihorario R (no en incrementos de 90 grados, solo 1 número cada vez),

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

Ejemplo completado:

Entrada:

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

Salida:

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

(los espacios extraños son para alinear los números en columnas bonitas)

El "anillo" externo de la matriz gira 2 en sentido antihorario, y el derecho interno también gira 2. En esta matriz, solo hay dos anillos.

Un ejemplo con 1 "anillo":

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

Debería dar salida:

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

Su desafío es incorporar una matriz y un número entero Ry generar la versión traducida después de las Rrotaciones.

La rotación de una matriz 4x5 está representada por la siguiente figura: ingrese la descripción de la imagen aquí

Restricciones:

  • 2 ≤ M, N ≤ 100, donde M y N son las dimensiones de la matriz. Se garantiza que el mínimo de M y N será par.
  • 1 ≤ R ≤ 80, donde r es el número de rotaciones.
  • La matriz solo contendrá enteros positivos.
  • Los valores no siempre son distintos.
  • La entrada siempre debe ser como una matriz 2D (si no puede tomar la entrada de tiempo de ejecución como una matriz 2D, entonces solo tiene que encontrar otra forma de obtener la entrada).

Otro caso de prueba, con valores no distintos:

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

Salidas:

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

Este es el , por lo que gana la respuesta más corta.

Aumentar
fuente
Relacionado
Peter Taylor
Relacionado.
Martin Ender
2
Relacionado.
dejó de girar en contra del reloj el
44
@ceasedtoturncounterclockwis Tu nombre es muy irónico para este desafío ...
HyperNeutrino
1
[[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 16], [5, 9, 13, 14]]el 16 se duplica de repente, supongo que debería ser [[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 15], [5, 9, 13, 14]]:?
Christoph

Respuestas:

5

Octava, 210 bytes

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

Pruébalo en Octave Online!

Versión sin golf:

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)

Explicación:

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

Una función que obtiene un número y genera un rango ordenado y centrado para la entrada 4 (par) genera -2 -1 1 2
para la entrada 5 (impar) genera -2.5 -1.5 0 1 2
solo que debe ordenarse y centrarse

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

una matriz compleja generada a partir de rangos

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

Convierta las coordenadas rectangulares a polares y los ángulos de retorno para que los ángulos de cada anillo se ordenen en sentido antihorario

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

La siguiente matriz generada

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

d=bwdist(B,'chessboard');

Calcula la transformación de distancia de B usando la distancia del tablero de ajedrez para generar índices de anillo

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

para una matriz de 6 * 7 tendremos la siguiente matriz

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(:)]);

clasificación lexicográfica primero basada en el índice de anillo y luego por orden de ángulo (índices de elementos ordenados devueltos)

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

y finalmente circular desplazar cada anillo.

rahnema1
fuente
4

Python 3, 292 288 bytes

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

Toma entrada con las nuevas líneas eliminadas, pero dejando un espacio después del número de incrementos para rotarlo.

Explicación:

En lugar de modelar la matriz como una serie de anillos concéntricos según la sugerencia del OP, uno puede dividirla en cuatro regiones donde los elementos viajan hacia arriba, hacia abajo, hacia la derecha o hacia la izquierda durante una sola rotación. Este es el propósito de la cadena de evaluación larga f: determinar en qué región i,jcae cada combinación. Luego, el resultado de eso se busca dos veces l, dando el elemento que debe rotar en posición i,jen el siguiente paso. La función gque hace todo esto y forma la nueva matriz después de un solo paso se llama repetidamente evaluando una cadena generada que contiene la representación de una llamada de función anidada.

Cuando hice esto originalmente, accidentalmente hice que la matriz girara en sentido horario en lugar de hacerlo en sentido antihorario. En lugar de hacer una corrección adecuada, agregué dos copias colocadas estratégicamente [::-1]para invertir la matriz antes y después de la rotación. Probablemente estos podrían tener un golf de ~ 280 276 bytes, pero soy demasiado vago para hacerlo.

Además, este es un puerto rápido no probado de un programa Python 2 un poco más largo, así que perdóname si no funciona del todo bien. Aquí está el código de Python 2, de todos modos:

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

EDITAR: Golfed 4 bytes reemplazando orcon |dos veces. andNo se puede evitar, por desgracia.

Aidan F. Pierce
fuente
Bienvenido a PPCG! Bonito primer post!
HyperNeutrino
Una historia divertida en realidad: hoy, en mi banda de música de la escuela secundaria, aprendimos una formación en la que todos se mueven en "anillos" rectangulares concéntricos similares a esta pregunta, e inmediatamente pensé en esta respuesta.
Aidan F. Pierce
1

Perl, 330 328 bytes

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}

Pruébalo en Ideone .

Sin golf:

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
fuente