4

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.

EddieEC
  • 357
  • 4
  • 17
  • 3
    Is it always supposed to start at 3-o'clock position and go counterclockwise? – Selcuk Nov 29 '19 at 04:35
  • 1
    There are some interesting ideas in answers to this question (ignore the Haskell and focus on the explanations): https://stackoverflow.com/questions/57569623/coordinates-for-clockwise-outwards-spiral These answers are about finding the coordinates given the sequence number, whereas your question is the inverse - finding the sequence number given the coordinates, so it's not a duplicate but you may find it useful. – kaya3 Nov 29 '19 at 04:38
  • @Selcuk yes that is how the problem is stated. – EddieEC Nov 29 '19 at 04:48
  • According to your input you move 1 right and 1 down to get to 8. Thus, wouldn't you start at the `0` index? What do you mean by start at 3-o'clock position? Start at 1? – lbragile Nov 29 '19 at 04:55
  • @Ibragile 3 o’clock counter-clockwise refers to the spiral pattern itself. It starts at 0, 1 is at its right and the numbers are list in a counter-clockwise manner. – EddieEC Nov 29 '19 at 04:58
  • There might be a mathematical solution; but one way would be to generate coordinates until you hit the one you are searching for. To generate them, keep the current `x` and `y` coordinates as well as the current direction (`x_dir` and `y_dir` which can be either `0`, `1`, or `-1`). You should also keep track of the current spiral width and height (let's say `x_max` and `y_max`). Now depending on the condition (e.g. `x == x_max`) you should change the direction and calculate the coordinates for the next number. – Selcuk Nov 29 '19 at 05:21
  • @Selcuk I see. But as I mentioned in other comments, if I want (100, 100) is this an efficient way of doing it? – EddieEC Nov 29 '19 at 15:42

3 Answers3

2

Here's an attempt at some code to give an idea of what I had in mind. I'm not sure it's completely free of bugs but perhaps you could discover and fix any :) (did I miss the case when x equals y?)

(Note, the online evaluator might not like the print statements in the body of the function.)

"""
  c  c  c  T2 c  c
  b  a  a  a  a  c
  T4 4  3  2  a  c
  b  5  0  1  a  c
  b  6  7  8  a  T1
  b  T3 b  b  b  c
"""

def f(x, y):
  square_size = 1

  if x > 0:
    square_size = 2 * x
  elif x < 0:
    square_size = -2 * x + 1
  if y > 0:
    square_size = max(square_size, 2 * y)
  elif y < 0:
    square_size = max(square_size, -2 * y + 1)

  corner_length = square_size * 2 - 1
  offset = square_size // 2

  # Top-right corner (even square side)
  if square_size % 2 == 0:
    # Target is on the right
    if abs(x) > abs(y):
      num_ahead = corner_length - (offset + y)
    # Target is on the top
    else:
      num_ahead = offset + x - 1

  # Bottom-left corner (odd square side)
  else:
    # Target is on the left
    if abs(x) > abs(y):
      num_ahead = corner_length - (offset - y) - 1
    # Target is on the bottom
    else:
      num_ahead = offset - x

  print ""
  print "Target: (%s, %s)" % (x, y)
  print "Square size: %sx%s" % (square_size, square_size)
  print "Corner length: %s" % corner_length
  print "Num ahead: %s" % num_ahead

  return square_size * square_size - 1 - num_ahead

T1 = (3, -1)
T2 = (1, 3)
T3 = (-1, -2)
T4 = (-2, 1)

print f(*T1)
print f(*T2)
print f(*T3)
print f(*T4)

Output (see the illustration at the top of the code snippet):

Target: (3, -1)
Square size: 6x6
Corner length: 11
Num ahead: 9
26

Target: (1, 3)
Square size: 6x6
Corner length: 11
Num ahead: 3
32

Target: (-1, -2)
Square size: 5x5
Corner length: 9
Num ahead: 3
21

Target: (-2, 1)
Square size: 5x5
Corner length: 9
Num ahead: 7
17
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • This works perfectly, except when `abs(x) = abs(y)` and `x<0` and when `square_size % 2 != 0`. As such, I have altered this line of code: `else: # Target is on the left if abs(x) > abs(y): num_ahead = corner_length - (offset - y) - 1` To this: `else: # Target is on the left if abs(x) >= abs(y) and x < 0: num_ahead = corner_length - (offset - y) - 1` – EddieEC Nov 30 '19 at 15:18
  • @EddieEC ah, ok. Does that fix it? How does it do with the online judge? – גלעד ברקן Nov 30 '19 at 16:39
  • It got accepted. But for some reason I can't seem to grasp the concept of the offset. Can you elaborate more on that? – EddieEC Nov 30 '19 at 17:09
  • @EddieEC the offset is because (0, 0) is in the middle of the spiral. Let's say we were looking at the `c`s in my diagram (sides top and right) and coordinates (3, 0). `y` would be zero but the number we need to subtract from the total corner length includes those entries lower than the target. That's the offset calculation, because the spiral extends to all ends from the middle. If (0,0) was at the bottom left of the square, maybe we wouldn't need it. – גלעד ברקן Nov 30 '19 at 18:05
  • 1
    Thank you so much! This helps a lot! I now understand it quite well! – EddieEC Nov 30 '19 at 18:10
1

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 as are completing the 4x4 square; the bs the 5x5; and the cs, 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.

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • This is good for small numbers I presume. What if I wanted to search for (100, 100). Would doing this still be the best approach? – EddieEC Nov 29 '19 at 15:38
  • @EddieEC my intention was to provide ideas towards a way to calculate the result directly, in O(1), given the coordinates. – גלעד ברקן Nov 29 '19 at 16:03
  • 1
    @EddieEC what size square would (100, 100) be on the border of? And how many numbers would be ahead of it on this border? We should be able to calculate that directly. – גלעד ברקן Nov 29 '19 at 16:10
  • That is actually a great idea. Thank you. I will try to implement it. – EddieEC Nov 29 '19 at 17:07
  • Hey, I am trying to figure out how to determine how many numbers are ahead in the border. I have been thinking about this all day, and I am still unsure how to do it. – EddieEC Nov 30 '19 at 00:15
  • Look at the pattern of the `a`s, `b`s, `c`s. What do you notice about their lengths? – גלעד ברקן Nov 30 '19 at 00:59
  • Yes I actually figured that part out, what I am unsure of is how to figure which a, b or c is the first one. – EddieEC Nov 30 '19 at 01:03
  • 1
    @EddieEC they alternate. The first is `1,2,3`, then `4,5,6,7,8`, etc., as simply increasing odd numbers. Top-right corner for even size squares then bottom-left corner for odd size squares, repeatedly. The hundredth one would be bottom-left of a 101x101 square (off the top of my head). You can calculate the size of the "full-corner"s by the formula for odd numbers, they are of form `2x + 1` as you probably know. – גלעד ברקן Nov 30 '19 at 01:22
  • 1
    @EddieEC then think about where the coordinates would fall within the border. Start with small examples so you can test your method easily. – גלעד ברקן Nov 30 '19 at 01:23
  • I found that the lowest number for a certain square size always has coordinates (a, -a+1) where a = max(x, y). From there it becomes straightforward. However, given I am solving for an online course and have to test my code online, it returns that it took too long too execute (it works relatively well in an IDE). So this means I need a simpler version that is also not complicated for a beginner, as this exercise is at the very beginning of the course. (PS: I am sorry to bother you this much but I really need someone to discuss with as it helps me a lot) – EddieEC Nov 30 '19 at 04:57
  • @EddieEC Please show your code. You might want to add it to the question description as a code snippet (or ask a new question). – גלעד ברקן Nov 30 '19 at 05:08
  • I have updated the post with the code. Kindly check it. – EddieEC Nov 30 '19 at 05:16
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/203387/discussion-between-eddieec-and--). – EddieEC Nov 30 '19 at 16:09
0

Consider a recursive formulation.

c c c c c
c b b b c
c b a b c
c b b b c
c c c c c

Following the spiral enumerated goes 1 a, 8 b's, 16 c's, 24 d's, etc. If we consider a to be level 0 (special case), b to be level 1, and so on, then each square of size 2*level+1 has 8*level letters in it.

From there, there are 4 cases on which side of the square the coordinates are at (right, top, left, bottom). Determine which square the coordinate is in and simple arithmetic determines the spiral number.

qwr
  • 9,525
  • 5
  • 58
  • 102
  • How is this different than the answer I already posted? (which is to consider the square the target is on) – גלעד ברקן Nov 29 '19 at 06:21
  • @גלעדברקן Similar idea, different formulation – qwr Nov 29 '19 at 06:48
  • @qwr this is a good idea. I actually thought of it, but my problem is with the logic of the directions. If I want to find the number at (100,100), would going over through all the numbers be a good idea? – EddieEC Nov 29 '19 at 15:36
  • @qwr I am stuck at determining the number given which square it is. Any pointers there? – EddieEC Nov 30 '19 at 00:16
  • Consider four cases: whether it will be on the right, top, left, or bottom of a square. – qwr Nov 30 '19 at 04:32