Mixing
On a two dimensional grid is there a formula I can use to spiral coordinates in an outward pattern?
$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?
coordinate-systems
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
$endgroup$
add a comment |
$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?
coordinate-systems
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
$endgroup$
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58
add a comment |
$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?
coordinate-systems
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
$endgroup$
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?
coordinate-systems
coordinate-systems
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
asked Jun 25 '12 at 23:33
Jane PandaJane Panda
16816
16816
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58
add a comment |
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58
add a comment |
4 Answers
4
active
oldest
votes
$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,0rangle$, the origin, position $1$ is $langle 1,0rangle$, position $2$ is $langle 1,-1rangle$, 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 $2sum_{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,0rangle$, the starting position after $k$ full blocks is $langle -k,krangle$.
Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<nle(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,krangle,&text{if }2k(2k+1)<nle(2k+1)^2\
langle k+1,4k^2+5k+1-nrangle,&text{if }(2k+1)^2<nle 2(k+1)(2k+1)\
langle 4k^2+7k+3-n,-k-1rangle,&text{if }2(k+1)(2k+1)<nle4(k+1)^2\
langle -k-1,n-4k^2-9k-5rangle,&text{if }4(k+1)^2<nle2(k+1)(2k+3);.
end{cases}$$
To find $k$ easily, let $m=lfloorsqrt nrfloor$. If $m$ is odd, $k=frac12(m-1)$. If $m$ is even, and $nge m(m+1)$, then $k=frac{m}2$; otherwise, $k=frac{m}2-1$.
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
$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
add a comment |
$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.
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
$endgroup$
$begingroup$
I think it would be alright to negate theycoordinate (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
add a comment |
$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
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
$endgroup$
add a comment |
$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
}
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f163080%2fon-a-two-dimensional-grid-is-there-a-formula-i-can-use-to-spiral-coordinates-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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,0rangle$, the origin, position $1$ is $langle 1,0rangle$, position $2$ is $langle 1,-1rangle$, 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 $2sum_{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,0rangle$, the starting position after $k$ full blocks is $langle -k,krangle$.
Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<nle(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,krangle,&text{if }2k(2k+1)<nle(2k+1)^2\
langle k+1,4k^2+5k+1-nrangle,&text{if }(2k+1)^2<nle 2(k+1)(2k+1)\
langle 4k^2+7k+3-n,-k-1rangle,&text{if }2(k+1)(2k+1)<nle4(k+1)^2\
langle -k-1,n-4k^2-9k-5rangle,&text{if }4(k+1)^2<nle2(k+1)(2k+3);.
end{cases}$$
To find $k$ easily, let $m=lfloorsqrt nrfloor$. If $m$ is odd, $k=frac12(m-1)$. If $m$ is even, and $nge m(m+1)$, then $k=frac{m}2$; otherwise, $k=frac{m}2-1$.
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
$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
add a comment |
$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,0rangle$, the origin, position $1$ is $langle 1,0rangle$, position $2$ is $langle 1,-1rangle$, 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 $2sum_{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,0rangle$, the starting position after $k$ full blocks is $langle -k,krangle$.
Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<nle(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,krangle,&text{if }2k(2k+1)<nle(2k+1)^2\
langle k+1,4k^2+5k+1-nrangle,&text{if }(2k+1)^2<nle 2(k+1)(2k+1)\
langle 4k^2+7k+3-n,-k-1rangle,&text{if }2(k+1)(2k+1)<nle4(k+1)^2\
langle -k-1,n-4k^2-9k-5rangle,&text{if }4(k+1)^2<nle2(k+1)(2k+3);.
end{cases}$$
To find $k$ easily, let $m=lfloorsqrt nrfloor$. If $m$ is odd, $k=frac12(m-1)$. If $m$ is even, and $nge m(m+1)$, then $k=frac{m}2$; otherwise, $k=frac{m}2-1$.
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
$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
add a comment |
$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,0rangle$, the origin, position $1$ is $langle 1,0rangle$, position $2$ is $langle 1,-1rangle$, 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 $2sum_{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,0rangle$, the starting position after $k$ full blocks is $langle -k,krangle$.
Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<nle(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,krangle,&text{if }2k(2k+1)<nle(2k+1)^2\
langle k+1,4k^2+5k+1-nrangle,&text{if }(2k+1)^2<nle 2(k+1)(2k+1)\
langle 4k^2+7k+3-n,-k-1rangle,&text{if }2(k+1)(2k+1)<nle4(k+1)^2\
langle -k-1,n-4k^2-9k-5rangle,&text{if }4(k+1)^2<nle2(k+1)(2k+3);.
end{cases}$$
To find $k$ easily, let $m=lfloorsqrt nrfloor$. If $m$ is odd, $k=frac12(m-1)$. If $m$ is even, and $nge m(m+1)$, then $k=frac{m}2$; otherwise, $k=frac{m}2-1$.
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
$endgroup$
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,0rangle$, the origin, position $1$ is $langle 1,0rangle$, position $2$ is $langle 1,-1rangle$, 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 $2sum_{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,0rangle$, the starting position after $k$ full blocks is $langle -k,krangle$.
Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<nle(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,krangle,&text{if }2k(2k+1)<nle(2k+1)^2\
langle k+1,4k^2+5k+1-nrangle,&text{if }(2k+1)^2<nle 2(k+1)(2k+1)\
langle 4k^2+7k+3-n,-k-1rangle,&text{if }2(k+1)(2k+1)<nle4(k+1)^2\
langle -k-1,n-4k^2-9k-5rangle,&text{if }4(k+1)^2<nle2(k+1)(2k+3);.
end{cases}$$
To find $k$ easily, let $m=lfloorsqrt nrfloor$. If $m$ is odd, $k=frac12(m-1)$. If $m$ is even, and $nge m(m+1)$, then $k=frac{m}2$; otherwise, $k=frac{m}2-1$.
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
answered Jun 26 '12 at 0:55
Brian M. ScottBrian M. Scott
460k40515917
460k40515917
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
add a comment |
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
1
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$
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$
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$
@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
$begingroup$
@Kaligule ... i agree. not at all obvious. thus my question
$endgroup$
– phdmba7of12
Nov 30 '18 at 19:14
add a comment |
$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.
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
$endgroup$
$begingroup$
I think it would be alright to negate theycoordinate (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
add a comment |
$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.
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
$endgroup$
$begingroup$
I think it would be alright to negate theycoordinate (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
add a comment |
$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.
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
$endgroup$
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.
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
edited Jun 26 '12 at 1:56
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
answered Jun 26 '12 at 1:51
lhflhf
167k11172403
167k11172403
$begingroup$
I think it would be alright to negate theycoordinate (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
add a comment |
$begingroup$
I think it would be alright to negate theycoordinate (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
$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
$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
add a comment |
$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
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
$endgroup$
add a comment |
$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
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
$endgroup$
add a comment |
$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
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
$endgroup$
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
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
edited Feb 2 at 1:30
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
answered Feb 7 '18 at 3:25
AxalixAxalix
1413
1413
add a comment |
add a comment |
$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
}
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
$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
add a comment |
$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
}
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
$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
add a comment |
$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
}
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
$endgroup$
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
}
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
edited Jan 15 '15 at 10:07
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
answered Jan 15 '15 at 9:02
rumtschorumtscho
701519
701519
$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
add a comment |
$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
$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
$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
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f163080%2fon-a-two-dimensional-grid-is-there-a-formula-i-can-use-to-spiral-coordinates-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Possible duplicate of math.stackexchange.com/questions/42942/…
$endgroup$
– lhf
Jun 26 '12 at 1:58