31
\$\begingroup\$

Let's say I have the following (2D) matrix:

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

Rotate the matrix counterclockwise R times (not in 90 degree increments, just by 1 number each time),

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

Completed example:

Input:

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

Output:

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

(weird spaces are to align the numbers in nice columns)

The outer "ring" of the matrix rotates 2 counterclockwise, and the inner right rotates 2 also. In this matrix, there are only two rings.

An example with 1 "ring":

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

Should output:

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

Your challenge is to take in a matrix and an integer R, and output the translated version after R rotations.

Rotation of a 4x5 matrix is represented by the following figure: enter image description here

Constraints:

  • 2 ≤ M, N ≤ 100, where M and N are the dimensions of the matrix. It is guaranteed that the minimum of M and N will be even.
  • 1 ≤ R ≤ 80, where r is number of rotations.
  • The matrix will only ever contain positive integers.
  • Values are not always distinct.
  • The input should always be as a 2D array (if you can't take runtime input as a 2D array, then you just have to find another way to get input).

Another test case, with non-distinct values:

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

Outputs:

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

This is , so the shortest answer wins!

\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Mar 3 '17 at 19:36
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender Mar 3 '17 at 20:17
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ – ceased to turn counterclockwis Mar 4 '17 at 15:18
  • 4
    \$\begingroup\$ @ceasedtoturncounterclockwis Your name is very ironic for this challenge... \$\endgroup\$ – HyperNeutrino Mar 5 '17 at 2:48
  • 1
    \$\begingroup\$ [[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 16], [5, 9, 13, 14]] the 16 is suddenly duplicated I guess it should be: [[3, 4, 8, 12], [2, 11, 10, 16], [1, 7, 6, 15], [5, 9, 13, 14]]? \$\endgroup\$ – Christoph Mar 10 '17 at 14:56
4
\$\begingroup\$

Jelly, 39 38 36 35 bytes

ḢṚ;Ḣ€;Ṫ;Ṫ€Ṛ$,-ṙ\;"ß¹¡
FJ©ṁ¹Çy®ịFṁµ¡

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Octave, 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

Try it on Octave Online!

Ungolfed version:

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)

Explanation:

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

A function that gets a number and generates a range that is ordered and centered for input 4 (even) generates -2 -1 1 2
for input 5(odd) generates -2.5 -1.5 0 1 2
only it should be ordered and centered

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

a complex matrix generated from ranges

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

Convert rectangular to polar coordinates and return angles so for each ring angles are sorted counteclockwise

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

The following matrix generated

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

d=bwdist(B,'chessboard');

Computes the distance transform of B using chessboard distance to generate ring indices

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

for a 6 * 7 matrix we will have the following matrix

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

lexicographic sort first based on ring index and then by order of angle(indices of sorted elements returned)

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

and finally circular shift each ring.

\$\endgroup\$
4
\$\begingroup\$

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

Takes input with newlines removed, but leaving a space after the number of increments to rotate it by.

Explanation:

Instead of modeling the matrix as a series of concentric rings per the OP's suggestion, one can instead divide it into four regions where the elements travel either up, down, right, or left during a single rotation. This is the purpose of the long eval-ed string f: to determine which region each i,j combination falls into. Then, the result of that is looked up twice in l, giving the element that must rotate into position i,j in the next step. The function g that does all of this and forms the new matrix after a single step is then called repeatedly by evaling a generated string containing the representation of a nested function call.

When I made this originally, I accidentally caused the matrix to rotate clockwise instead of counterclockwise. Rather than doing a proper fix, I added two strategically placed copies of [::-1] to reverse the matrix before and after the rotation. These could probably be golfed off to ~280 276 bytes, but I'm too lazy to do that.

Also, this is a quick untested port from a slightly longer Python 2 program, so forgive me if it doesn't work quite right. Here's the Python 2 code, anyways:

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

EDIT: Golfed off 4 bytes by replacing or with | twice. and can't be helped, unfortunately.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Nice first post! \$\endgroup\$ – HyperNeutrino Mar 10 '17 at 3:27
  • \$\begingroup\$ Funny story actually — in my high school marching band today we learned a formation where everyone moves in concentric rectangular "rings" similar to this question, and I immediately thought of this answer. \$\endgroup\$ – Aidan F. Pierce Aug 9 '17 at 21:16
1
\$\begingroup\$

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}

Try it on Ideone.

Ungolfed:

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.