Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Hexagon Spiral by jcg
#hex-spiral
def hex_spiral(a, b):
return dist (find_place(a), find_place(b))
def find_place(n):
## ring 0 contains 1 number
## ring 1 contains 6*1 number -> total 1+6*1
## ring 2 contains 6*2 number -> total 1*6*(1+2)
## ...
## ring k contains 6*k numbers -> total 1*6*(1+2+...+k) = 1+6*k*(k+1)//2 numbers
##
## n is on ring k / 6*(k-1)*k//2 <= n-2 < 6*k*(k+1)//2
## (k-1)*k <= (n-2)/3 < k(k+1)
# compute # of ring :
k = 0
while k * (k + 1) <= (n - 2) // 3:
k += 1
if k == 0:
return (0, 0)
# compute which side (0=nw,1=ne,2=e,3=se,4=sw,5=w)
side_length = k
first_on_ring = 3 * k * (k-1) + 2
side = (n - first_on_ring) // side_length
first_on_side = first_on_ring + side * side_length
pos_in_side = n - first_on_side
# compute coords
if side == 0:
x = -k + 1 + pos_in_side
y = k
elif side == 1:
x = 1 + pos_in_side
y = k - 1 - pos_in_side
elif side == 2:
x = k
y = -1 - pos_in_side
elif side == 3:
x = k - 1 - pos_in_side
y = -k
elif side == 4:
x = -1 - pos_in_side
y = -k + 1 + pos_in_side
elif side == 5:
x = -k
y = 1 + pos_in_side
return (x,y)
def dist(a,b):
if a[0] > b[0]:
return dist(b, a)
if a[0] == b[0]:
return abs(a[1] - b[1])
deltax = b[0] - a[0]
ymax = a[1]
ymin = a[1] - deltax
if ymin <= b[1] <= ymax:
return deltax
elif b[1] > ymax:
return deltax + (b[1] - ymax)
else: # b[1] < ymin
return deltax + (ymin - b[1])
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert hex_spiral(2, 9) == 1, "First"
assert hex_spiral(9, 2) == 1, "Reverse First"
assert hex_spiral(6, 19) == 2, "Second, short way"
assert hex_spiral(5, 11) == 3, "Third"
assert hex_spiral(13, 15) == 2, "Fourth, One row"
assert hex_spiral(11, 17) == 4, "Fifth, One more test"
Nov. 12, 2014
