I bet you're pretty sick of prime numbers sums.
Write a function that can rotate an NxN matrix (aka. a square 2 dimensional array) in place!
You should be able to rotate an arbitrary number of degrees clockwise or counterclockwise.
You're also not allowed to make a new array copy, that would be too easy, plus that would be impractical for non trivial matrices. No copying arrays!
Ex.
rotate(arr, 90)
a b c d m i e a
e f g h n j f b
i j k l o k g c
m n o p p l h d
Other urls found in this thread:
en.wikipedia.org
twitter.com
> You should be able to rotate an arbitrary number of degrees clockwise or counterclockwise.
Please, show me what do you expect from rotating array for 30 or 45 degrees.
def rotateSquareMatrix(m):
l = len(m)
if l > 1:
for y in range(l):
for x in range(l):
# 10, 31, 23, 02
x1, y1 = x, y
x2, y2 = l - y - 1, x
x3, y3 = l - x - 1, l - y - 1
x4, y4 = y , l - x - 1
if ((x, y) < (x2, y2) and
(x, y) < (x3, y3) and
(x, y) < (x4, y4)):
e = m[y4][x4]
m[y4][x4] = m[y3][x3]
m[y3][x3] = m[y2][x2]
m[y2][x2] = m[y1][x1]
m[y1][x1] = e
else:
pass # Nothing to do for a 0x0 or 1x1 matrix.
return m
def square(n):
r, i = [], 0
for y in range(n):
row = []
r.append(row)
for x in range(n):
row.append(i)
i += 1
return r
def matrixToString(m, f='%4s'):
r = []
for row in m:
r.append(''.join([f % (e,) for e in row]))
return '\n'.join(r)
print matrixToString(square(5))
print
print matrixToString(rotateSquareMatrix(square(5)))
Just allocate more memory to make room.
> You're also not allowed to make a new array copy
OP, where the fuck are you
I'll do you one better OP.
>consider NxN matrices as elements of SL(N,C), i.e. they have complex entries
>it is known that SL(2,N) is the complexification of SU(N) (actually this is only true up to projectivity for N > 2, but this won't matter)
>SU(N) is the universal cover of SO(N+1), meaning that they have the same Lie algebra
>SO(N+1) is homeomorphic as a topological space to the sphere S^N+1
>thus the same group of symmetry actions on S^N+1 is the same of those on SO(N+1), which is in term the same as those on SU(N)
>we know that the symmetry group of the sphere S^N+1 consisted of rotations and the reflections about the origin
>representations of the elements of this symmetry group can be parameterized by Euler angles, and are all (pseudo-)orthogonal matrices, denote these matrices by g for rotations and r for reflections
>the g's and r's belong to the Lie algebra of the symmetry group, which is isomorphic to O(N+1), e.g. for N = 2 the g's are spanned by the Pauli matrices
>using the exponential map exp: O(N+1) → Sym(SU(N)) we can reconstruct the (connected component of the) symmetry group for SU(N)
>denote G = exp(g) and R = exp(r), note that representations commute with exp (corollary of fundamental theorem of Lie algebras)
>this gives us rotations G parameterized by Euler angles and reflections R acting on SU(N)
>we now restrict the Euler angles to special rotations by nπ/2, whence n = 1,2
>this discretization (or quantization of you wish to be fancy) of angles AND reflection axes breaks Sym(SU(N)) into the dihedral group D of the square lattice
>we now have a representation of D, which we may act upon elements of SL(N,C) as symmetry operations
>this action preserves the shape of the matrix, which is what OP is looking for PLUS reflections about axes
The details are left as an exercise for the code monkeys.
This would make more sense to accept not degrees, but an integer implying a number of turns
Eg -3 rotates the matrix 3 flips counter clockwise, vice versa
It should be n = 0,1,2,3, sorry.
Where is her nose?
On her face silly user
>No copying arrays!
Is this really the sort of programming we want to be doing these days?
With GPUs being used for compute wouldn't it be better for your challenges to have more of a parallel programming slant instead of plain ol' serial programming?
>You're also not allowed to make a new array copy
>that would be impractical for non trivial matrices.
user, in that case you still need to create temporary variables for swapping each elements, which I think is less practical.
Unless of course there are other ways than swapping elements,
The best way is to just change the access methods to translate the rotated indices to the original ones and leaving the matrix unmodified.
>Unless of course there are other ways than swapping elements,
If the matrix is an object and accessed to it occur through an interface, then you could just create a new object with the same interface that changes the indexes before passing them on to the original matrix object.
30 seconds too late, sucker
Better detail on when the technique can be applied, brah.
Think this kind of object would have terrible cache behaviour though, if that matters.
a 90 degree rotation is just a transposition composed with a horizontal reflection
Write code.
both tasks are trivial to code so I leave it as an exercise to you, the reader
>"primes"
>bajillion replies
>"matricies"
>sound of crickets
We haven't even got to challenging mode yet.
>rotate matrix by 45 degrees
>state when possible and when not possible
>rotate matrix by 45 degrees
Show me an example.
That would make it too easy to solve.
If you're still here in an our, I will probably have finished writing code by then.
No I am genuinely curious. How would you "rotate" a matrix if the elements are characters and not numbers?
How can you compute the rotation matrix?
01 02 03 04 05
16 06
15 07
14 08
13 12 11 10 09
Rotates to:
05 06 01 02 03
14 04
13 05
12 06
11 10 09 08 07
15 16 01 02 03
14 04
13 05
12 06
11 10 09 08 07
I think he means something like
1 2 3 4 1 2
4 5 6 => 7 5 3
7 8 9 8 9 6
how about:
a b c ---> d a b
d e f ---> g e c
g h i ---> h i f
Now abviously this will not work for any angle - I guess.
Did you read the question?
That's not rotation. Rotation Matrices are a different thing.
en.wikipedia.org
see
He said to rotate a matrix, and never mentioned rotation matrices. Also see OP.
I looked at the example output.
Matrices doesn't "rotate". Are you programmers illiterate?
don't*
- write down a 2 dimensional matrix in standard notation on a piece of paper
- now rotate said piece of paper
If you rotate the piece of paper, the writings become meaningless
> Matrices doesn't "rotate"
Your writing is meaningless in any rotation.
That's not the matrix you just rotated, idiot wintoddler
That's because writings do not rotate
...
Checkmate atheists.
why is that thingo eating a chipo
that thing is actually akarina, the best k-on girl.
Fuck off, K-ON >>>>> Yuru Yuri. YY is OK at best, same as Yuyushiki. These people just don't have a passion to deliver a groundbreaking anime such as K-ON or Haruhi, which defined the genre.
None programmer here.
What application does this have?
Like 97% of """higher""" maths, none.
Mathematicians pride themselves in being absolutely useless.
# Number of rings, excluding the center.
# Outermost ring has a depth of zero.
# Zero-based offset.
def ringToCoord(nRings, depth, offset):
r = nRings - depth # One-based.
circumference = 8 * r
if offset < 1 * circumference / 4: x, y = offset, 0
elif offset < 2 * circumference / 4: x, y = circumference / 4, offset - circumference / 4
elif offset < 3 * circumference / 4: x, y = 3 * circumference / 4 - offset, circumference / 4
else: x, y = 0, circumference - offset
x, y = depth + x, depth + y
return x, y
def rot45InPlace(m):
l = len(m)
assert l and l % 2, "Must be odd."
if l > 1:
nRings = l // 2 # Center not important.
for depth in range(nRings): # Zero-based.
r = nRings - depth # One-based.
for a in range(r):
for b in [8, 7, 6, 5, 4, 3, 2, 1, 0]:
x2, y2 = ringToCoord(nRings, depth, a + (b % 8) * r)
if b == 8: e = m[y2][x2]
elif b == 0: m[y1][x1] = e
else: m[y1][x1] = m[y2][x2]
x1, y1 = x2, y2
else:
pass # Nothing to do for a 0x0 or 1x1 matrix.
return m
function [mat_out] = rotmat(mat_in, n)
if n
>rot90
Where's your custom implementation
Easy. Next.
0
$ = a => document.getElementsByTagName(a)[0]
$('input').addEventListener('input', () => $('pre').style.transform = `rotate(${$('input').value}deg)`)
$('body').style.overflow = 'hidden'
You can get away with using a single temp variable.
You could also XOR swap.
You would need 15 xor swaps to swap 4 numbers
I'm not advocating it, just saying it's possible
>arbitrary number of degrees
*leans in*
WRONG
multiple of 90° or π/2 radians
Why not in increments of 90/(N-1)?
I managed to do it with just one tmp variable!
void matrix_rotate(int **a, int size, int iters)
{
/* rotate clockwise */
unsigned len = size - 1;
unsigned i, j, k;
for (k = 0; k < iters % 4; k++) /* times */
{
for (i = 0; i < len / 2; i++)
{
for (j = i; j < len; j++)
{
int tmp = a[i][j];
a[i][j] = a[len-j][i];
a[len-j][i] = a[len-i][len-j];
a[len-i][len-j] = a[j][len-i];
a[j][len-i] = tmp;
}
}
}
}
bump
How about rotation by 180? 270?
prone bone akari while eating potato
Just do an in-place transpose and then in-place reverse each row?
>get to work from class
>work has demo of my code for a csv reader using a stream from amazon S3
>passed initial tests but didn't test anywhere near enough
>demo file is completely different from the files I tested
>mfw my demo soft crashes and I am left with an ungodly amount of shame
>only thing saving me from an utter shitstorm is my QA and demo person giving the usual talk on how it's a demo
this is my first year of work how fucked am I?
umm..
matrix_rotate(mat->arr, mat->n, 270 / 90);
This. You should be able to combine the transpose with the reverses, but it's probably not going to affect it too much. Reversing a subarray is fast because it's cache local, while transposing in-place is expensive because it isn't cache-local.
This is such a dumb question. You fags need formal education.
>YOU'RE NOT USING THE SPECIAL TERMINOLOGY I WAS TAUGHT AT MY EXPENSIVE UNIVIVERSITY EDUMACATION!!!!
>HOW DARE PEOPLE LEARN THINGS WITHOUT A DEGREE!!!?!
ewww a self-taught
(import (ice-9 receive) (srfi srfi-1) (srfi srfi-26))
(define (array-swap! array . idxs)
(receive (src-idxs dst-idxs)
(split-at idxs (array-rank array))
(let ((tmp (apply array-ref array dst-idxs)))
(apply array-set! array (apply array-ref array src-idxs) dst-idxs)
(apply array-set! array tmp src-idxs))))
(define (rotate90! m)
(define (swap-list size offset)
(let ((max-offset (1- size)))
(list (list offset 0)
(list 0 (- max-offset offset))
(list (- max-offset offset) max-offset)
(list max-offset offset))))
(define (rotate-at-offset! size offset)
(let loop ((lst (swap-list size offset)))
(apply array-swap! m (append (car lst) (cadr lst)))
(if (not (null? (cddr lst)))
(loop (cdr lst)))))
(let ((size (car (array-dimensions m))))
(for-each (cute rotate-at-offset! size ) (iota (1- size)))))
(define (rotate! m deg)
(for-each (lambda (x) (rotate90! m)) (iota (quotient deg 90))))
1 16 15 14 13
2 17 24 23 12
3 18 25 22 11
4 19 20 21 10
5 6 7 8 9
13 12 11 10 9
14 21 22 19 8
15 24 25 20 7
16 23 18 17 6
1 2 3 4 5
You have a bug.
Hold on a second...
S^N + 1
or
S^(N + 1)
?
They're two very different things.
Don't know how to test this.
Have shell access to a pi running raspian.
Is there any suitable package I can install?
>to the sphere S^N+1
>sphere
>S^N+1
What do you think?
I have literally never thought about spheres.
Spheres are sets. You don't do + 1 to sets.
You can run this with Guile. The name of the package in Raspbian is "guile".
1. Reverse each column
2. Transpose
Not that hard
ty
scheme@(guile-user)> test5x5array
$1 = #2((1 2 3 4 5) (16 11 22 33 6) (15 88 99 44 7) (14 77 66 55 8) (13 12 11 10 9))
scheme@(guile-user)> (rotate90! test5x5array)
scheme@(guile-user)> test5x5array
$2 = #2((5 6 7 8 9) (4 11 22 33 10) (3 88 99 44 11) (2 77 66 55 12) (1 16 15 14 13))
It's only rotating the outside of the array?
whoops
(import (ice-9 receive) (srfi srfi-1) (srfi srfi-26))
(define (array-swap! array . idxs)
(receive (src-idxs dst-idxs)
(split-at idxs (array-rank array))
(let ((tmp (apply array-ref array dst-idxs)))
(apply array-set! array (apply array-ref array src-idxs) dst-idxs)
(apply array-set! array tmp src-idxs))))
(define (rotate90! m)
(define (swap-list size offset)
(let ((max-offset (1- size)))
(list (list offset 0)
(list 0 (- max-offset offset))
(list (- max-offset offset) max-offset)
(list max-offset offset))))
(define (rotate-at-offset! size depth offset)
(let loop ((lst (map (cute map (cute + depth ) )
(swap-list (- size (* 2 depth)) offset))))
(apply array-swap! m (append (car lst) (cadr lst)))
(if (not (null? (cddr lst)))
(loop (cdr lst)))))
(define (rotate-ring90! size depth)
(for-each (cute rotate-at-offset! size depth )
(iota (- size (* 2 depth) 1))))
(let ((size (car (array-dimensions m))))
(for-each (cute rotate-ring90! size ) (iota (quotient size 2)))))
(define (rotate! m deg)
(for-each (lambda (x) (rotate90! m)) (iota (quotient deg 90))))
Looks good against my 5x5 test matrix.
Shame I can't a understand a word of the code though.