Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Coordinate transform solution in Clear category for Square Spiral by macfreek
#!/usr/bin/env python3.2
# -*- coding: utf-8 -*-
"""Problem:
The map of circuit consists of square cells. The first element in the center is marked as 1, continuing clockwise spiral the other elements are marked in ascending order up to infinity. On the map, you can move (connect) vertically and horizontally. For example, the distance between cells 1 and 9 - two moves, between 24 and 9 - one move. Find the distance between any two elements.
^ 3 37 36 35 34 33 32 31
| 2 38 17 16 15 14 13 30
| 1 39 18 5 4 3 12 29
0 40 19 6 1 2 11 28
y -1 41 20 7 8 9 10 27
-2 42 21 22 23 24 25 26
-3 43 44 45 46 47 48 49
-3 -2 -1 0 1 2 3 --> x
"""
"""General remarks:
The spiral forms a square of d*d numbers, with d the diameter. The first number of a new spiral is the next number after the square of (d-2)*(d-2) numbers. So the second circle (d=3) starts with 2 = (1^2+1), the third circle (d=5) starts with 10 = 3^2+1, and the fourth circle (d=7) starts with 26 = 5^2+1, etc.
The diameter of each circle is 2*r-1, with r the radius.
The corner numbers are the (d-1)th, 2(d-1)th, 3(d-1)th and 4(d-1)th number in the circle.
"""
from math import sqrt
def IndexToCoord(index):
"""Given a index in the spiral 1...., return the x,y coordinate. E.g.:
IndexToCoord(1) = 0,0;
IndexToCoord(2) = 1,0;
IndexToCoord(3) = 1,1;
IndexToCoord(4) = 0,1;
IndexToCoord(5) = -1,1;
IndexToCoord(6) = -1,0;
IndexToCoord(7) = -1,-1;
IndexToCoord(8) = 0,-1;
IndexToCoord(9) = 1,-1;
IndexToCoord(10) = 2,-1;
IndexToCoord(11) = 2,0;
etc.
"""
# radius
r = int((1+sqrt(index-1))/2)
if r == 0:
return 0,0
d = 2*r - 1
# start index of each side
side, index = divmod(index - d*d - 1, 2*r)
index += 1 - r
if side == 0:
return (r, index)
elif side == 1:
return (-index, r)
elif side == 2:
return (-r, -index)
else: # side == 3
return (index, -r)
def CoordToIndex(x, y):
"""Given a position (x,y) return the index in the spiral. E.g.:
IndexToCoord(0,0) = 1;
IndexToCoord(1,0) = 2;
IndexToCoord(1,1) = 3;
IndexToCoord(0,1) = 4;
IndexToCoord(-1,1) = 5;
IndexToCoord(-1,0) = 6;
IndexToCoord(-1,-1) = 7;
IndexToCoord(0,-1) = 8;
IndexToCoord(1,-1) = 9;
IndexToCoord(2,-1) = 10;
IndexToCoord(2,0) = 11;
etc.
"""
# radius
r = max(abs(x),abs(y))
if r == -y: # side == 3
return 4*r*r + 3*r + 1 + x
elif r == x: # side == 0
return 4*r*r - 3*r + 1 + y
elif r == y: # side == 1:
return 4*r*r - r + 1 - x
elif r == -x: # side == 2:
return 4*r*r + r + 1 - y
raise AssertionError()
def find_distance(first, second):
"Find the destination"
ax, ay = IndexToCoord(first)
bx, by = IndexToCoord(second)
return abs(ax-bx) + abs(ay-by)
May 29, 2014