14
$\begingroup$

I don't know exactly how to describe it, but in a programmatic way I want to spiral outward from coordinates 0,0 to infinity (for practical purposes, though really I only need to go to about +/-100,000:+/-100,000)

So if this is my grid:

[-1, 1][ 0, 1][ 1, 1][ 2, 1]
[-1, 0][ 0, 0][ 1, 0][ 2, 0]
[-1,-1][ 0,-1][ 1,-1][ 2,-1]

I want to spiral in an order sort of like:

[7][8][9][10]
[6][1][2][11]
[5][4][3][12]
etc...

Is there a formula or method of doing this?

$\endgroup$
12
$\begingroup$

Here’s a recipe for finding the coordinates of your position after $n$ steps along the spiral.

It’s simpler to number the positions on the spiral starting at $0$: position $0$ is $\langle 0,0\rangle$, the origin, position $1$ is $\langle 1,0\rangle$, position $2$ is $\langle 1,-1\rangle$, and so on. Using $R,D,L$, and $U$ to indicate steps Right, Down, Left, and Up, respectively, we see the following pattern:

$$RD\,|LLUU\,\|\,RRRDDD\,|LLLLUUUU\,\|\,RRRRRDDDDD\,|LLLLLLUUUUUU\;\|\dots\;,$$

or with exponents to denote repetition, $R^1D^1|L^2U^2\|R^3D^3|L^4U^4\|R^5D^5|L^6U^6\|\dots\;$. I’ll call each $RDLU$ group a block; the first block is the initial $RDLLUU$, and I’ve displayed the first three full blocks above.

Clearly the first $m$ blocks comprise a total of $2\sum_{k=1}^mk=m(m+1)$ steps. It’s also not hard to see that the $k$-th block is $R^{2k+1}D^{2k+1}L^{2k+2}U^{2k+2}$, so that the net effect of the block is to move you one step up and to the left. Since the starting position after $0$ blocks is $\langle 0,0\rangle$, the starting position after $k$ full blocks is $\langle -k,k\rangle$.

Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<n\le(2k+2)(2k+3)\;;$$ at this point you’ve gone through $k$ blocks plus an additional $n-2k(2k+1)$ steps. After some straightforward but slightly tedious algebra we find that you’re at

$$\begin{cases} \langle n-4k^2-3k,k\rangle,&\text{if }2k(2k+1)<n\le(2k+1)^2\\ \langle k+1,4k^2+5k+1-n\rangle,&\text{if }(2k+1)^2<n\le 2(k+1)(2k+1)\\ \langle 4k^2+7k+3-n,-k-1\rangle,&\text{if }2(k+1)(2k+1)<n\le4(k+1)^2\\ \langle -k-1,n-4k^2-9k-5\rangle,&\text{if }4(k+1)^2<n\le2(k+1)(2k+3)\;. \end{cases}$$

To find $k$ easily, let $m=\lfloor\sqrt n\rfloor$. If $m$ is odd, $k=\frac12(m-1)$. If $m$ is even, and $n\ge m(m+1)$, then $k=\frac{m}2$; otherwise, $k=\frac{m}2-1$.

$\endgroup$
  • 1
    $\begingroup$ Yikes that is a bit more complex than I expected, hopefully I can put it to use! $\endgroup$ – Jane Panda Jun 26 '12 at 2:40
  • $\begingroup$ Is there a generalization/extension of this to an $d$-dimensional outward spiral? $\endgroup$ – phdmba7of12 Oct 16 '17 at 14:10
  • $\begingroup$ @phdmba7of12 It doesn't seem obvious how this spiral would go. Could you provide an example for a 3x3x3 cube? $\endgroup$ – Kaligule Nov 29 '18 at 21:36
  • $\begingroup$ @Kaligule ... i agree. not at all obvious. thus my question $\endgroup$ – phdmba7of12 Nov 30 '18 at 19:14
12
$\begingroup$

Here is some code that finds the $n$-th point in the spiral. Unfortunately it spirals the other way but perhaps it helps anyway.

function spiral(n)
        k=ceil((sqrt(n)-1)/2)
        t=2*k+1
        m=t^2 
        t=t-1
        if n>=m-t then return k-(m-n),-k        else m=m-t end
        if n>=m-t then return -k,-k+(m-n)       else m=m-t end
        if n>=m-t then return -k+(m-n),k else return k,k-(m-n-t) end
end

See http://upload.wikimedia.org/wikipedia/commons/1/1d/Ulam_spiral_howto_all_numbers.svg.

$\endgroup$
  • $\begingroup$ I think it would be alright to negate the y coordinate (y *= -1), given that the first element is located at (0,0), in order to make it spiral the other way around as the question has requested. $\endgroup$ – Tim Visee Dec 14 '17 at 16:08
4
$\begingroup$

If you are looking for a no-if solution and a formula, I was able to find this one:

$A = ||x| - |y|| + |x| + |y|;$

$R = A^2 + sgn(x + y + 0.1)*(A + x - y) + 1;$

$x, y \in \mathbb{Z}$

$sgn$sign function

<?php

$n = 4;
$from = -intval($n / 2) - 1;
$to = -$from + ($n % 2) - 2;

for ($x = $to; $x > $from; $x--) {
    for ($y = $to; $y > $from; $y--) {
		$result = pow((abs(abs($x) - abs($y)) + abs($x) + abs($y)), 2) + abs($x + $y + 0.1) / ($x + $y + 0.1) * (abs(abs($x) - abs($y)) + abs($x) + abs($y) + $x - $y) + 1;
		echo $result . "\t";
    }
    echo "\n";
}

which prints

7   8   9   10  
6   1   2   11  
5   4   3   12  
16  15  14  13  

https://repl.it/repls/DarkslategraySteepBluebottle

$\endgroup$
1
$\begingroup$

As you can see from Brian's answer, the formula for it is complex. But there is a very simple recursive algorithm you can use:

  • for each step, record both your position and your orientation
  • for n = 0, start at (0,0), facing east
  • for n = 1, the spiral is (0,0): east; (0,1): east
  • for n > 1, calculate the spiral for n-1. Look to your right.
    • if the space is occupied by a point of the spiral, take a step forward
    • if the space is free, turn right, then take a step forward

It is very easy to extend to other starting orientations, and also to create a left turning spiral. Here is a Scala implementation of the algorithm. I tried to optimize it for readability, not efficiency.

object Orientation extends Enumeration {
  val north = Value("north")
  val east = Value("east")
  val south = Value("south")
  val west = Value("west")

  val orderedValues = Vector(north, east, south, west)

  def turnRight(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
    (orderedValues.indexOf(fromOrientation) + 1) % 4)

  def turnLeft(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
    (orderedValues.indexOf(fromOrientation) +3) % 4)

  def oneStepOffset(inOrientation: Orientation.Value): (Int, Int) = inOrientation match {
    case Orientation.north => (0, 1)
    case Orientation.east => (1, 0)
    case Orientation.south => (0, -1)
    case Orientation.west => (-1, 0)
  }
}

object Direction extends Enumeration {
  val straight = Value("straight")
  val right = Value("right")
  val left = Value("left")
}

def spiral(n: Int, initialOrientation: Orientation.Value = Orientation.east, turningDirection: Direction.Value = Direction.right): List[(Int, Int)] = {

  if (turningDirection == Direction.straight) throw new IllegalArgumentException("The spiral must turn left or right")
  if (n < 0) throw new IllegalArgumentException("The spiral only takes a positive integer as the number of steps")

  class Step(
    val position: (Int, Int),
    val orientation: Orientation.Value)

  def nextPosition(lastStep: Step, direction: Direction.Value): (Int, Int) = {
    val newOrientation = direction match {
      case Direction.straight => lastStep.orientation
      case Direction.right => Orientation.turnRight(lastStep.orientation)
      case Direction.left => Orientation.turnLeft(lastStep.orientation)
    }

    val offset = Orientation.oneStepOffset(newOrientation)

    return (
      lastStep.position._1 + offset._1,
      lastStep.position._2 + offset._2)
  }

  def takeStep(lastStep: Step, occupiedPositions: Seq[(Int, Int)]): Step = {
    val positionAfterTurning = nextPosition(lastStep, turningDirection)
    val nextStep = if (occupiedPositions.contains(positionAfterTurning)) {
      new Step(nextPosition(lastStep, Direction.straight), lastStep.orientation)
    } else {
      val newOrientation = turningDirection match {
        case Direction.left => Orientation.turnLeft(lastStep.orientation)
        case Direction.right => Orientation.turnRight(lastStep.orientation)
      }
      new Step(positionAfterTurning, newOrientation)
    }
    return nextStep
  }

  def calculateSpiral(upTo: Int): List[Step] = upTo match {
    case 0 => new Step((0, 0), initialOrientation) :: Nil
    case 1 => new Step(Orientation.oneStepOffset(initialOrientation), initialOrientation) :: new Step((0, 0), initialOrientation) :: Nil
    case x if x > 1 => {
      val spiralUntilNow = calculateSpiral(upTo - 1)
      val nextStep = takeStep(spiralUntilNow.head, spiralUntilNow.map(step => step.position))
      (nextStep :: spiralUntilNow)
    }
  }

  return (calculateSpiral(n).map(step => step.position)).reverse
}
$\endgroup$
  • $\begingroup$ I don't have the code handy, but this is basically what I ended up doing. By persisting a few variables it's also fairly straightforward to allow for pausing/resuming. $\endgroup$ – Jane Panda Jan 15 '15 at 16:33

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.