views:

1253

answers:

8
+9  A: 

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
Can Berk Güder
This is the best way of writing it, as far as I can see. The only possible improvement would be to make it O(MN) instead of O(max(M,N)^2) by directly skipping past those (x,y) that are not going to be printed, but that will make the code a bit more ugly.
ShreevatsaR
I'm optimizing my solution and it's pretty close to what you've already got. This is a pretty good solution I think. Besides ShreevatsaR's suggestion, and stuff like not calculating x/2 and y/2 each iteration, there's not too much to improve on except style.
Triptych
+2  A: 

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}),"
}
Starkii
Still O(max(n,m)^2), but nice style.
Triptych
direction=-direction instead of direction*=-1? if you were golfing d=-d is shorter than d*=-1 too
gnibbler
+1  A: 

Haskell, take your pick:

spiral x y = (0, 0) : concatMap ring [1 .. max x' y'] where
    ring n | n > x' = left x' n  ++ right x' (-n)
    ring n | n > y' = up   n  y' ++ down (-n) y'
    ring n          = up n n ++ left n n ++ down n n ++ right n n
    up    x y = [(x, n) | n <- [1-y .. y]]; down = (.) reverse . up
    right x y = [(n, y) | n <- [1-x .. x]]; left = (.) reverse . right
    (x', y') = (x `div` 2, y `div` 2)

spiral x y = filter (\(x',y') -> 2*abs x' <= x && 2*abs y' <= y) .
             scanl (\(a,b) (c,d) -> (a+c,b+d)) (0,0) $
             concat [ (:) (1,0) . tail 
                    $ concatMap (replicate n) [(0,1),(-1,0),(0,-1),(1,0)]
                    | n <- [2,4..max x y] ]
ephemient
Please don't take this as a rant or a troll's comment, but GOD is haskell ugly!
Petruza
I could not agree with the above comment more.
Sneakyness
This Haskell looks very trendy to me.
Kinopiko
A: 

I know, Python looks nice and neat for this.

Can someone please put this in C code ? (assuming that each of the "cell" in the array stores a coordinate as mentioned)

(BTW, is there an easy way to initialize the "cells" coordinates without hardcoding them ?)

It would be nice to see how to loop through these in C for-loops.

Say that you still want to start the spiral from the center of the MxN array. (where m/2 and n/2 is the center)

Thanks!

See Tom's C++ solution http://stackoverflow.com/questions/398299/looping-in-a-spiral/1555236#1555236 if you rewrite the std::max it will be C
gnibbler
+1  A: 

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;
    }
}
Carl Manaster
I think this is not quite 'code golf' :)
leppie
@leppie: Maybe not - certainly not short enough - but I think it's a good demonstration of TDD, and reasonably clean, easy-to-understand, correct code. I'll leave it in.
Carl Manaster
+4  A: 

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)
Andrea Ambu
A: 

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/2) && (-Y/2 < 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;
    }
}
Tom J Nowell
you can also use s and ds like I do to detect the corners which gets rid of the huge if condition
gnibbler
A: 

This is based on your own solution, but we can be smarter about finding the corners. This makes it easier to see how you might skip over the areas outside if M and N are very different.

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

and a generator based solution that is better than O(max(n,m)^2), It is O(nm+abs(n-m)^2) because it skips whole strips if they are not part of the solution.

def spiral(X,Y):
X = X+1>>1
Y = Y+1>>1
x = y = 0
d = side = 1
while x<X or y<Y:
    if abs(y)<Y:
        for x in range(x, x+side, d):
            if abs(x)<X: yield x,y
        x += d
    else:
        x += side
    if abs(x)<X:
        for y in range(y, y+side, d):
            if abs(y)<Y: yield x,y
        y += d
    else:
        y += side
    d =-d
    side = d-side
gnibbler