80 lines
2.3 KiB
Python
Executable File
80 lines
2.3 KiB
Python
Executable File
#!/usr/bin/env python
|
|
# -*- coding: utf-8 -*-
|
|
|
|
NORTH, S, W, E = (0, -1), (0, 1), (-1, 0), (1, 0) # directions
|
|
|
|
turn_right = {
|
|
E: NORTH,
|
|
NORTH: W,
|
|
W: S,
|
|
S: E,
|
|
} # old -> new direction
|
|
|
|
def spiral(width, height):
|
|
if width < 1 or height < 1:
|
|
raise ValueError
|
|
x, y = width // 2, height // 2 # start near the center
|
|
dx, dy = S # initial direction
|
|
matrix = [[None] * width for _ in range(height)]
|
|
count = 0
|
|
while True:
|
|
count += 1
|
|
matrix[y][x] = count # visit
|
|
# try to turn right
|
|
new_dx, new_dy = turn_right[dx,dy]
|
|
new_x, new_y = x + new_dx, y + new_dy
|
|
if (0 <= new_x < width and 0 <= new_y < height and
|
|
matrix[new_y][new_x] is None): # can turn right
|
|
x, y = new_x, new_y
|
|
dx, dy = new_dx, new_dy
|
|
else: # try to move straight
|
|
x, y = x + dx, y + dy
|
|
if not (0 <= x < width and 0 <= y < height):
|
|
return matrix # nowhere to go
|
|
|
|
def spiral2(width, height):
|
|
if width < 1 or height < 1:
|
|
raise ValueError
|
|
x, y = width // 2, height // 2 # start near the center
|
|
dx, dy = S # initial direction
|
|
mydict = {}
|
|
matrix = [[None] * width for _ in range(height)]
|
|
count = 0
|
|
while True:
|
|
count += 1
|
|
matrix[y][x] = count # visit
|
|
mydict[count] = (x,y)
|
|
# try to turn right
|
|
new_dx, new_dy = turn_right[dx,dy]
|
|
new_x, new_y = x + new_dx, y + new_dy
|
|
if (0 <= new_x < width and 0 <= new_y < height and
|
|
matrix[new_y][new_x] is None): # can turn right
|
|
x, y = new_x, new_y
|
|
dx, dy = new_dx, new_dy
|
|
else: # try to move straight
|
|
x, y = x + dx, y + dy
|
|
if not (0 <= x < width and 0 <= y < height):
|
|
#return matrix # nowhere to go
|
|
return mydict
|
|
|
|
|
|
def print_matrix(matrix):
|
|
width = len(str(max(el for row in matrix for el in row if el is not None)))
|
|
fmt = "{:0%dd}" % width
|
|
for row in matrix:
|
|
print(" ".join("_"*width if el is None else fmt.format(el) for el in row))
|
|
|
|
#print_matrix(spiral(601, 601))
|
|
#print_matrix(spiral(5, 5))
|
|
|
|
aids = spiral2(601,601)
|
|
|
|
dstx = aids[1][0]
|
|
dsty = aids[1][1]
|
|
|
|
x = aids[265149][0]
|
|
y = aids[265149][1]
|
|
|
|
distance = abs(x - dstx) + abs(y - dsty)
|
|
print(distance)
|