Given an N-side square matrix, is there a way to find the ring value of a cell without using loops or if conditions?

Refresh

April 2019

Views

31 time

1

For instance, imagine you have a 6-side square matrix. These are the cells cartesian indices:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5)
(1,0) (1,1) (1,2) (1,3) (1,4) (1,5)
(2,0) (2,1) (2,2) (2,3) (2,4) (2,5)
(3,0) (3,1) (3,2) (3,3) (3,4) (3,5)
(4,0) (4,1) (4,2) (4,3) (4,4) (4,5)
(5,0) (5,1) (5,2) (5,3) (5,4) (5,5)

A 6-side square has 3 rings: a

A A A A A A
A B B B B A
A B C C B A
A B C C B A
A B B B B A
A A A A A A

QUESTION: What's the function that takes the coordinates of a cell, the side N of the square and returns the ring value accordingly? Ex:

f(x = 1, y  2, N = 6) = B

A,B,C... can be any numerical value: 1,2,3 ... or 0,1,2 ... or whatever. What matters is that they are congruent for any N. Ex:

N = 1   =>   A = 1
N = 2   =>   A = 1
N = 3   =>   A = 1, B = 2
N = 4   =>   A = 1, B = 2
N = 5   =>   A = 1, B = 2, C = 3
N = 6   =>   A = 1, B = 2, C = 3
N = 7   =>   A = 1, B = 2, C = 4, D = 4
...

Using if conditions the problem is easily solved. Given a pair (x,y) and the square side N:

# N//2 is the number of rings in a N-side square
for k in range(1,N//2+1):
    if x == 0+k-1 or y== 0+k-1 or x == N-k or y == N-1:
        return k

This seems like a very expensive way to find the ring value of the cell though. I have been trying to find the function using diagonals, sum of the coordinates, difference of the coordinates ... of the cells, but I still couldn't find anything. Has anyone ever encountered this problem? Is there a way to solve it?

3 answers

0

The ring value is the complement of the distance to the center of the array, in the "infinity norm" sense.

N/2 - max(|X - (N-1)/2|, |Y - (N-1)/2|).

This assigns the value 0 for A, 1 for B and so on.

To avoid the half integers, you can use

(N - min(|2X - N + 1|, |2Y - N + 1|) / 2.

The max and abs functions may involve hidden ifs, but you can't avoid that.


def Ring(X, Y, N):
    return (N - max(abs(2 * X - N + 1), abs(2 * Y - N + 1))) // 2

for N in range(1, 8):
    for X in range(N):
        for Y in range(N):
            print(chr(Ring(X, Y, N) + 65), '', end= '')
        print()
    print()

A 

A A 
A A 

A A A 
A B A 
A A A 

A A A A 
A B B A 
A B B A 
A A A A 

A A A A A 
A B B B A 
A B C B A 
A B B B A 
A A A A A 

A A A A A A 
A B B B B A 
A B C C B A 
A B C C B A 
A B B B B A 
A A A A A A 

A A A A A A A 
A B B B B B A 
A B C C C B A 
A B C D C B A 
A B C C C B A 
A B B B B B A 
A A A A A A A 
1

I think this function does what you want:

def ring_id(n, i, j):
    even = n % 2 == 0
    n_2 = n // 2
    i = i - n_2
    if even and i >= 0:
        i += 1
    i = abs(i)
    j = j - n_2
    if even and j >= 0:
        j += 1
    j = abs(j)
    ring_id = i + max(j - i, 0)
    return n_2 - ring_id

Small test with letters:

import string

def print_rings(n):
    ring_names = string.ascii_uppercase
    for i in range(n):
        for j in range(n):
            rid = ring_id(n, i, j)
            print(ring_names[rid], end=' ')
        print()

print_rings(6)
# A A A A A A
# A B B B B A
# A B C C B A
# A B C C B A
# A B B B B A
# A A A A A A
print_rings(7)
# A A A A A A A
# A B B B B B A
# A B C C C B A
# A B C D C B A
# A B C C C B A
# A B B B B B A
# A A A A A A A

EDIT: If you insist in not having the word if in your function, you can (somewhat awkwardly) rewrite the above function as:

def ring_id(n, i, j):
    even = 1 - n % 2
    n_2 = n // 2
    i = i - n_2
    i += even * (i >= 0)
    i = abs(i)
    j = j - n_2
    j += even * (j >= 0)
    j = abs(j)
    ring_id = i + max(j - i, 0)
    return n_2 - ring_id

Or if you want it looking more "formula-like" (albeit unreadable and with more repeated computation):

def ring_id(n, i, j):
    i2 = abs(i - (n // 2) + (1 - n % 2) * (i >= (n // 2)))
    j2 = abs(j - (n // 2) + (1 - n % 2) * (j >= (n // 2)))
    return (n // 2) - i2 + max(j2 - i2, 0)

This is not any more or less "mathematical" though, it is fundamentally the same logic.

2

Looks like a math problem to solve. EDIT: Updated function, should be better able to handle even and odd cases after the mid point i hope. However, OP's request to turn this into a mathematical equation, i'm not sure how to do that.

import math


def ring_finder(x, y, N, outer_ring = 0):
    '''
    x and y are the coordinates of a cell, N is the length of the side of square
    Returns the correct ring count starting from outer_ring value (default, 0)
    '''
    if x >= N or y >= N:
        print("coordinates outside square, please check")
        return None
    no_of_squares = math.ceil(N/2)
    x = N - x - 1 if x >= no_of_squares else x
    y = N - y - 1 if y >= no_of_squares else y
    return min(x, y) + outer_ring

ring_finder(5, 5, 6)

ring_finder(1, 2, 6)