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

I couldn't find a Rust implementation, so I picked the one from @neatsu as inspiration and wrote it in Rust.

My implementation "fills" the area described by the size variable, i.e. it stops as soon as the next step would go outside of the given dimensions, and starts at the origin location.

I also changed the direction to go Right -> Up -> Left -> Down.

use Direction::*;
enum Direction { Up, Down, Left, Right }
impl Direction {
    fn next(&mut self) {
        *self = match self { Up => Left, Down => Right, Left => Down, Right => Up }
    }
}
fn spiral(origin: (f64, f64), size: (f64, f64), step: f64) -> Vec<(f64, f64)> {
    let (mut distance, mut range, mut direction, mut x, mut y) = (0,1,Right, origin.0, origin.1);
    let mut res_vec = Vec::<(f64, f64)>::new();
    while x.abs() <= size.0/2.0 && y.abs() <= size.1/2.0 {
        res_vec.push((x, y)); distance += 1;
        match direction {
            Up => { y += step; if distance >= range { direction.next(); distance = 0; range += 1;}},
            Down => { y -= step; if distance >= range { direction.next(); distance = 0; range += 1; }},
            Left => { x -= step; if distance >= range { direction.next(); distance = 0; }},
            Right => { x += step; if distance >= range { direction.next(); distance = 0; }},
        }
    }
    return res_vec;
}

Usage:

let res = spiral((0.0, 0.0), (2.0, 2.0), 0.2);
print!("{:?}", res);

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.

EDIT: It has been a few years but I had a similar problem and wrote the following solution in F# which I want to share. The word print may have been a misnomer in my original answer but hopefully this non-pseudocode version will address any points raised in the comments regarding versatility and termination conditions. I have added example use cases for spiralling about an arbitrary point and finding the correct solution to the original problem for iterating an NxM matrix.

let spiral =
    let rec f (x, y) d m = seq {
        let mutable x = x
        let mutable y = y
        while 2 * x * d < m do
            yield x, y
            x <- x + d
        while 2 * y * d < m do
            yield x, y
            y <- y + d
        yield! f (x, y) -d (m + 1)
    }
    f (0, 0) 1 1

spiral
|> Seq.take 5
|> List.ofSeq;;
// [(0, 0); (1, 0); (1, 1); (0, 1); (-1, 1)]

spiral
|> Seq.take 5
|> Seq.map (fun (x, y) -> x + 5, y + 5)
|> List.ofSeq;;
// [(5, 5); (6, 5); (6, 6); (5, 6); (4, 6)]

spiral
|> Seq.takeWhile (fun (x, y) -> x * x + y * y < 9)
|> Seq.filter (fun (x, y) -> -2 <= x && x <= 2 && -1 <= y && y <= 1)
|> List.ofSeq;;
// [(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 3

A Kotlin spiral.

data class Point(val x: Int, val y: Int) {
    operator fun plus(p: Point): Point = Point(x + p.x, y + p.y)

    override fun toString() = "($x, $y)"

    companion object {
        enum class Directions(val d: Point) {
            RIGHT(Point(1, 0)),
            UP(Point(0, 1)),
            LEFT(Point(-1, 0)),
            DOWN(Point(0, -1))
        }

        fun spiral() = sequence {
            var p = Point(0, 0)
            // Always start at the origin.
            yield(p)
            // 0, 2, 4, 6 ...
            generateSequence(0) { it + 2 }.forEach { n ->
                // For each of the 4 directions
                Directions.values().forEach { d ->
                    // actual length depends slightly on direction
                    val l = n + when (d) {
                        Directions.RIGHT, Directions.UP -> 1
                        Directions.LEFT, Directions.DOWN -> 2
                    }
                    // run to the next corner
                    for (i in 1..l) {
                        p += d.d
                        yield(p)
                    }
                }
            }
        }
    }
}

Answer 4

Your question looks like a question called spiral memory. In that problem, each square on the grid is allocated in a spiral pattern starting from the number 1 which locates at the origin. And then counting up while spiraling outwards. For example:

17  16  15  14  13

18   5   4   3  12

19   6   1   2  11

20   7   8   9  10

21  22  23  ---->

My solution for computing the coordinates of each number following this spiral pattern is posted below:

def spiral_pattern(num):
    x = y = 0
    for _ in range(num-1):
        x, y = find_next(x, y)
    yield (x, y)


def find_next(x, y):
    """find the coordinates of the next number"""
    if x == 0 and y == 0:
        return 1, 0

    if abs(x) == abs(y):
        if x > 0 and y > 0:
            x, y = left(x, y)
        elif x < 0 and y > 0:
            x, y = down(x, y)
        elif x < 0 and y < 0:
            x, y = right(x, y)
        elif x > 0 and y < 0:
            x, y = x+1, y
    else:
        if x > y and abs(x) > abs(y):
            x, y = up(x, y)
        elif x < y and abs(x) < abs(y):
            x, y = left(x, y)
        elif x < y and abs(x) > abs(y):
            x, y = down(x, y)
        elif x > y and abs(x) < abs(y):
            x, y = right(x, y)

    return x, y

def up(x, y):
    return x, y+1


def down(x, y):
    return x, y-1


def left(x, y):
    return x-1, y


def right(x, y):
    return x+1, y

Answer 5

This is a Python/numpy solution which fills any rectangle with spiral. It solves slightly different problem than the original question but that is what I needed.

import numpy as np
import matplotlib.pyplot as plt

def spiral(m, n):
    M = np.zeros([m, n], dtype=int)
    i, j = 0, 0 # location of "turtle"
    di, dj = 0, 1 # direction of movement
    h = (np.min([m,n]))/2
    for ii in range(m * n):
        M[i, j] = ii
        if (i < h and (i == j+1 or i+1 == n-j)) or (i >= m-h and (m-i == n-j or m-i == j+1)):
            di, dj = dj, -di # turn clockwise
        i, j = i + di, j + dj
    return M

plt.imshow(spiral(16, 24))

Answer 6

Here's a solution in Python 3 for printing consecutive integers in a spiral clockwise and counterclockwise.

import math

def sp(n): # spiral clockwise
    a=[[0 for x in range(n)] for y in range(n)]
    last=1
    for k in range(n//2+1):
      for j in range(k,n-k):
          a[k][j]=last
          last+=1
      for i in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for j in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for i in range(n-k-2,k,-1):
          a[i][j]=last
          last+=1

    s=int(math.log(n*n,10))+2 # compute size of cell for printing
    form="{:"+str(s)+"}"
    for i in range(n):
        for j in range(n):
            print(form.format(a[i][j]),end="")
        print("")

sp(3)
# 1 2 3
# 8 9 4
# 7 6 5

sp(4)
#  1  2  3  4
# 12 13 14  5
# 11 16 15  6
# 10  9  8  7

def sp_cc(n): # counterclockwise
    a=[[0 for x in range(n)] for y in range(n)]
    last=1
    for k in range(n//2+1):
      for j in range(n-k-1,k-1,-1):
          a[n-k-1][j]=last
          last+=1
      for i in range(n-k-2,k-1,-1):
          a[i][j]=last
          last+=1
      for j in range(k+1,n-k):
          a[i][j]=last
          last+=1
      for i in range(k+1,n-k-1):
          a[i][j]=last
          last+=1

    s=int(math.log(n*n,10))+2 # compute size of cell for printing
    form="{:"+str(s)+"}"
    for i in range(n):
        for j in range(n):
            print(form.format(a[i][j]),end="")
        print("")

sp_cc(5)
#  9 10 11 12 13
#  8 21 22 23 14
#  7 20 25 24 15
#  6 19 18 17 16
#  5  4  3  2  1

Explanation

A spiral is made of concentric squares, for instance a 5x5 square with clockwise rotation looks like this:

 5x5        3x3      1x1

>>>>>
^   v       >>>
^   v   +   ^ v   +   >
^   v       <<<
<<<<v

(>>>>> means "go 5 times right" or increase column index 5 times, v means down or increase row index, etc.)

All squares are the same up to their size, I looped over the concentric squares.

For each square the code has four loops (one for each side), in each loop we increase or decrease the columns or row index. If i is the row index and j the column index then a 5x5 square can be constructed by: - incrementing j from 0 to 4 (5 times) - incrementing i from 1 to 4 (4 times) - decrementing j from 3 to 0 (4 times) - decrementing i from 3 to 1 (3 times)

For the next squares (3x3 and 1x1) we do the same but shift the initial and final indices appropriately. I used an index k for each concentric square, there are n//2 + 1 concentric squares.

Finally, some math for pretty-printing.

To print the indexes:

def spi_cc(n): # counter-clockwise
    a=[[0 for x in range(n)] for y in range(n)]
    ind=[]
    last=n*n
    for k in range(n//2+1):
      for j in range(n-k-1,k-1,-1):
          ind.append((n-k-1,j))
      for i in range(n-k-2,k-1,-1):
          ind.append((i,j))
      for j in range(k+1,n-k):
          ind.append((i,j))
      for i in range(k+1,n-k-1):
          ind.append((i,j))

    print(ind)

spi_cc(5)

Answer 7

This is my approach for a square spiral in c#, i made this some time ago, i just thought i could add it, since it's different from all the others, not the best, but just a different way, i am sure it can be adapted for a non-square too.

This approach i take the max number of steps in, instead of the max vector tho.

The main thing about this approach is the corners, there's some adjustments for the first step and the "progress" step needed to go out of the "corner" in the right bottom corner.

private void Spiral(int sequence)
{
    const int x = 0;
    const int y = 1;
    int[,] matrix = new int[2, sequence];
    int dirX, dirY, prevX, prevY, curr;
    dirX = dirY = prevX = prevY = curr = default(int);

    do
    {
        if (curr > 0)
        {
            prevX = matrix[x, curr - 1];
            prevY = matrix[y, curr - 1];
        }

        //Change direction based on the corner.
        if (Math.Abs(prevX) == Math.Abs(prevY) && curr > 0)
        {
            dirX = dirY = 0;

            if (prevY > 0 && prevX > 0)
                dirX = -1;
            else if (prevY > 0 && prevX < 0)
                dirY = -1;
            else if (prevY < 0 && prevX < 0)
                dirX = 1;
            else if (prevY < 0 && prevX > 0) //Move forward
                dirX = 1;
            else if (prevY == 0 && prevX == 0) //For the first step.
                dirX = 1;
        }
        else if (prevY < 0 && prevX > 0 && (Math.Abs(matrix[x, curr - 2]) == Math.Abs(matrix[y, curr - 2]))) //Move forward
        {
            dirX = 0;
            dirY = 1;
        }
        else if (prevX == 1 && prevY == 0) //For the second step.
        {
            dirY = 1;
            dirX = 0;
        }

        matrix[x, curr] = prevX + dirX;
        matrix[y, curr] = prevY + dirY;

        System.Console.Write($"({matrix[x, curr]},{matrix[y, curr]}) ");

    } while (++curr < sequence);
}

Answer 8

Here's an answer in Julia: my approach is to assign the points in concentric squares ('spirals') around the origin (0,0), where each square has side length m = 2n + 1, to produce an ordered dictionary with location numbers (starting from 1 for the origin) as keys and the corresponding coordinate as value.

Since the maximum location per spiral is at (n,-n), the rest of the points can be found by simply working backward from this point, i.e. from the bottom right corner by m-1 units, then repeating for the perpendicular 3 segments of m-1 units.

This process is written in reverse order below, corresponding to how the spiral proceeds rather than this reverse counting process, i.e. the ra [right ascending] segment is decremented by 3(m+1), then la [left ascending] by 2(m+1), and so on - hopefully this is self-explanatory.

import DataStructures: OrderedDict, merge

function spiral(loc::Int)
    s = sqrt(loc-1) |> floor |> Int
    if s % 2 == 0
        s -= 1
    end
    s = (s+1)/2 |> Int
    return s
end

function perimeter(n::Int)
    n > 0 || return OrderedDict([1,[0,0]])
    m = 2n + 1 # width/height of the spiral [square] indexed by n
    # loc_max = m^2
    # loc_min = (2n-1)^2 + 1
    ra = [[m^2-(y+3m-3), [n,n-y]] for y in (m-2):-1:0]
    la = [[m^2-(y+2m-2), [y-n,n]] for y in (m-2):-1:0]
    ld = [[m^2-(y+m-1), [-n,y-n]] for y in (m-2):-1:0]
    rd = [[m^2-y, [n-y,-n]] for y in (m-2):-1:0]
    return OrderedDict(vcat(ra,la,ld,rd))
end

function walk(n)
    cds = OrderedDict(1 => [0,0])
    n > 0 || return cds
    for i in 1:n
        cds = merge(cds, perimeter(i))
    end
    return cds
end

So for your first example, plugging m = 3 into the equation to find n gives n = (5-1)/2 = 2, and walk(2) gives an ordered dictionary of locations to coordinates, which you can turn into just an array of coordinates by accessing the dictionary's vals field:

walk(2)
DataStructures.OrderedDict{Any,Any} with 25 entries:
  1  => [0,0]
  2  => [1,0]
  3  => [1,1]
  4  => [0,1]
  ⋮  => ⋮

[(co[1],co[2]) for co in walk(2).vals]
25-element Array{Tuple{Int64,Int64},1}:
 (0,0)  
 (1,0)  
 ⋮       
 (1,-2) 
 (2,-2)

Note that for some functions [e.g. norm] it can be preferable to leave the coordinates in arrays rather than Tuple{Int,Int}, but here I change them into tuples—(x,y)—as requested, using list comprehension.

The context for "supporting" a non-square matrix isn't specified (note that this solution still calculates the off-grid values), but if you want to filter to only the range x by y (here for x=5,y=3) after calculating the full spiral then intersect this matrix against the values from walk.

grid = [[x,y] for x in -2:2, y in -1:1]
5×3 Array{Array{Int64,1},2}:
 [-2,-1]  [-2,0]  [-2,1]
   ⋮       ⋮       ⋮ 
 [2,-1]   [2,0]   [2,1]

[(co[1],co[2]) for co in intersect(walk(2).vals, grid)]
15-element Array{Tuple{Int64,Int64},1}:
 (0,0)  
 (1,0)  
 ⋮ 
 (-2,0) 
 (-2,-1)

Answer 9

Davidont's excellent solution in VB.Net

    Public Function Spiral(n As Integer) As RowCol
    ' given n an index in the squared spiral
    ' p the sum of point in inner square
    ' a the position on the current square
    ' n = p + a
    ' starts with row 0 col -1
    Dim r As Integer = CInt(Math.Floor((Math.Sqrt(n + 1) - 1) / 2) + 1)

    ' compute radius : inverse arithmetic sum of 8+16+24+...=
    Dim p As Integer = (8 * r * (r - 1)) \ 2
    ' compute total point on radius -1 : arithmetic sum of 8+16+24+...

    Dim en As Integer = r * 2
    ' points by face

    Dim a As Integer = (1 + n - p) Mod (r * 8)
    ' compute the position and shift it so the first is (-r,-r) but (-r+1,-r)
    ' so square can connect

    Dim row As Integer
    Dim col As Integer

    Select Case Math.Floor(a \ (r * 2))
        ' find the face : 0 top, 1 right, 2, bottom, 3 left
        Case 0
            row = a - r
            col = -r
        Case 1
            row = r
            col = (a Mod en) - r
        Case 2
            row = r - (a Mod en)
            col = r
        Case 3
            row = -r
            col = r - (a Mod en)
    End Select

    Return New RowCol(row, col)
End Function

Answer 10

Here's a JavaScript (ES6) iterative solution to this problem:

let spiralMatrix = (x, y, step, count) => {
    let distance = 0;
    let range = 1;
    let direction = 'up';

    for ( let i = 0; i < count; i++ ) {
        console.log('x: '+x+', y: '+y);
        distance++;
        switch ( direction ) {
            case 'up':
                y += step;
                if ( distance >= range ) {
                    direction = 'right';
                    distance = 0;
                }
                break;
            case 'right':
                x += step;
                if ( distance >= range ) {
                    direction = 'bottom';
                    distance = 0;
                    range += 1;
                }
                break;
            case 'bottom':
                y -= step;
                if ( distance >= range ) {
                    direction = 'left';
                    distance = 0;
                }
                break;
            case 'left':
                x -= step;
                if ( distance >= range ) {
                    direction = 'up';
                    distance = 0;
                    range += 1;
                }
                break;
            default:
                break;
        }
    }
}

Here's how to use it:

spiralMatrix(0, 0, 1, 100);

This will create an outward spiral, starting at coordinates (x = 0, y = 0) with step of 1 and a total number of items equals to 100. The implementation always starts the movement in the following order - up, right, bottom, left.

Please, note that this implementation creates square matrices.

Answer 11

TDD, in Java.

SpiralTest.java:

import java.awt.Point;
import java.util.List;

import junit.framework.TestCase;

public class SpiralTest extends TestCase {

    public void test3x3() throws Exception {
        assertEquals("(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1)", strung(new Spiral(3, 3).spiral()));
    }

    public void test5x3() throws Exception {
        assertEquals("(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)",
                strung(new Spiral(5, 3).spiral()));
    }

    private String strung(List<Point> points) {
        StringBuffer sb = new StringBuffer();
        for (Point point : points)
            sb.append(strung(point));
        return sb.toString().trim();
    }

    private String strung(Point point) {
        return String.format("(%s, %s) ", point.x, point.y);
    }

}

Spiral.java:

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class Spiral {
    private enum Direction {
    E(1, 0) {Direction next() {return N;}},
    N(0, 1) {Direction next() {return W;}},
    W(-1, 0) {Direction next() {return S;}},
    S(0, -1) {Direction next() {return E;}},;

        private int dx;
        private int dy;

        Point advance(Point point) {
            return new Point(point.x + dx, point.y + dy);
        }

        abstract Direction next();

        Direction(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }
    };
    private final static Point ORIGIN = new Point(0, 0);
    private final int   width;
    private final int   height;
    private Point       point;
    private Direction   direction   = Direction.E;
    private List<Point> list = new ArrayList<Point>();

    public Spiral(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public List<Point> spiral() {
        point = ORIGIN;
        int steps = 1;
        while (list.size() < width * height) {
            advance(steps);
            advance(steps);
            steps++;
        }
        return list;
    }

    private void advance(int n) {
        for (int i = 0; i < n; ++i) {
            if (inBounds(point))
                list.add(point);
            point = direction.advance(point);
        }
        direction = direction.next();
    }

    private boolean inBounds(Point p) {
        return between(-width / 2, width / 2, p.x) && between(-height / 2, height / 2, p.y);
    }

    private static boolean between(int low, int high, int n) {
        return low <= n && n <= high;
    }
}

Answer 12

Here is my solution (In Ruby)

def spiral(xDim, yDim)
   sx = xDim / 2
   sy = yDim / 2

   cx = cy = 0
   direction = distance = 1

   yield(cx,cy)
   while(cx.abs <= sx || cy.abs <= sy)
      distance.times { cx += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance.times { cy += direction; yield(cx,cy) if(cx.abs <= sx && cy.abs <= sy); } 
      distance += 1
      direction *= -1
   end
end

spiral(5,3) { |x,y|
   print "(#{x},#{y}),"
}

Answer 13

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 14

Here's a O(1) solution to find the position in a squared spiral : Fiddle

function spiral(n) {
    // given n an index in the squared spiral
    // p the sum of point in inner square
    // a the position on the current square
    // n = p + a

    var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    var p = (8 * r * (r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    var en = r * 2;
    // points by face

    var a = (1 + n - p) % (r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    var pos = [0, 0, r];
    switch (Math.floor(a / (r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            {
                pos[0] = a - r;
                pos[1] = -r;
            }
            break;
        case 1:
            {
                pos[0] = r;
                pos[1] = (a % en) - r;

            }
            break;
        case 2:
            {
                pos[0] = r - (a % en);
                pos[1] = r;
            }
            break;
        case 3:
            {
                pos[0] = -r;
                pos[1] = r - (a % en);
            }
            break;
    }
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos);
    return pos;
}

Answer 15

I love python's generators.

def spiral(N, M):
    x,y = 0,0   
    dx, dy = 0, -1

    for dumb in xrange(N*M):
        if abs(x) == abs(y) and [dx,dy] != [1,0] or x>0 and y == 1-x:  
            dx, dy = -dy, dx            # corner, change direction

        if abs(x)>N/2 or abs(y)>M/2:    # non-square
            dx, dy = -dy, dx            # change direction
            x, y = -y+dx, x+dy          # jump

        yield x, y
        x, y = x+dx, y+dy

Testing with:

print 'Spiral 3x3:'
for a,b in spiral(3,3):
    print (a,b),

print '\n\nSpiral 5x3:'
for a,b in spiral(5,3):
    print (a,b),

You get:

Spiral 3x3:
(0, 0) (1, 0) (1, 1) (0, 1) (-1, 1) (-1, 0) (-1, -1) (0, -1) (1, -1) 

Spiral 5x3:
(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 16

C++ anyone? Quick translation from python, posted for completeness

void Spiral( int X, int Y){
    int x,y,dx,dy;
    x = y = dx =0;
    dy = -1;
    int t = std::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)){
            // 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 17

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 18

Python looping clockwise spiral code using Can Berk Güder answer.

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 19

I am sharing this code which I designed for a different purpose; it is about finding the Column number "X", and the row number "Y" of array element @ spiral index "index". This function takes the width "w" and height "h" of the matrix, and the required "index". Of course, this function can be used to produce the same required output. I think it is the fastest possible method (as it jumps over cells instead of scanning them).

    rec BuildSpiralIndex(long w, long h, long index = -1)
    {  
        long count = 0 , x = -1,  y = -1, dir = 1, phase=0, pos = 0,                            length = 0, totallength = 0;
        bool isVertical = false;
        if(index>=(w*h)) return null;

        do 
        {                
            isVertical = (count % 2) != 0;
            length = (isVertical ? h : w) - count/2 - count%2 ;
            totallength += length;
            count++;
        } while(totallength<index);

        count--; w--; h--;
        phase = (count / 4); pos = (count%4);
        x = (pos > 1 ? phase : w - phase);
        y = ((pos == 1 || pos == 2) ? h - phase : phase) + (1 * (pos == 3 ? 1 : 0));
        dir = pos > 1 ? -1 : 1;
        if (isVertical) y -= (totallength - index - 1) * dir;
        else x -= (totallength - index -1) * dir;
        return new rec { X = x, Y = y };
    }

Answer 20

C# version, handles non-square sizes as well.

private static Point[] TraverseSpiral(int width, int height) {
    int numElements = width * height + 1;
    Point[] points = new Point[numElements];

    int x = 0;
    int y = 0;
    int dx = 1;
    int dy = 0;
    int xLimit = width - 0;
    int yLimit = height - 1;
    int counter = 0;

    int currentLength = 1;
    while (counter < numElements) {
        points[counter] = new Point(x, y);

        x += dx;
        y += dy;

        currentLength++;
        if (dx > 0) {
            if (currentLength >= xLimit) {
                dx = 0;
                dy = 1;
                xLimit--;
                currentLength = 0;
            }
        } else if (dy > 0) {
            if (currentLength >= yLimit) {
                dx = -1;
                dy = 0;
                yLimit--;
                currentLength = 0;
            }
        } else if (dx < 0) {
            if (currentLength >= xLimit) {
                dx = 0;
                dy = -1;
                xLimit--;
                currentLength = 0;
            }
        } else if (dy < 0) {
            if (currentLength >= yLimit) {
                dx = 1;
                dy = 0;
                yLimit--;
                currentLength = 0;
            }
        }

        counter++;
    }

    Array.Reverse(points);
    return points;
}

Answer 21

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);

Answer 22

I have an open source library, pixelscan, that is a python library that provides functions to scan pixels on a grid in a variety of spatial patterns. Spatial patterns included are circular, rings, grids, snakes, and random walks. There are also various transformations (e.g., clip, swap, rotate, translate). The original OP problem can be solved as follows

for x, y in clip(swap(ringscan(0, 0, 0, 2)), miny=-1, maxy=1):
    print x, y

which yields the points

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

The libraries generators and transformations can be chained to change the points in a wide variety of orders and spatial patterns.

Answer 23

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 24

I made this one with a friend that adjusts the spiral to the canvas aspect ratio on Javascript. Best solution I got for a image evolution pixel by pixel, filling the entire image.

Hope it helps some one.

var width = 150;
var height = 50;

var x = -(width - height)/2;
var y = 0;
var dx = 1;
var dy = 0;
var x_limit = (width - height)/2;
var y_limit = 0;
var counter = 0;

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext('2d');

setInterval(function(){
   if ((-width/2 < x && x <= width/2)  && (-height/2 < y && y <= height/2)) {
       console.log("[ " + x + " , " +  y + " ]");
       ctx.fillStyle = "#FF0000";
       ctx.fillRect(width/2 + x, height/2 - y,1,1);
   }
   if( dx > 0 ){//Dir right
       if(x > x_limit){
           dx = 0;
           dy = 1;
       }
   }
   else if( dy > 0 ){ //Dir up
       if(y > y_limit){
           dx = -1;
           dy = 0;
       }
   }
   else if(dx < 0){ //Dir left
       if(x < (-1 * x_limit)){
           dx = 0;
           dy = -1;
       }
   }
   else if(dy < 0) { //Dir down
       if(y < (-1 * y_limit)){
           dx = 1;
           dy = 0;
           x_limit += 1;
           y_limit += 1;
       }
   }
   counter += 1;
   //alert (counter);
   x += dx;
   y += dy;      
}, 1);

You can see it working on http://jsfiddle.net/hitbyatruck/c4Kd6/ . Just be sure to change the width and height of the canvas on the javascript vars and on the attributes on the HTML.

Answer 25

I really like this challenge 1+ for this post. I tried this by Ruby Code :

For 3X3 Square matrix

(0..8).each do |i|
    j = Math.sqrt(i).round
    k = (j ** 2 - i).abs - j
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i)
    puts "(#{p[0]}, #{p[1]}) "
end

Output:

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

---

For 5X3 as you mentioned in image

iter = (0..19).to_enum
while true
    i = iter.next
    j = Math.sqrt(i).round
    k = (j ** 2 - i).abs - j
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i)
    print "(#{p[0]}, #{p[1]}) "
  if i == 11
    5.times {i = iter.next}
  end
end

Output for this:

(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 26

//PHP implementation

function spiral($n) {

    $r = intval((sqrt($n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    $p = (8 * $r * ($r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    $en = $r * 2;
    // points by face

    $a = (1 + $n - $p) % ($r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    $pos = array(0, 0, $r);
    switch (intval($a / ($r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            $pos[0] = $a - $r;
            $pos[1] = -$r;
            break;
        case 1:
            $pos[0] = $r;
            $pos[1] = ($a % $en) - $r;
            break;
        case 2:
            $pos[0] = $r - ($a % $en);
            $pos[1] = $r;
            break;
        case 3:
            $pos[0] = -$r;
            $pos[1] = $r - ($a % $en);
            break;
    }
    return $pos;
}

for ($i = 0; $i < 168; $i++) {

    echo '<pre>';
    print_r(spiral($i));
    echo '</pre>';
}

Answer 27

I recently had a similar challenge where I had to create a 2D array and use a spiral matrix algorithm to sort and print the results. This C# code will work with a N,N 2D array. It is verbose for clarity and can likely be re-factored to fit your needs.

//CREATE A NEW MATRIX OF SIZE 4 ROWS BY 4 COLUMNS - SCALE MATRIX SIZE HERE
SpiralMatrix SM = new SpiralMatrix(4, 4);
string myData = SM.Read();


public class SpiralMatrix
{
    //LETS BUILD A NEW MATRIX EVERY TIME WE INSTANTIATE OUR CLASS
    public SpiralMatrix(int Rows, int Cols)
    {
        Matrix = new String[Rows, Cols];

        int pos = 1;
        for(int r = 0; r<Rows; r++){
            for (int c = 0; c < Cols; c++)
            {
                //POPULATE THE MATRIX WITH THE CORRECT ROW,COL COORDINATE
                Matrix[r, c] = pos.ToString();
                pos++;
            }
        }
    }

    //READ MATRIX
    public string Read()
    {
        int Row = 0;
        int Col = 0;

        string S = "";
        bool isDone = false;

        //CHECK tO SEE IF POSITION ZERO IS AVAILABLE
        if(PosAvailable(Row, Col)){
            S = ConsumePos(Row, Col);
        }


        //START READING SPIRAL
        //THIS BLOCK READS A FULL CYCLE OF RIGHT,DOWN,LEFT,UP EVERY ITERATION
        while(!isDone)
        {
            bool goNext = false;

            //READ ALL RIGHT SPACES ON THIS PATH PROGRESSION
            while (PosAvailable(Row, Col+1))
            {
                //Is ReadRight Avail
                Col++;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL DOWN SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row+1, Col)){
                //Is ReadDown Avail
                Row++;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL LEFT SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row, Col-1)){
                //Is ReadLeft Avail
                Col--;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            //READ ALL UP SPACES ON THIS PATH PROGRESSION
            while(PosAvailable(Row-1, Col)){
                //Is ReadUp Avail
                Row--;
                S += ConsumePos(Row, Col);
                goNext = true;
            }

            if(!goNext){
                //DONE - SET EXIT LOOP FLAG
                isDone = true;
            }
        }

        return S;
    }

    //DETERMINE IF THE POSITION IS AVAILABLE
    public bool PosAvailable(int Row, int Col)
    {
        //MAKE SURE WE ARE WITHIN THE BOUNDS OF THE ARRAY
        if (Row < Matrix.GetLength(0) && Row >= 0
            && Col < Matrix.GetLength(1) && Col >= 0)
        {
            //CHECK COORDINATE VALUE
            if (Matrix[Row, Col] != ConsumeChar)
                return true;
            else
                return false;
        }
        else
        {
            //WE ARE OUT OF BOUNDS
            return false;
        }
    }

    public string ConsumePos(int Row, int Col)
    {
        string n = Matrix[Row, Col];
        Matrix[Row, Col] = ConsumeChar;
        return n;
    }

    public string ConsumeChar = "X";
    public string[,] Matrix;
}

Answer 28

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 29

This is a slightly different version - trying to use recursion and iterators in LUA. At each step the program descends further inside the matrix and loops. I also added an extra flag to spiral clockwise or anticlockwise. The output starts from the bottom right corners and loops recursively towards the center.

local row, col, clockwise

local SpiralGen
SpiralGen = function(loop)  -- Generator of elements in one loop
    local startpos = { x = col - loop, y = row - loop }
    local IteratePosImpl = function() -- This function calculates returns the cur, next position in a loop. If called without check, it loops infinitely

        local nextpos = {x = startpos.x, y = startpos.y}        
        local step = clockwise and {x = 0, y = -1} or { x = -1, y = 0 }

        return function()

            curpos = {x = nextpos.x, y = nextpos.y}
            nextpos.x = nextpos.x + step.x
            nextpos.y = nextpos.y + step.y
            if (((nextpos.x == loop or nextpos.x == col - loop + 1) and step.y == 0) or 
                ((nextpos.y == loop or nextpos.y == row - loop + 1) and step.x == 0)) then --Hit a corner in the loop

                local tempstep = {x = step.x, y = step.y}
                step.x = clockwise and tempstep.y or -tempstep.y
                step.y = clockwise and -tempstep.x or tempstep.x
                -- retract next step with new step
                nextpos.x = curpos.x + step.x 
                nextpos.y = curpos.y + step.y

            end         
            return curpos, nextpos
        end
    end
    local IteratePos = IteratePosImpl() -- make an instance
    local curpos, nextpos = IteratePos()
    while (true) do
        if(nextpos.x == startpos.x and nextpos.y == startpos.y) then            
            coroutine.yield(curpos)
            SpiralGen(loop+1) -- Go one step inner, since we're done with this loop
            break -- done with inner loop, get out
        else
            if(curpos.x < loop + 1 or curpos.x > col - loop or curpos.y < loop + 1 or curpos.y > row - loop) then
                break -- done with all elemnts, no place to loop further, break out of recursion
            else
                local curposL = {x = curpos.x, y = curpos.y}
                curpos, nextpos = IteratePos()
                coroutine.yield(curposL)
            end
        end     
    end 
end


local Spiral = function(rowP, colP, clockwiseP)
    row = rowP
    col = colP
    clockwise = clockwiseP
    return coroutine.wrap(function() SpiralGen(0) end) -- make a coroutine that returns all the values as an iterator
end


--test
for pos in Spiral(10,2,true) do
    print (pos.y, pos.x)
end

for pos in Spiral(10,9,false) do
    print (pos.y, pos.x)
end

Answer 30

This is my very very bad solution, made from bare minimum knowledge of Java. Here I have to place units on a field in a spiral. Units cannot be placed on top of other units or on mountains or in the ocean.

To be clear. This is not a good solution. This is a very bad solution added for the fun of other people to laugh at how bad it can be done

private void unitPlacementAlgorithm(Position p, Unit u){
    int i = p.getRow();
    int j = p.getColumn();

    int iCounter = 1;
    int jCounter = 0;

    if (getUnitAt(p) == null) {
            unitMap.put(p, u);
    } else {
        iWhileLoop(i, j, iCounter, jCounter, -1, u);
    }

}

private void iWhileLoop(int i, int j, int iCounter, int jCounter, int fortegn, Unit u){
    if(iCounter == 3) {
        for(int k = 0; k < 3; k++) {
            if(k == 2) { //This was added to make the looping stop after 9 units
                System.out.println("There is no more room around the city");
                return; 
            }
            i--;

            if (getUnitAt(new Position(i, j)) == null 
                && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
                && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                    unitMap.put(new Position(i, j), u);
                    return;
            }
            iCounter--;
        }
    }

    while (iCounter > 0) {
        if (fortegn > 0) {
            i++;
        } else {
            i--;
        }

        if (getUnitAt(new Position(i, j)) == null 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                unitMap.put(new Position(i, j), u);
                return;
        }
        iCounter--;
        jCounter++;
    }
    fortegn *= -1;
    jWhileLoop(i, j, iCounter, jCounter, fortegn, u);
}

private void jWhileLoop(int i, int j, int iCounter, int jCounter,
        int fortegn, Unit u) {
    while (jCounter > 0) {
        if (fortegn > 0) {
            j++;
        } else {
            j--;
        }

        if (getUnitAt(new Position(i, j)) == null 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.OCEANS)) 
            && !(getTileAt(new Position(i, j)).getTypeString().equals(GameConstants.MOUNTAINS))) {
                unitMap.put(new Position(i, j), u);
                return;

        }
        jCounter--;
        iCounter++;
        if (jCounter == 0) {
            iCounter++;
        }

    }
    iWhileLoop(i, j, iCounter, jCounter, fortegn, u);
}

Cudos to anyone who can actually read this

Bonus question: What is the running time of this "algorithm"? :P