Spiral in the grid

Question

Write a program which enumerates points on a regular grid in the form of a spiral. The output should be the indices of the points (row-major) and the spiral should start at 0 and proceed anti-clockwise.

Here is an illustration of the problem:

Specifications:

• Write a program which accepts two integers and writes the result to standard out.
• Input: width and height of the grid (range is [1,1024])
• Output: indices of grid points in the correct order

Goal:

• Entry with fewest characters wins.
• Would also be interested in elegant entries for "classic" programming languages.

Examples:

• width=3, height=3 => 0 1 2 5 8 7 6 3 4
• width=4, height=3 => 0 1 2 3 7 11 10 9 8 4 5 6

Answer 1

CJam - 18

q~1$*,/{(S*S@zW%}h

Try it at http://cjam.aditsu.net/

The input should contain the 2 numbers separated by space.

Explanation:

q~ reads and evaluates the input
1$* copies the width and multiplies by height
,/ generates the array with all the numbers in order, and splits it in rows
{…}h repeats the block until the condition (at the end of the block) is false
(S*S takes the first row of the grid and adds spaces to separate the numbers
@zW% takes the rest of the grid and rotates it (z = transpose, W% = reverse)
The remaining grid becomes the loop condition; the loop terminates when the grid is empty.

Answer 2

Ruby — 96 81

@Ventero knocks off 15 characters with some splatting combined with a really clever default argument!

g=->a=p,*r{a ?a+g[*r.transpose.reverse]:[]}
f=->w,h{g[*[*0...w*h].each_slice(w)]}

Examples:

f[3,3]  # => [0, 1, 2, 5, 8, 7, 6, 3, 4]
f[4,3]  # => [0, 1, 2, 3, 7, 11, 10, 9, 8, 4, 5, 6]

Here's an ungolfed solution in Ruby using just one method for those who are interested:

def spiral(width, height, matrix = [*[*0...width * height].each_slice(width)])
  matrix.empty? ? [] : matrix.shift + spiral(0, 0, matrix.transpose.reverse)
end

Answer 3

My PHP version. 349 276 characters.

Same as below but I found out something surprising. In PHP, for loops can have multiple expressions in both pre and post iteration. I never knew that and suddenly they are far more powerful/complex than I thought they were. So could not resist rewriting my first attempt to make use of that.

Anyway, new and improved code here - 73 characters shorter than the first:

<?php $a=4;$b=3;$c=-1;$d=$a*$b;$e=$a;$f=($b-1);function c($g,$k){
global $c,$d;for($l=0;$l<$g;$c=$c+$k,++$l,--$d,print $c.' ');}while($d>0)
{$m=1;$g=$e;c($g,$m);--$e;if($f>0){$m=$a;$g=$f;c($g,$m);--$f;if($e>0)
{$m=-1;$g=$e;c($g,$m);--$e;if($f>0){$m=-$a;$g=$f;c($g,$m);--$f;}}}}?>

which can be seen here:

Original attempt below

No where near as cool as the 18 chars of CJam (which I shall be googling about in a minute) but this is the full php program that takes the width and height as the first two parameters.

<?php $a=4;$b=3;$c=-1;$d=$e=0;$f=($b*$a);function calc($g,$h,$j,$k){for($l=$g;
$l<$h;++$l){$k=$k+$j;echo' '.$k;}return($k);}while($f>0){if($d<$a){$c=calc($d,$a,1,$c);
$f=$f-($a-$d);++$e;if($e<$b){$c=calc($e,$b,$a,$c);$f=$f-($b-$e);++$d;
if($d<$a){$c=calc($d,$a,-1,$c);$f=$f-($a-$d);++$e;
if($e<$b){$j=0-$a;$c=calc($e,$b,$j,$c);$f=$f-($b-$e);}}}}++$d;}?>

You can see it in action here: http://codepad.org/qPUWwY2J (above paste has had extra line breaks so it all shows on the page without side scrolling.)

I think this puzzle was a great question and I must admit that starting on 0 caused some issues for me. I have checked lots of different grids and it seems to work well although takes a bit of time to work through large grids.

My answer simply recognizes that moving left and right is adding +1 or -1 to the start number used, and up or down just adds or subtracts the original width. It then simply steps down the height and width counters for each pass. All of the output is in a function that I just send the change, step count and start number to. I reckon I could get a few more characters off by not declaring variables, but not 300 or so.

Great puzzle, had some tricky bits but I enjoyed it, thank you.

Answer 4

Mathematica - 97 characters

w=4;h=3;Flatten@NestList[Reverse@Transpose@Rest@#&,Partition[Range[w h],w],2Min[w,h]-2][[;;,1]]-1

• First generate the grid.
• Iteratively drop the first row and rotate (transpose + reverse) the remaining matrix.
• The number of iterations until we end with 1-dimensional matrix is 2*min(w,h)-2.
• Collect the dropped first rows into an array.
• Subtract 1 because Mathematica starts indices with 1.

Answer 5

JavaScript - 225 Characters

w=8,h=8
{for(a=[0],x=y=b=r=t=l=s=0;a.length<w*h;){if(s==0&&x+r+1==w&&++b+1||s==1&&y+t+1==h&&++r+1||s==2&&x==l&&++t+1||s==3&&y==b&&++l+1)s=(s+1)%4
s==0&&++x+1||s==1&&++y+1||s==2&&--x+1||--y
a.push(x+w*y)}alert(a.join(' '))}

And ungolfed:

w = 8 // width of grid
h = 8 // height of grid
for(a = [0], // array
    x =      // x pos
    y =      // y pos
    b =      // bottom rows done
    r =      // right rows done
    t =      // top rows done
    l =      // left rows done
    s = 0;    // current side 0: b, 1: r, 2: t, 3: l
  a.length < w*h;) {
    if (s==0 && x+r+1==w && ++b+1 ||
        s==1 && y+t+1==h && ++r+1 ||
        s==2 &&     x==l && ++t+1 ||
        s==3 &&     y==b && ++l+1 ){
        s=(s+1)%4
    }

    s==0 && ++x+1 ||
    s==1 && ++y+1 ||
    s==2 && --x+1 ||
            --y

    a.push(x+w*y)
}
alert(a.join(' '))

The code sets the grid size in w and h. It stores current coordinates in x and y. It navigates in direction s, and stores the number of rows already filled on the sides in b, r, t and l.

A demo is at http://jsfiddle.net/L2ReA/