Mixing
Diagonal snake filling array
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
Python 3.7. I'm trying to fill multidimensional array (n*m size) in diagonal-snake pattern:
1 3 4 10 11 21
2 5 9 12 20 22
6 8 13 19 23 30
7 14 18 24 29 31
15 17 25 28 32 35
16 26 27 33 34 36
I have a function for n x n size and it works fine for it. But for n x m size it returns:
1 3 4 10 14
2 5 9 15 20
6 8 16 19 19
7 17 18 20 21
My code:
def method1(i, j, n, m):
num = i+j
summ = num * (num + 1) >> 1
s = n * m
if num > n-1:
t = 2*(n-1) - (i+j) + 1
s -= t*(t+1) >> 1
if num & 1:
if num > n-1:
return s + (n-i)
else:
return summ + j+1
if num > n-1:
return s + (n-j)
else:
return summ + i+1
for i in range(n):
for j in range(m):
print(method1(i, j, n, m), end=" ")
print('n')
What am I doing wrong?
P.S. Your answer can be in any language.
python arrays numpy matrix diagonal
asked 3 hours ago
EAMax
3151418
add a comment |Â
up vote
6
down vote
favorite
Python 3.7. I'm trying to fill multidimensional array (n*m size) in diagonal-snake pattern:
1 3 4 10 11 21
2 5 9 12 20 22
6 8 13 19 23 30
7 14 18 24 29 31
15 17 25 28 32 35
16 26 27 33 34 36
I have a function for n x n size and it works fine for it. But for n x m size it returns:
1 3 4 10 14
2 5 9 15 20
6 8 16 19 19
7 17 18 20 21
My code:
def method1(i, j, n, m):
num = i+j
summ = num * (num + 1) >> 1
s = n * m
if num > n-1:
t = 2*(n-1) - (i+j) + 1
s -= t*(t+1) >> 1
if num & 1:
if num > n-1:
return s + (n-i)
else:
return summ + j+1
if num > n-1:
return s + (n-j)
else:
return summ + i+1
for i in range(n):
for j in range(m):
print(method1(i, j, n, m), end=" ")
print('n')
What am I doing wrong?
P.S. Your answer can be in any language.
python arrays numpy matrix diagonal
asked 3 hours ago
EAMax
3151418
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
Python 3.7. I'm trying to fill multidimensional array (n*m size) in diagonal-snake pattern:
1 3 4 10 11 21
2 5 9 12 20 22
6 8 13 19 23 30
7 14 18 24 29 31
15 17 25 28 32 35
16 26 27 33 34 36
I have a function for n x n size and it works fine for it. But for n x m size it returns:
1 3 4 10 14
2 5 9 15 20
6 8 16 19 19
7 17 18 20 21
My code:
def method1(i, j, n, m):
num = i+j
summ = num * (num + 1) >> 1
s = n * m
if num > n-1:
t = 2*(n-1) - (i+j) + 1
s -= t*(t+1) >> 1
if num & 1:
if num > n-1:
return s + (n-i)
else:
return summ + j+1
if num > n-1:
return s + (n-j)
else:
return summ + i+1
for i in range(n):
for j in range(m):
print(method1(i, j, n, m), end=" ")
print('n')
What am I doing wrong?
P.S. Your answer can be in any language.
python arrays numpy matrix diagonal
asked 3 hours ago
EAMax
3151418
Python 3.7. I'm trying to fill multidimensional array (n*m size) in diagonal-snake pattern:
1 3 4 10 11 21
2 5 9 12 20 22
6 8 13 19 23 30
7 14 18 24 29 31
15 17 25 28 32 35
16 26 27 33 34 36
I have a function for n x n size and it works fine for it. But for n x m size it returns:
1 3 4 10 14
2 5 9 15 20
6 8 16 19 19
7 17 18 20 21
My code:
def method1(i, j, n, m):
num = i+j
summ = num * (num + 1) >> 1
s = n * m
if num > n-1:
t = 2*(n-1) - (i+j) + 1
s -= t*(t+1) >> 1
if num & 1:
if num > n-1:
return s + (n-i)
else:
return summ + j+1
if num > n-1:
return s + (n-j)
else:
return summ + i+1
for i in range(n):
for j in range(m):
print(method1(i, j, n, m), end=" ")
print('n')
What am I doing wrong?
P.S. Your answer can be in any language.
python arrays numpy matrix diagonal
python arrays numpy matrix diagonal
asked 3 hours ago
EAMax
3151418
asked 3 hours ago
EAMax
3151418
asked 3 hours ago
EAMax
3151418
asked 3 hours ago
EAMax
3151418
asked 3 hours ago
EAMax
3151418
3151418
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
not clear what you are doing wrong, but the following code should work:
import numpy as np
n = 4
m = 5
x, y = (0, 0)
ux, uy = (1, -1)
a = np.zeros((n, m))
for i in range(n*m):
print((x, y), i+1)
a[x, y] = i + 1
x, y = (x + ux, y + uy)
if y == m:
print('right side') # including corner
y = m - 1
x += 2
elif x == n:
print('bottom side') # including corner
x = n - 1
y += 2
elif x == -1:
print('top side')
x = 0
elif y == -1:
print('left side')
y = 0
else:
continue
ux, uy = -ux, -uy
print(a)
output:
(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1. 3. 4. 10. 11.]
[ 2. 5. 9. 12. 17.]
[ 6. 8. 13. 16. 18.]
[ 7. 14. 15. 19. 20.]]
To write this, it helped a lot to draw a diagram.
answered 2 hours ago
pietroppeter
32918
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
add a comment |Â
up vote
4
down vote
Here is a vectorized solution:
def tr(z):
return z*(z+1)//2
def snake(Y, X):
y, x = np.ogrid[:Y, :X]
mn, mx = np.minimum(X, Y), np.maximum(X, Y)
return (1 + tr(np.clip(x+y, None, mn))
+ mn * np.clip(x+y - mn, 0, None)
- tr(np.clip(x+y - mx, 0, None))
+ ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
+ ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))
Demo:
>>> snake(7, 3)
array([[ 1, 3, 4],
[ 2, 5, 9],
[ 6, 8, 10],
[ 7, 11, 15],
[12, 14, 16],
[13, 17, 20],
[18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
[2, 5, 6, 8]])
Explainer:
The function tr computes the number of elements in a triangle which is more or less half a square (a tiny bit more because we include the diagonal). This is used in snake to compute the offset of each diagonal; diagonals are indexed by x+y.
More precisely, the first three lines in the return statement compute the diagonal offset. The first line counts diagonals in the top left triangle, the second line counts full length diagonals and also those in the bottom right triangle; it counts those also as full length - the third line corrects for that.
The last two lines count within diagonals. The first of the two in top-right direction, the second in bottom-left direction. Observe, that the top-right offset is equal to the x coordinate for all diagonals that start at the left edge. The correction term (np.clip ...) is for diagonals starting at the bottom edge. Similarly bottom-left offsets are y if we start at the top edge and require a correction if we start at the right edge.
answered 1 hour ago
Paul Panzer
28.1k21138
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
add a comment |Â
up vote
2
down vote
EDIT:
Here is a version of basically the same algorithm but without any loops:
def snake_matrix(n):
# Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
i = np.arange(n)
c = np.cumsum(i)
reps = np.repeat(c, i + 1)
seqs = np.arange(len(reps)) - reps
# Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
i_rep = np.repeat(i, i + 1)
seqs_inv = i_rep - seqs
# Select sequences for row and column indices
seq_even_mask = (i_rep % 2 == 0)
# Row inverts even sequences
row = np.where(seq_even_mask, seqs, seqs_inv)
# Column inverts odd sequences
col = np.where(~seq_even_mask, seqs, seqs_inv)
# Mirror for lower right corner
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
Interestingly, after a couple of benchmarks it seems that depending on the size this may or may not be faster than the previous algorithm.
Here is another solution with NumPy. I don't know if there is any other way to make this better (without loops, or in this case list comprehensions), but at least it does not loop over every single element. This one only works for square matrices though.
import numpy as np
def snake_matrix(n):
# Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
seqs = [np.arange(i + 1) for i in range(n)]
# Row indices reverse odd sequences
row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
# Column indices reverse even sequences
col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
# Indices for bottom right triangle "mirror" top left triangle
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
# Make matrix
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
print(snake_matrix(6))
Output:
[[ 0 2 3 9 10 20]
[ 1 4 8 11 19 21]
[ 5 7 12 18 22 29]
[ 6 13 17 23 28 30]
[14 16 24 27 31 34]
[15 25 26 32 33 35]]
There is some more information about this kind of enumeration in OEIS A319571 sequence (although that refers to the general sequence for an infinite grid, in this case you would have one enumeration starting at the top left and another at the bottom right).
answered 1 hour ago
jdehesa
20.2k33050
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
not clear what you are doing wrong, but the following code should work:
import numpy as np
n = 4
m = 5
x, y = (0, 0)
ux, uy = (1, -1)
a = np.zeros((n, m))
for i in range(n*m):
print((x, y), i+1)
a[x, y] = i + 1
x, y = (x + ux, y + uy)
if y == m:
print('right side') # including corner
y = m - 1
x += 2
elif x == n:
print('bottom side') # including corner
x = n - 1
y += 2
elif x == -1:
print('top side')
x = 0
elif y == -1:
print('left side')
y = 0
else:
continue
ux, uy = -ux, -uy
print(a)
output:
(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1. 3. 4. 10. 11.]
[ 2. 5. 9. 12. 17.]
[ 6. 8. 13. 16. 18.]
[ 7. 14. 15. 19. 20.]]
To write this, it helped a lot to draw a diagram.
answered 2 hours ago
pietroppeter
32918
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
add a comment |Â
up vote
3
down vote
accepted
not clear what you are doing wrong, but the following code should work:
import numpy as np
n = 4
m = 5
x, y = (0, 0)
ux, uy = (1, -1)
a = np.zeros((n, m))
for i in range(n*m):
print((x, y), i+1)
a[x, y] = i + 1
x, y = (x + ux, y + uy)
if y == m:
print('right side') # including corner
y = m - 1
x += 2
elif x == n:
print('bottom side') # including corner
x = n - 1
y += 2
elif x == -1:
print('top side')
x = 0
elif y == -1:
print('left side')
y = 0
else:
continue
ux, uy = -ux, -uy
print(a)
output:
(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1. 3. 4. 10. 11.]
[ 2. 5. 9. 12. 17.]
[ 6. 8. 13. 16. 18.]
[ 7. 14. 15. 19. 20.]]
To write this, it helped a lot to draw a diagram.
answered 2 hours ago
pietroppeter
32918
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
not clear what you are doing wrong, but the following code should work:
import numpy as np
n = 4
m = 5
x, y = (0, 0)
ux, uy = (1, -1)
a = np.zeros((n, m))
for i in range(n*m):
print((x, y), i+1)
a[x, y] = i + 1
x, y = (x + ux, y + uy)
if y == m:
print('right side') # including corner
y = m - 1
x += 2
elif x == n:
print('bottom side') # including corner
x = n - 1
y += 2
elif x == -1:
print('top side')
x = 0
elif y == -1:
print('left side')
y = 0
else:
continue
ux, uy = -ux, -uy
print(a)
output:
(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1. 3. 4. 10. 11.]
[ 2. 5. 9. 12. 17.]
[ 6. 8. 13. 16. 18.]
[ 7. 14. 15. 19. 20.]]
To write this, it helped a lot to draw a diagram.
answered 2 hours ago
pietroppeter
32918
not clear what you are doing wrong, but the following code should work:
import numpy as np
n = 4
m = 5
x, y = (0, 0)
ux, uy = (1, -1)
a = np.zeros((n, m))
for i in range(n*m):
print((x, y), i+1)
a[x, y] = i + 1
x, y = (x + ux, y + uy)
if y == m:
print('right side') # including corner
y = m - 1
x += 2
elif x == n:
print('bottom side') # including corner
x = n - 1
y += 2
elif x == -1:
print('top side')
x = 0
elif y == -1:
print('left side')
y = 0
else:
continue
ux, uy = -ux, -uy
print(a)
output:
(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1. 3. 4. 10. 11.]
[ 2. 5. 9. 12. 17.]
[ 6. 8. 13. 16. 18.]
[ 7. 14. 15. 19. 20.]]
To write this, it helped a lot to draw a diagram.
answered 2 hours ago
pietroppeter
32918
answered 2 hours ago
pietroppeter
32918
answered 2 hours ago
pietroppeter
32918
answered 2 hours ago
pietroppeter
32918
32918
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
add a comment |Â
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
It works like a charm! Thanks for your solution.
– EAMax
2 hours ago
add a comment |Â
up vote
4
down vote
Here is a vectorized solution:
def tr(z):
return z*(z+1)//2
def snake(Y, X):
y, x = np.ogrid[:Y, :X]
mn, mx = np.minimum(X, Y), np.maximum(X, Y)
return (1 + tr(np.clip(x+y, None, mn))
+ mn * np.clip(x+y - mn, 0, None)
- tr(np.clip(x+y - mx, 0, None))
+ ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
+ ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))
Demo:
>>> snake(7, 3)
array([[ 1, 3, 4],
[ 2, 5, 9],
[ 6, 8, 10],
[ 7, 11, 15],
[12, 14, 16],
[13, 17, 20],
[18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
[2, 5, 6, 8]])
Explainer:
The function tr computes the number of elements in a triangle which is more or less half a square (a tiny bit more because we include the diagonal). This is used in snake to compute the offset of each diagonal; diagonals are indexed by x+y.
More precisely, the first three lines in the return statement compute the diagonal offset. The first line counts diagonals in the top left triangle, the second line counts full length diagonals and also those in the bottom right triangle; it counts those also as full length - the third line corrects for that.
The last two lines count within diagonals. The first of the two in top-right direction, the second in bottom-left direction. Observe, that the top-right offset is equal to the x coordinate for all diagonals that start at the left edge. The correction term (np.clip ...) is for diagonals starting at the bottom edge. Similarly bottom-left offsets are y if we start at the top edge and require a correction if we start at the right edge.
answered 1 hour ago
Paul Panzer
28.1k21138
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
add a comment |Â
up vote
4
down vote
Here is a vectorized solution:
def tr(z):
return z*(z+1)//2
def snake(Y, X):
y, x = np.ogrid[:Y, :X]
mn, mx = np.minimum(X, Y), np.maximum(X, Y)
return (1 + tr(np.clip(x+y, None, mn))
+ mn * np.clip(x+y - mn, 0, None)
- tr(np.clip(x+y - mx, 0, None))
+ ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
+ ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))
Demo:
>>> snake(7, 3)
array([[ 1, 3, 4],
[ 2, 5, 9],
[ 6, 8, 10],
[ 7, 11, 15],
[12, 14, 16],
[13, 17, 20],
[18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
[2, 5, 6, 8]])
Explainer:
The function tr computes the number of elements in a triangle which is more or less half a square (a tiny bit more because we include the diagonal). This is used in snake to compute the offset of each diagonal; diagonals are indexed by x+y.
More precisely, the first three lines in the return statement compute the diagonal offset. The first line counts diagonals in the top left triangle, the second line counts full length diagonals and also those in the bottom right triangle; it counts those also as full length - the third line corrects for that.
The last two lines count within diagonals. The first of the two in top-right direction, the second in bottom-left direction. Observe, that the top-right offset is equal to the x coordinate for all diagonals that start at the left edge. The correction term (np.clip ...) is for diagonals starting at the bottom edge. Similarly bottom-left offsets are y if we start at the top edge and require a correction if we start at the right edge.
answered 1 hour ago
Paul Panzer
28.1k21138
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Here is a vectorized solution:
def tr(z):
return z*(z+1)//2
def snake(Y, X):
y, x = np.ogrid[:Y, :X]
mn, mx = np.minimum(X, Y), np.maximum(X, Y)
return (1 + tr(np.clip(x+y, None, mn))
+ mn * np.clip(x+y - mn, 0, None)
- tr(np.clip(x+y - mx, 0, None))
+ ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
+ ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))
Demo:
>>> snake(7, 3)
array([[ 1, 3, 4],
[ 2, 5, 9],
[ 6, 8, 10],
[ 7, 11, 15],
[12, 14, 16],
[13, 17, 20],
[18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
[2, 5, 6, 8]])
Explainer:
The function tr computes the number of elements in a triangle which is more or less half a square (a tiny bit more because we include the diagonal). This is used in snake to compute the offset of each diagonal; diagonals are indexed by x+y.
More precisely, the first three lines in the return statement compute the diagonal offset. The first line counts diagonals in the top left triangle, the second line counts full length diagonals and also those in the bottom right triangle; it counts those also as full length - the third line corrects for that.
The last two lines count within diagonals. The first of the two in top-right direction, the second in bottom-left direction. Observe, that the top-right offset is equal to the x coordinate for all diagonals that start at the left edge. The correction term (np.clip ...) is for diagonals starting at the bottom edge. Similarly bottom-left offsets are y if we start at the top edge and require a correction if we start at the right edge.
answered 1 hour ago
Paul Panzer
28.1k21138
Here is a vectorized solution:
def tr(z):
return z*(z+1)//2
def snake(Y, X):
y, x = np.ogrid[:Y, :X]
mn, mx = np.minimum(X, Y), np.maximum(X, Y)
return (1 + tr(np.clip(x+y, None, mn))
+ mn * np.clip(x+y - mn, 0, None)
- tr(np.clip(x+y - mx, 0, None))
+ ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
+ ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))
Demo:
>>> snake(7, 3)
array([[ 1, 3, 4],
[ 2, 5, 9],
[ 6, 8, 10],
[ 7, 11, 15],
[12, 14, 16],
[13, 17, 20],
[18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
[2, 5, 6, 8]])
Explainer:
The function tr computes the number of elements in a triangle which is more or less half a square (a tiny bit more because we include the diagonal). This is used in snake to compute the offset of each diagonal; diagonals are indexed by x+y.
More precisely, the first three lines in the return statement compute the diagonal offset. The first line counts diagonals in the top left triangle, the second line counts full length diagonals and also those in the bottom right triangle; it counts those also as full length - the third line corrects for that.
The last two lines count within diagonals. The first of the two in top-right direction, the second in bottom-left direction. Observe, that the top-right offset is equal to the x coordinate for all diagonals that start at the left edge. The correction term (np.clip ...) is for diagonals starting at the bottom edge. Similarly bottom-left offsets are y if we start at the top edge and require a correction if we start at the right edge.
answered 1 hour ago
Paul Panzer
28.1k21138
edited 49 mins ago
answered 1 hour ago
Paul Panzer
28.1k21138
answered 1 hour ago
Paul Panzer
28.1k21138
answered 1 hour ago
Paul Panzer
28.1k21138
28.1k21138
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
add a comment |Â
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
This is impressive but no clue how you got that working! Not sure if it can be explained tersely though.
– jdehesa
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
So hard for me, but useful to explore. Thanks!
– EAMax
1 hour ago
2
2
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
@jdehesa, EAMax I added some explanation. Hope it helps.
– Paul Panzer
48 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
great answer and very well explained also! in understanding the different parts it helped for me to print the various addends of the return function.
– pietroppeter
37 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
I think this is a way better answer than mine (especially now with the explanation). @EAMax, feel free to change accepted answer!
– pietroppeter
14 mins ago
add a comment |Â
up vote
2
down vote
EDIT:
Here is a version of basically the same algorithm but without any loops:
def snake_matrix(n):
# Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
i = np.arange(n)
c = np.cumsum(i)
reps = np.repeat(c, i + 1)
seqs = np.arange(len(reps)) - reps
# Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
i_rep = np.repeat(i, i + 1)
seqs_inv = i_rep - seqs
# Select sequences for row and column indices
seq_even_mask = (i_rep % 2 == 0)
# Row inverts even sequences
row = np.where(seq_even_mask, seqs, seqs_inv)
# Column inverts odd sequences
col = np.where(~seq_even_mask, seqs, seqs_inv)
# Mirror for lower right corner
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
Interestingly, after a couple of benchmarks it seems that depending on the size this may or may not be faster than the previous algorithm.
Here is another solution with NumPy. I don't know if there is any other way to make this better (without loops, or in this case list comprehensions), but at least it does not loop over every single element. This one only works for square matrices though.
import numpy as np
def snake_matrix(n):
# Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
seqs = [np.arange(i + 1) for i in range(n)]
# Row indices reverse odd sequences
row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
# Column indices reverse even sequences
col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
# Indices for bottom right triangle "mirror" top left triangle
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
# Make matrix
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
print(snake_matrix(6))
Output:
[[ 0 2 3 9 10 20]
[ 1 4 8 11 19 21]
[ 5 7 12 18 22 29]
[ 6 13 17 23 28 30]
[14 16 24 27 31 34]
[15 25 26 32 33 35]]
There is some more information about this kind of enumeration in OEIS A319571 sequence (although that refers to the general sequence for an infinite grid, in this case you would have one enumeration starting at the top left and another at the bottom right).
answered 1 hour ago
jdehesa
20.2k33050
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
add a comment |Â
up vote
2
down vote
EDIT:
Here is a version of basically the same algorithm but without any loops:
def snake_matrix(n):
# Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
i = np.arange(n)
c = np.cumsum(i)
reps = np.repeat(c, i + 1)
seqs = np.arange(len(reps)) - reps
# Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
i_rep = np.repeat(i, i + 1)
seqs_inv = i_rep - seqs
# Select sequences for row and column indices
seq_even_mask = (i_rep % 2 == 0)
# Row inverts even sequences
row = np.where(seq_even_mask, seqs, seqs_inv)
# Column inverts odd sequences
col = np.where(~seq_even_mask, seqs, seqs_inv)
# Mirror for lower right corner
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
Interestingly, after a couple of benchmarks it seems that depending on the size this may or may not be faster than the previous algorithm.
Here is another solution with NumPy. I don't know if there is any other way to make this better (without loops, or in this case list comprehensions), but at least it does not loop over every single element. This one only works for square matrices though.
import numpy as np
def snake_matrix(n):
# Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
seqs = [np.arange(i + 1) for i in range(n)]
# Row indices reverse odd sequences
row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
# Column indices reverse even sequences
col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
# Indices for bottom right triangle "mirror" top left triangle
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
# Make matrix
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
print(snake_matrix(6))
Output:
[[ 0 2 3 9 10 20]
[ 1 4 8 11 19 21]
[ 5 7 12 18 22 29]
[ 6 13 17 23 28 30]
[14 16 24 27 31 34]
[15 25 26 32 33 35]]
There is some more information about this kind of enumeration in OEIS A319571 sequence (although that refers to the general sequence for an infinite grid, in this case you would have one enumeration starting at the top left and another at the bottom right).
answered 1 hour ago
jdehesa
20.2k33050
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
EDIT:
Here is a version of basically the same algorithm but without any loops:
def snake_matrix(n):
# Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
i = np.arange(n)
c = np.cumsum(i)
reps = np.repeat(c, i + 1)
seqs = np.arange(len(reps)) - reps
# Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
i_rep = np.repeat(i, i + 1)
seqs_inv = i_rep - seqs
# Select sequences for row and column indices
seq_even_mask = (i_rep % 2 == 0)
# Row inverts even sequences
row = np.where(seq_even_mask, seqs, seqs_inv)
# Column inverts odd sequences
col = np.where(~seq_even_mask, seqs, seqs_inv)
# Mirror for lower right corner
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
Interestingly, after a couple of benchmarks it seems that depending on the size this may or may not be faster than the previous algorithm.
Here is another solution with NumPy. I don't know if there is any other way to make this better (without loops, or in this case list comprehensions), but at least it does not loop over every single element. This one only works for square matrices though.
import numpy as np
def snake_matrix(n):
# Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
seqs = [np.arange(i + 1) for i in range(n)]
# Row indices reverse odd sequences
row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
# Column indices reverse even sequences
col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
# Indices for bottom right triangle "mirror" top left triangle
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
# Make matrix
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
print(snake_matrix(6))
Output:
[[ 0 2 3 9 10 20]
[ 1 4 8 11 19 21]
[ 5 7 12 18 22 29]
[ 6 13 17 23 28 30]
[14 16 24 27 31 34]
[15 25 26 32 33 35]]
There is some more information about this kind of enumeration in OEIS A319571 sequence (although that refers to the general sequence for an infinite grid, in this case you would have one enumeration starting at the top left and another at the bottom right).
answered 1 hour ago
jdehesa
20.2k33050
EDIT:
Here is a version of basically the same algorithm but without any loops:
def snake_matrix(n):
# Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
i = np.arange(n)
c = np.cumsum(i)
reps = np.repeat(c, i + 1)
seqs = np.arange(len(reps)) - reps
# Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
i_rep = np.repeat(i, i + 1)
seqs_inv = i_rep - seqs
# Select sequences for row and column indices
seq_even_mask = (i_rep % 2 == 0)
# Row inverts even sequences
row = np.where(seq_even_mask, seqs, seqs_inv)
# Column inverts odd sequences
col = np.where(~seq_even_mask, seqs, seqs_inv)
# Mirror for lower right corner
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
Interestingly, after a couple of benchmarks it seems that depending on the size this may or may not be faster than the previous algorithm.
Here is another solution with NumPy. I don't know if there is any other way to make this better (without loops, or in this case list comprehensions), but at least it does not loop over every single element. This one only works for square matrices though.
import numpy as np
def snake_matrix(n):
# Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
seqs = [np.arange(i + 1) for i in range(n)]
# Row indices reverse odd sequences
row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
# Column indices reverse even sequences
col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
# Indices for bottom right triangle "mirror" top left triangle
row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
# Make matrix
m = np.empty((n, n), dtype=int)
m[row, col] = np.arange(n * n)
return m
print(snake_matrix(6))
Output:
[[ 0 2 3 9 10 20]
[ 1 4 8 11 19 21]
[ 5 7 12 18 22 29]
[ 6 13 17 23 28 30]
[14 16 24 27 31 34]
[15 25 26 32 33 35]]
There is some more information about this kind of enumeration in OEIS A319571 sequence (although that refers to the general sequence for an infinite grid, in this case you would have one enumeration starting at the top left and another at the bottom right).
answered 1 hour ago
jdehesa
20.2k33050
edited 42 mins ago
answered 1 hour ago
jdehesa
20.2k33050
answered 1 hour ago
jdehesa
20.2k33050
answered 1 hour ago
jdehesa
20.2k33050
20.2k33050
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
add a comment |Â
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
Thanks for your response. It is so helpful.
– EAMax
1 hour ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
@EAMax Glad it helped. I added a version without loops just for interest, although it is not always faster than the other. Anyway as I said this algorithm is only for square matrices so it's still not a full solution.
– jdehesa
58 mins ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53173098%2fdiagonal-snake-filling-array%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password