7
\$\begingroup\$

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:

enter image description here

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
\$\endgroup\$
  • \$\begingroup\$ Why [popularity-contest]? This seems like it would be better suited for [code-golf]. \$\endgroup\$ – Doorknob Jul 15 '14 at 20:40
  • \$\begingroup\$ Thank you for your comment. I was not sure about that and edited it accordingly. \$\endgroup\$ – Danvil Jul 15 '14 at 20:41
  • 1
    \$\begingroup\$ related: codegolf.stackexchange.com/questions/769/… (my brain is too tired to figure out if this is only a trivial extension of the other one or not) \$\endgroup\$ – Martin Ender Jul 15 '14 at 20:44
  • \$\begingroup\$ What should we write? A complete program? A function? Assume input as variables? Where should the input come from and output go to? \$\endgroup\$ – Justin Jul 15 '14 at 21:25
  • \$\begingroup\$ Change "Most elegant entry by popularity vote wins", since this is now code-golf no longer popularity-contest \$\endgroup\$ – Digital Trauma Jul 15 '14 at 23:31
7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Amazingly tiny. I would not have thought it possible. \$\endgroup\$ – AndoDaan Jul 15 '14 at 23:22
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Glad you like it! \$\endgroup\$ – Danvil Jul 16 '14 at 9:19
  • \$\begingroup\$ This is one of the things I like best about code-golf - it exposes you to powerful features you don't know of languages you otherwise know well \$\endgroup\$ – Digital Trauma Jul 16 '14 at 14:32
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ +very clever use of NestList \$\endgroup\$ – DavidC Jul 17 '14 at 12:32
1
\$\begingroup\$

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/

\$\endgroup\$
  • \$\begingroup\$ You can easily save a few characters by writing x=y=b=r=t=l=s=0 instead of x=0,y=0,b=0,r=0,t=0,l=0,s=0. \$\endgroup\$ – darthmaim Jul 16 '14 at 20:04
  • \$\begingroup\$ for(x=y=b=r=t=l=s=0;a.length<w*h;) is even shorter, combining the loop with the assignment. \$\endgroup\$ – darthmaim Jul 16 '14 at 20:07
  • \$\begingroup\$ I don't think I see the function definition anywhere. \$\endgroup\$ – seequ Jul 16 '14 at 20:39
  • \$\begingroup\$ @TheRare The function encloses all the code, I did not include it in my code. \$\endgroup\$ – Charlie Harding Jul 16 '14 at 20:42
  • \$\begingroup\$ Usually you should include the function definition too, if one should be there. \$\endgroup\$ – seequ Jul 16 '14 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.