11
\$\begingroup\$

The Doctor, in trying to escape from the Dalek forces has decided to send them in a spin by traveling in various pockets of space in a spiral motion.

Depending on the nature of the available space-time, The Doctor needs to enter into the TARDIS controls the height and width of the section of space and his entry point with which to begin the spiral.

The section of space can be envisioned as a h x w grid filled with sequential integers from left to right, top to bottom, starting with 1.

The starting position is provided as r c for the row and column... From this the TARDIS's software needs to spit out the ordered list of integers obtained by spiraling outward in an anti-clockwise direction from row r column c, starting upwards...

Your task, as the Doctor's companion is to program the TARDIS to take four numbers, in the format height width row column and have it determine which sector of space the TARDIS needs to travel to match the spiral movement described below...

Input 1

5 5 3 3

(5 x 5 grid, starting at position 3,3)

Output 1

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

Explaining output

Original grid enter image description here

Generated spiral enter image description here

Input 2

2 4 1 2

(2 x 4 grid starting at position 1,2)

Output 2

2 1 5 6 7 3 8 4

Explaining output

Slightly different as spiral now must circle around grid to generate respective output...

Original grid enter image description here

Generated spiral enter image description here

Rules:

  1. This is code-golf, so shortest code length gets the tick of approval.

  2. The above examples must be used to test your code. If it doesn't provide the respective output, there's something wrong...

  3. Both golfed and in-golfed versions of code must be provided in your answer...

Good luck!

\$\endgroup\$
  • \$\begingroup\$ May I point you to draw.io where one can quickly make rather reasonable drawings (you've got excellent legibility with your hand drawn version... just I don't see any red circles). Consider i.stack.imgur.com/xbLSA.png as an example of what could be done. Note that that has the xml embeded in it, so if you go to draw.io you can import from url. \$\endgroup\$ – user12166 May 16 '15 at 3:42
  • \$\begingroup\$ I'll bear that in mind for my next need for a drawing, @MichaelT, thank you... \$\endgroup\$ – WallyWest May 16 '15 at 4:30
  • 1
    \$\begingroup\$ I post an answer with a function returning array as output. Is it acceptable? \$\endgroup\$ – edc65 May 16 '15 at 10:23
  • \$\begingroup\$ @edc65 Mate, you and I go way back here on CG, I'll allow a function of S(h,w,r,c) or the like for this... :) \$\endgroup\$ – WallyWest May 16 '15 at 10:56
3
\$\begingroup\$

JavaScript (ES6) 124 163 177

Edit Totally different way, no need of an array to store visited cells. Using the fact that the side of the spiral increase of 1 after every 2 turns.

// New way
f=(h,w,y,x)=>
  (e=>{
    for(o=[],d=i=t=l=0;l<w*h;i<t?i+=2:[i,d,e]=[1,-e,d,++t])
      o[l]=y*w-w+x,l+=x>0&x<=w&y>0&y<=h,x+=d,y-=e
  })(1)||o


// Golfed
g=(h,w,y,x)=>
  (g=>{
    for(e=n=0;n<h*w;)g[[n%w+1,-~(n/w)]]=++n;
    for(o=[g[[x,y]]],l=d=1;l<n;l+=!!(o[l]=g[[x+=d,y+=e]]))
      g[[x,y]]=0,
      g[[x+e,y-d]]!=0&&([d,e]=[e,-d])
  })([])||o



// Not golfed
u=(h,w,y,x)=>{
  var i,j,dx,dy,kx,ky,o,n,
    g={} // simulate a 2dimensional array using a hashtable with keys in the form 'x,y'

  for(n=i=0; i++<h;) // fill grid (probably better done in a single loop)
    for(j=0; j++<w;)
      g[[j,i]] = ++n;
  o=[g[[x,y]]] // starting point in output
  dx=1, dy=0 // start headed right
  
  for(; !o[w*h-1]; ) // loop until all w*h position are put in output
  {
    g[[x, y]] = 0 // mark current position to avoid reusing
    kx=dy, ky=-dx // try turning left
    if(g[[x+kx, y+ky]] != 0) // check if position marked
    { // found a valid position
      dx=kx, dy=ky // change direction
    }
    x+=dx, y+=dy // move
    k=g[[x, y]] // get current value
    if (k) o.push(k) // put in output list if not 'undefined' (outside grid)
  }
  return o
}

// TEST - In FireFox

out=x=>O.innerHTML+=x+'\n';
[
 [[5,5,3,3],'13 8 7 12 17 18 19 14 9 4 3 2 1 6 11 16 21 22 23 24 25 20 15 10 5'],
 [[2,4,1,2],'2 1 5 6 7 3 8 4']
].forEach(t=>out(t[0] + '\n Result: ' + f(...t[0])+'\n Check:  ' + t[1]))

test=()=>
{
  var r, i=I.value.match(/\d+/g), h=i[0]|0, w=i[1]|0, y=i[2]|0, x=i[3]|0
  if (y>h||x>w) r = 'Invalid input'
  else r = f(h,w,y,x)
  out(i+'\n Reault: ' +r)
}
<pre id=O></pre>
Your test:<input id=I><button onclick="test()">-></button>

\$\endgroup\$
  • \$\begingroup\$ Amazing golfing! From 300 to 163... I take my hat off to you... \$\endgroup\$ – WallyWest May 16 '15 at 18:13
  • 1
    \$\begingroup\$ @WallyWest with that comment you push me to do better. Thnx \$\endgroup\$ – edc65 May 17 '15 at 13:40
  • \$\begingroup\$ Nice! My Python solution was a lot longer but I was like, it is all right, you use a better method. Now you use the same and it it is even shorter... I have some work to do. :) \$\endgroup\$ – randomra May 17 '15 at 14:11
  • \$\begingroup\$ @randomra I'd still love to see it... \$\endgroup\$ – WallyWest Jun 3 '15 at 23:58
2
\$\begingroup\$

Python 3, 191

Probably not a great score, but here it goes:

def f(b,a,d,c):
 p,r,l,s,h=c+1j*d,-1j,1,0,0
 for _ in [0]*((a+b)**2):x,y=p.real,p.imag;0<x<a+1and 0<y<b+1and print(int((y-1)*a+x),end=' ');p+=r;s=(s+1)%l;t=s==0;h=(h+t)%2;l+=h<t;r*=(-1j)**t 

We move along the spiral by increasing side-length after every second turns. If our position is inside the given grid we print its corresponding number.

Variables are:

  • p is complex position
  • x and y are position coordinates
  • r is direction
  • s is position on current side
  • l is current side length
  • h is the parity of the current side's ordinal
\$\endgroup\$

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.