Given a spiral pattern, my job is to write a function that takes certain coordinates and returns the number at these coordinates. For example:
4 < 3 < 2
v ^
5 0 > 1
v
6 > 7 > 8
If the input is (1, -1)
, the function would return 8
.
I am not looking for a code. I am looking for an explanation as to how spiral patterns work as I am relatively new to programming (taking an introductory online course) and I have never come across such a thing. I would like to also understand the algorithm involved.
Again, I do not want any code, as I am looking to solve this myself. I am only requesting an explanation.
Update: I came up with this code which effectively determines the minimum number for the outer square and iterates until the requires coordinates are reached.
def spiral_index(x, y):
small = max(x, y)*2 - 1
min_number = small**2
xpos = max(x, y)
ypos = -max(x, y) + 1
count = min_number
while xpos != x:
xpos -= 1
count += 1
while ypos != y:
ypos += 1
count += 1
return count
However, my online course submission page rejects the code because it takes too long to execute. So I need a quicker method that is beginner-friendly.
I would think about these things to start: given the farther of the x and y coordinates, (1) how big is the square we are looking at? (how many entries are in it); (2) are we on a column where the numbers are going up or down? (same for rows and right/left); and (3) if we complete the current square, placing our target on the outer border of the square, how many numbers are "ahead" of the target? Clearly, if we know how many are in the square in total and we know how many are ahead, we can calculate the target.
Let's extend your example to (3, -1):
c c c c c c
b a a a a c
b 4 3 2 a c
b 5 0 1 a c
b 6 7 8 a T
b b b b b c
Notice that the a
s are completing the 4x4 square; the b
s the 5x5; and the c
s, the 6x6 on which our target, T
is on. A 6x6 square has 36 entries. We figure that there are 9 entries ahead of T
so T = 35 - 9 = 26.