In a far-off kingdom, a chess queen takes a daily walk across a spiral path, numbered from 1 to n, not caring to follow the spiral itself, but simply making queen's moves as she would on a chessboard. The queen is beloved by her subjects, and they make a note of every square she visits on her path. Given that the queen can start her walk on any square and ends it on any square, what is the shortest queen's walk that she can take?

The challenge

Given a spiral of integers on a rectangular grid, write a function that returns one of the shortest possible paths (counted by number of cells travelled) between two numbers on this spiral grid using a chess queen's moves.

For example, from 16 to 25:

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

Some possible paths include 16, 4, 2, 10, 25 and 16, 5, 1, 9, 25.

Rules

  • The input will be any two positive integers.
  • The output will be a path of integers (including both endpoints) across the spiral using only orthogonal and diagonal moves.
  • The length of a path is counted by the number of cells travelled.
  • Your answer may be a program or a function.
  • This is code golf, so the smallest number of bytes wins.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Test cases

>>> queen_spiral(4, 5)
4, 5
>>> queen_spiral(13, 20)
13, 3, 1, 7, 20
>>> queen_spiral(14, 14)
14
>>> queen_spiral(10, 3)
10, 11, 3
>>> queen_spiral(16, 25)
16, 4, 2, 10, 25
>>> queen_spiral(80, 1)
80, 48, 24, 8, 1
  • Related. – Leaky Nun Aug 4 '16 at 5:48
  • 5
    You might want to mention that you're looking for the shortest path by number of cells travelled (as opposed to Euclidian distance, say). – Martin Ender Aug 4 '16 at 6:09

Mathematica 615 530 bytes

This constructs a number grid, converts it into a graph, and then finds a shortest path between the two numbers that were input.


UnGolfed

numberSpiral is from Mathworld Prime Spiral. It creates an n by n Ulam Spiral (without highlighting the primes).

findPath converts the number grid into a graph. Edges are valid queen moves on the number grid.


numberSpiral[n_Integer?OddQ]:= 
  Module[{a,i=(n+1)/2,j=(n+1)/2,cnt=1,dir=0,len,parity,vec={{1,0},{0,-1},{-1,0},{0,1}}},a=Table[j+n(i-1),{i,n},{j,n}];Do[Do[Do[a[[j,i]]=cnt++;{i,j}+=vec[[dir+1]],{k,len}];dir=Mod[dir+1,4],{parity,0,1}],{len,n-1}];a];  

findPath[v1_, v2_] := 
  Module[{f, z, k},
    (*f  creates edges between each number and its neighboring squares *)
    f[sp_,n_]:=n<->#&/@(sp[[Sequence@@#]]&/@(Position[sp,n][[1]]/.{r_,c_}:>Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1}, {r+1,c-1}},{x_,y_}/; 0<x<k&&0<y<k]));k=If[EvenQ[
     z=\[LeftCeiling]Sqrt[Sort[{v1, v2}][[-1]]]\[RightCeiling]],z+1,z];
    FindShortestPath[Graph[Sort/@Flatten[f[ns=numberSpiral[k],#]&/@Range[k^2]] //Union],v1,v2]]

Examples

findPath[4,5]
findPath[13,22]
findPath[16,25]
numberSpiral[5]//Grid

{4,5}

{13,3,1,7,22}

{16,4,1,9,25}

grid


The shortest path from 80 to 1 contains 5, not 6, vertices.

findPath[80,1]
numberSpiral[9]//Grid

{80, 48, 24, 8, 1}

eighty one grid


Golfed

u=Module;
w@n_:=u[{a,i=(n+1)/2,j=(n+1)/2,c=1,d=0,l,p,v={{1,0},{0,-1},{-1,0},{0,1}}},
a=Table[j+n(i-1),{i,n},{j,n}];
Do[Do[Do[a[[j,i]]=c++;{i,j}+=v[[d+1]],{k,l}];d=Mod[d+1,4],{p,0,1}],{l,n-1}];a];
h[v1_,v2_]:=u[{f,z},
s_~f~n_:=n<->#&/@(s[[Sequence@@#]]&/@(Position[s,n][[1]]/.{r_,c_}:> 
Cases[{{r-1,c},{r+1,c},{r,c-1},{r,c+1},{r-1,c-1},{r-1,c+1},{r+1,c+1},{r+1,c-1}},{x_,y_}/;0<x<k&&0<y<k]));
k=If[EvenQ[z=\[LeftCeiling]Sqrt[Sort[{v1,v2}][[-1]]]\[RightCeiling]],z+1,z];
FindShortestPath[g=Graph[Sort/@Flatten[f[ns=w@k,#]&/@Union@Range[k^2]]],v1,v2]]

Scala (830 bytes)

Builds the spiral in a square 2D array using four mutually recursive functions. Another recursive search to build the path list.

def P(s:Int,e:Int):List[Int]={
import scala.math._
type G=Array[Array[Int]]
type I=Int
type T=(I,I)
def S(z:I)={def U(g:G,x:I,y:I,c:I,r:I):Unit={for(i<-0 to r.min(y)){g(y-i)(x)=c+i}
if(r<=y)R(g,x,y-r,c+r,r)}
def R(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x+i)=c+i}
D(g,x+r,y,c+r,r+1)}
def D(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y+i)(x)=c+i}
L(g,x,y+r,c+r,r)}
def L(g:G,x:I,y:I,c:I,r:I)={for(i<-0 to r){g(y)(x-i)=c+i}
U(g,x-r,y,c+r,r+1)}
val g=Array.ofDim[I](z,z)
U(g,z/2,z/2,1,1)
g}
def C(n:I,g:G):T={var(x,y)=(0,0)
for(i<-g.indices){val j=g(i).indexOf(n)
if(j>=0){x=j
y=i}}
(x,y)}
def N(n:Int)=if(n==0)0 else if(n<0)-1 else 1
def Q(a:T,b:T):List[T]={val u=N(b._1-a._1)
val v=N(b._2-a._2)
if(u==0&&v==0)b::Nil else a::Q((a._1+u,a._2+v),b)}
val z=ceil(sqrt(max(s,e))).toInt|1
val p=S(z)
Q(C(s,p),C(e,p)).map{case(x,y)=>p(y)(x)}}

Ungolfed

  import scala.math._
  type Grid=Array[Array[Int]]
  def spiral(size: Int) = {
    def up(grid:Grid, x: Int, y: Int, c: Int, r: Int): Unit = {
      for (i <- 0 to r.min(y)) {
        grid(y-i)(x) = c + i
      }
      if (r <= y)
        right(grid,x,y-r,c+r,r)
    }
    def right(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y)(x+i) = c + i
      }
      down(grid,x+r,y,c+r,r+1)
    }
    def down(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y+i)(x) = c + i
      }
      left(grid,x,y+r,c+r,r)
    }
    def left(grid:Grid, x: Int, y: Int, c: Int, r: Int) = {
      for (i <- 0 to r) {
        grid(y)(x-i) = c + i
      }
      up(grid,x-r,y,c+r,r+1)
    }
    val grid = Array.ofDim[Int](size,size)
    up(grid,size/2,size/2,1,1)
    grid
  }
  def findPath(start: Int, end: Int): List[Int] = {
    def findCoords(n: Int, grid: Grid): (Int, Int) = {
      var (x,y)=(0,0)
      for (i <- grid.indices) {
        val j = grid(i).indexOf(n)
        if (j >= 0) {
          x = j
          y = i
        }
      }
      (x,y)
    }
    def sign(n: Int) = if (n == 0) 0 else if (n < 0) -1 else 1
    def path(stc: (Int, Int), enc: (Int, Int)) : List[(Int, Int)] = {
      val dx = sign(enc._1 - stc._1)
      val dy = sign(enc._2 - stc._2)
      if (dx == 0 && dy == 0) {
        enc :: Nil
      } else {
        stc :: path((stc._1 + dx, stc._2 + dy), enc)
      }
    }
    val size = ceil(sqrt(max(start, end))).toInt | 1
    val spir = spiral(size)
    path(findCoords(start, spir),findCoords(end, spir)).
      map { case (x, y) => spir(y)(x) }
  }

Ruby, 262 218 216 bytes

This is a port of my Python answer. Golfing suggestions welcome.

Edit: 45 bytes thanks to Jordan and their suggestions of d=[0]*n=m*m;*e=c=0;*t=a, .rect, 0<=>x and x,y=(e[a]-g=e[b]).rect; t<<d[(g.real+x)*m+g.imag+y]. Another byte from (x+y*1i) to (x+y.i).

->a,b{m=([a,b].max**0.5).to_i+1;d=[0]*n=m*m;*e=c=0;*t=a
n.times{|k|d[c.real*m+c.imag]=k+1;e<<c;c+=1i**((4*k+1)**0.5-1).to_i}
x,y=(e[a]-g=e[b]).rect
(x+=0<=>x;y+=0<=>y;t<<d[(g.real+x)*m+g.imag+y])while(x+y.i).abs>0
t}

Ungolfed:

def q(a,b)
  m = ([a,b].max**0.5).to_i+1
  n = m*m
  d = [0]*n
  c = 0
  *e = c   # same as e=[0]
  *t = a   # same as t=[a]

  (1..n).each do |k|
    d[c.real * m + c.imag] = k+1
    e << c
    c += 1i**((4*k+1)**0.5-1).to_i
  end

  x, y = (e[a] - g=e[b]).rect

  while (x+y.i).abs > 0 do
    if x<0
      x += 1
    elsif x>0
      x += -1
    end

    if y<0
      y += 1
    elsif y>0
      y -= 1
    end

    t << d[(g.real+x)*m+g.imag+y]
  end

  return t
end
  • You should remove the q= from your answer since you're not counting its bytes. c=0;e=[c];t=[a] can be shortened to *e=c=0;*t=a. You can replace z=e[a]-e[b];x,y=z.real,z.imag with x,y=(e[a]-e[b]).rect and x+=x<0?1:x>0?-1:0 with x+=0<=>x (same for y). I think that gets it down to 229 bytes. – Jordan Aug 5 '16 at 17:43
  • If you switch to a 1-dimensional array you can save 6 more bytes. Replace the initialization of d with d=[0]*m*m, then replace d[c.real][c.imag] with d[c.real*m+c.imag] and d[e[b].real+x][e[b].imag+y] with d[(e[b].real+x)*m+e[b].imag+y]. – Jordan Aug 5 '16 at 17:48
  • A 2-byte improvement over my previous comment: t<<d[(e[b].real+x)*m+e[b].imag+y] can be shortened to u,v=e[b].rect;t<<d[(u+x)*m+v+y]. – Jordan Aug 5 '16 at 18:04
  • Two more bytes by changing d=[0]*m*m to d=[0]*n=m*m and (m*m).times to n.times. That's 219. – Jordan Aug 5 '16 at 18:22
  • You can save two additional bytes by changing x,y=(e[a]-e[b]).rect to x,y=(e[a]-g=e[b]).rect, deleting u,v=e[b].rect and changing t<<d[(u+x)*m+v+y] to t<<d[(g.real+x)*g.imag+v+y] (basically reverting my second-to-last comment). – Jordan Aug 5 '16 at 18:31

Python 3, 316 bytes

This answer looks at the coordinates of a and b on the spiral (using complex numbers) and adds the diagonal moves first, then the orthogonal moves.

def q(a,b):
 m=int(max(a,b)**.5)+1;d=[];c=0;e=[c];t=[a]
 for i in range(m):d+=[[0]*m]
 for k in range(m*m):d[int(c.real)][int(c.imag)]=k+1;e+=[c];c+=1j**int((4*k+1)**.5-1)
 z=e[a]-e[b];x,y=int(z.real),int(z.imag)
 while abs(x+y*1j):x+=(x<0)^-(x>0);y+=(y<0)^-(y>0);t+=[d[int(e[b].real)+x][int(e[b].imag)+y]]
 return t

Ungolfed:

def queen_spiral(a,b):
    square_size = int(max(a,b)**.5)+1
    complex_to_spiral = []
    complex = 0
    spiral_to_complex = [c] # add 0 first, so that it's 1-indexed later
    result = [a]

    for i in range(square_size):
        complex_to_spiral.append([0]*square_size) # the rows of the spiral

    for k in range(square_size**2):
        row = int(complex.real)
        column = int(complex.imag)
        complex_to_spiral[row][column] = k+1 # 1-indexing

        spiral_to_complex.append(complex)

        quarter_turns = int((4*k+1)**.5-1)
        complex += 1j**quarter_turns

    z = spiral_to_complex[a] - spiral_to_complex[b]
    v = spiral_to_complex[b]
    x, y = int(z.real), int(z.imag)
    r, s = int(v.real), int(v.imag)

    while abs(x+y*1j):
        if x < 0:
            x += 1
        elif x > 0:
            x += -1
        # else x == 0, do nothing
        if y < 0:
            y += 1
        elif y > 0:
            y += -1

        vertex = complex_to_spiral[r+x][s+y]
        result.append(vertex)
    return result

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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