Looping in a spiral

Question

A friend was in need of an algorithm that would let him loop through the elements of an NxM matrix (N and M are odd). I came up with a solution, but I wanted to see if my fellow SO'ers could come up with a better solution.

I'm posting my solution as an answer to this question.

Example Output:

For a 3x3 matrix, the output should be:

(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)

Furthermore, the algorithm should support non-square matrices, so for example for a 5x3 matrix, the output should be:

(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) (2, -1) (2, 0) (2, 1) (-2, 1) (-2, 0) (-2, -1)

Answer 1

Java spiral "Code golf" attempt, based on the C++ variant.

public static void Spiral(int X, int Y) {
    int x=0, y=0, dx = 0, dy = -1;
    int t = Math.max(X,Y);
    int maxI = t*t;

    for (int i=0; i < maxI; i++){
        if ((-X/2 <= x) && (x <= X/2) && (-Y/2 <= y) && (y <= Y/2)) {
            System.out.println(x+","+y);
            //DO STUFF
        }

        if( (x == y) || ((x < 0) && (x == -y)) || ((x > 0) && (x == 1-y))) {
            t=dx; dx=-dy; dy=t;
        }   
        x+=dx; y+=dy;
    }
}

Answer 2

let x = 0
let y = 0
let d = 1
let m = 1

while true
  while 2 * x * d < m
    print(x, y)
    x = x + d
  while 2 * y * d < m
    print(x, y)
    y = y + d
  d = -1 * d
  m = m + 1

There have been many proposed solutions for this problem wrote in various programming languages however they all seem to stem from the same convoluted approach. I'm going to consider the more general problem of computing a spiral which can be expressed concisely using induction.

Base case: Start at (0, 0), move forward 1 square, turn left, move forward 1 square, turn left. Inductive step: Move forward n+1 squares, turn left, move forward n+1 squares, turn left.

The mathematical elegance of expressing this problem strongly suggests there should be a simple algorithm to compute the solution. Keeping abstraction in mind, I've chosen not to implement the algorithm in a specific programming language but rather as pseudo-code.

First I'll consider an algorithm to compute just 2 iterations of the spiral using 4 pairs of while loops. The structure of each pair is similar, yet distinct in its own right. This may seem crazy at first (some loops only get executed once) but step by step I'll make transformations until we arrive at 4 pairs of loops that are identical and hence can be replaced with a single pair placed inside of another loop. This will provide us with a general solution of computing n iterations without using any conditionals.

let x = 0
let y = 0

//RIGHT, UP
while x < 1
  print(x, y)
  x = x + 1
while y < 1
  print(x, y)
  y = y + 1

//LEFT, LEFT, DOWN, DOWN
while x > -1
  print(x, y)
  x = x - 1
while y > -1
  print(x, y)
  y = y - 1

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x < 2
  print(x, y)
  x = x + 1
while y < 2
  print(x, y)
  y = y + 1

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x > -2
  print(x, y)
  x = x - 1
while y > -2
  print(x, y)
  y = y - 1

The first transformation we will make is the introduction of a new variable d, for direction, that holds either the value +1 or -1. The direction switches after each pair of loops. Since we know the value of d at all points, we can multiply each side of each inequality by it, adjust the direction of the inequality accordingly and simplify any multiplications of d by a constant to another constant. This leaves us with the following.

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

Now we note that both x * d and the RHS are integers so we can subtract any real value between 0 and 1 from the RHS without affecting the result of the inequality. We choose to subtract 0.5 from the inequalities of every other pair of while loops in order to establish more of a pattern.

let x = 0
let y = 0
let d = 1

//RIGHT, UP
while x * d < 0.5
  print(x, y)
  x = x + d
while y * d < 0.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, DOWN, DOWN
while x * d < 1
  print(x, y)
  x = x + d
while y * d < 1
  print(x, y)
  y = y + d
d = -1 * d

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < 1.5
  print(x, y)
  x = x + d
while y * d < 1.5
  print(x, y)
  y = y + d
d = -1 * d

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < 2
  print(x, y)
  x = x + d
while y * d < 2
  print(x, y)
  y = y + d

We can now introduce another variable m for the number of steps we take at each pair of while loops.

let x = 0
let y = 0
let d = 1
let m = 0.5

//RIGHT, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//RIGHT, RIGHT, RIGHT, UP, UP, UP
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d
d = -1 * d
m = m + 0.5

//LEFT, LEFT, LEFT, LEFT, DOWN, DOWN, DOWN, DOWN
while x * d < m
  print(x, y)
  x = x + d
while y * d < m
  print(x, y)
  y = y + d

Finally, we see that the structure of each pair of while loops is identical and can be reduced to a single loop placed inside of another loop. Also, to avoid using real valued numbers I've multiplied the initial value of m; the value m is incremented by; and both sides of each inequality by 2.

This leads to the solution shown at the beginning of this answer.

Answer 3

Here's a C++ solution that shows that you can calculate the next (x, y) coordinates directly and easily from the previous ones - no need for tracking the current direction, radius, or anything else:

void spiral(const int M, const int N)
{
    // Generate an Ulam spiral centered at (0, 0).
    int x = 0;
    int y = 0;

    int end = max(N, M) * max(N, M);
    for(int i = 0; i < end; ++i)
    {
        // Translate coordinates and mask them out.
        int xp = x + N / 2;
        int yp = y + M / 2;
        if(xp >= 0 && xp < N && yp >= 0 && yp < M)
            cout << xp << '\t' << yp << '\n';

        // No need to track (dx, dy) as the other examples do:
        if(abs(x) <= abs(y) && (x != y || x >= 0))
            x += ((y >= 0) ? 1 : -1);
        else
            y += ((x >= 0) ? -1 : 1);
    }
}

If all you're trying to do is generate the first N points in the spiral (without the original problem's constraint of masking to an N x M region), the code becomes very simple:

void spiral(const int N)
{
    int x = 0;
    int y = 0;
    for(int i = 0; i < N; ++i)
    {
        cout << x << '\t' << y << '\n';
        if(abs(x) <= abs(y) && (x != y || x >= 0))
            x += ((y >= 0) ? 1 : -1);
        else
            y += ((x >= 0) ? -1 : 1);
    }
}

The trick is that you can compare x and y to determine what side of the square you're on, and that tells you what direction to move in.

Answer 4

Solution for AutoIt

#include <Math.au3>
#include <Array.au3>

Func SpiralSearch($xMax,$yMax)
    $x = 0
    $y = 0
    $dx = 0
    $dy = -1
    for $i=0 To _max($xMax, $yMax)^2-1 Step 1
        if -$xMax/2 < $x and $x <= $xMax/2 And -$yMax/2 < $y And $y <= $yMax/2 Then
            MsgBox(0, "We are here ", $x & " " & $y)
        EndIf
        if $x == $y or ($x < 0 and $x == -$y) or ($x > 0 and $x == 1-$y) Then
            _ArraySwap ($dx, $dy)
            $dx=-$dx
        EndIf
        $x += $dx
        $y += $dy
    Next
EndFunc

Answer 5

Here's my solution (in Python):

def spiral(X, Y):
    x = y = 0
    dx = 0
    dy = -1
    for i in range(max(X, Y)**2):
        if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2):
            print (x, y)
            # DO STUFF...
        if x == y or (x < 0 and x == -y) or (x > 0 and x == 1-y):
            dx, dy = -dy, dx
        x, y = x+dx, y+dy

Answer 6

Just for fun in Javascript:

function spiral(x, y) {
  var iy = ix = 0
    , hr = (x - 1) / 2
    , vr = (y - 1) / 2
    , tt = x * y
    , matrix = []
    , step = 1
    , dx = 1
    , dy = 0;

  while(matrix.length < tt) {

    if((ix <= hr && ix >= (hr * -1)) && (iy <= vr && (iy >= (vr * -1)))) {
      console.log(ix, iy);
      matrix.push([ix, iy]);
    }

    ix += dx;
    iy += dy;

    // check direction
    if(dx !== 0) {
      // increase step
      if(ix === step && iy === (step * -1)) step++;

      // horizontal range reached
      if(ix === step || (ix === step * -1)) {
        dy = (ix === iy)? (dx * -1) : dx;
        dx = 0;  
      }
    } else {
      // vertical range reached
      if(iy === step || (iy === step * -1)) {
        dx = (ix === iy)? (dy * -1) : dy;
        dy = 0;
      }
    }
  }

  return matrix;
}

var sp = spiral(5, 3);