問(wèn)題描述：
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then
counting up while spiraling outward. For example, the first few squares are allocated like this:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...
While this is very space-efficient (no squares are skipped), requested data must be carried back to
square 1 (the location of the only access port for this memory system) by programs that can only
move up, down, left, or right. They always take the shortest path: the Manhattan Distance between
the location of the data and square 1.
For example:
Data from square 1 is carried 0 steps, since it's at the access port.
Data from square 12 is carried 3 steps, such as: down, left, left.
Data from square 23 is carried only 2 steps: up twice.
Data from square 1024 must be carried 31 steps.
How many steps are required to carry the data from the square identified in your puzzle input all
the way to the access port?
解決代碼(通過(guò)歸納法)
'''
螺旋數(shù)組用每個(gè)節(jié)點(diǎn)的坐標(biāo)位置保存在節(jié)點(diǎn)屬性position中
值為1的節(jié)點(diǎn)定義位置為(0,0),其余節(jié)點(diǎn)坐標(biāo)都為與(0,0)節(jié)點(diǎn)的相對(duì)位置
按照打印的話速客，看起來(lái)就像是這樣:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23--->...
由內(nèi)往外逆時(shí)針生序排列
歸納規(guī)律
初始點(diǎn)--------------第1個(gè)節(jié)點(diǎn)
1：1_(0,0)
第1次 多向移動(dòng)--------------右上 兩個(gè)方向上各移動(dòng)1次 向右移動(dòng)相當(dāng)于+(1,0) 向上移動(dòng)相當(dāng)于+(0,1)
2(自上個(gè)節(jié)點(diǎn):向右1位): 1_(0,0) 2_(1,0)
3(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1)
第2次,多向移動(dòng)-------------左下 兩個(gè)方向上各移動(dòng)各2次 向左移動(dòng)相當(dāng)于+(-1,0) 向下移動(dòng)相當(dāng)于+(0,-1)
4(自上個(gè)節(jié)點(diǎn):向左1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1)
5(自上個(gè)節(jié)點(diǎn):向左1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1)
6(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0)
7(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1)
第3次,多向移動(dòng)-------------右上 兩個(gè)方向上各移動(dòng)3位 向右移動(dòng)相當(dāng)于+(1,0) 向上移動(dòng)相當(dāng)于+(0,1)
8 (自上個(gè)節(jié)點(diǎn):向右1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1)
9 (自上個(gè)節(jié)點(diǎn):向右1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1)
10(自上個(gè)節(jié)點(diǎn):向右1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1)
11(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0)
12(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1)
13(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2)
第4次,多向移動(dòng)------------左下 兩個(gè)方向上各移動(dòng)4位 向左移動(dòng)相當(dāng)于+(-1,0) 向下移動(dòng)相當(dāng)于+(0,-1)
14(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2)
15(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2)
16(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2)
17(自上個(gè)節(jié)點(diǎn):向上1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2)
18(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1)
19(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1) 19_(-2,0)
20(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1) 19_(-2,0) 20_(-2,-1)
21(自上個(gè)節(jié)點(diǎn):向下1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1) 19_(-2,0) 20_(-2,-1) 21_(-2,-2)
第5次,多向移動(dòng)------------右上 兩個(gè)方向上各移動(dòng)5位 向右移動(dòng)相當(dāng)于+(1,0) 向上移動(dòng)相當(dāng)于+(0,1)
22(自上個(gè)節(jié)點(diǎn):向左1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1) 19_(-2,0) 20_(-2,-1) 21_(-2,-2) 22_(-1,-2)
23(自上個(gè)節(jié)點(diǎn):向左1位): 1_(0,0) 2_(1,0) 3_(1,1) 4_(0,1) 5_(-1,1) 6_(-1,0) 7_(-1,-1) 8_(0,-1) 9_(1,-1) 10_(2,-1) 11_(2,0) 12_(2,1) 13_(2,2) 14_(1,2) 15_(0,2) 16_(-1,2) 17_(-2,2) 18(-2,1) 19_(-2,0) 20_(-2,-1) 21_(-2,-2) 22_(-1,-2) 23_(0,-2)
.
.
.
.
由以上規(guī)律可以看出，從1值點(diǎn)開(kāi)始，我們按照 右->上->左->下 開(kāi)始漫游，當(dāng)漫游到當(dāng)前方向的最后一個(gè)位置時(shí)候，換下一個(gè)方向繼續(xù)漫游
'''
import collections
#定義坐標(biāo)表示
Position=collections.namedtuple('Position','x y')
#節(jié)點(diǎn)對(duì)象
class Node:
#初始化 設(shè)置節(jié)點(diǎn)的值
def __init__(self,val):
self.val=val #設(shè)置 Node 節(jié)點(diǎn)的值
#設(shè)置坐標(biāo)值
def set_position(self,position):
self.position=position
def __repr__(self):
return "{}_({},{})".format(self.val,self.position.x,self.position.y)
def __str__(self):
return self.__str__()
#根據(jù)當(dāng)前漫游方向獲取接下來(lái)漫游的方向 按照: 右 上 左 下 的方向循環(huán)
def get_direction(direction_index):
if direction_index<=2:
result=direction_index+1
if direction_index==3:
result=0
return result
#根據(jù)輸入的值n尘应，創(chuàng)建從1到n的n個(gè)節(jié)點(diǎn),返回各個(gè)節(jié)點(diǎn)組成的字典
def generate_nodes(n):
#存放結(jié)果集合
result_dict={}
#向各個(gè)方向移動(dòng)需要變更的節(jié)點(diǎn)位置值
direction_move_list=[(1,0),(0,1),(-1,0),(0,-1)] #方向: 右 上 左 下
#判斷1個(gè)特殊情況,n=1時(shí)
result_dict[1]=Node(1)
result_dict[1].position=Position(0,0)
if n==1:
#直接返回結(jié)果
return result_dict
#開(kāi)始漫游并創(chuàng)建漫游到的節(jié)點(diǎn)
current_n=1 #記錄當(dāng)前漫游到的節(jié)點(diǎn)
#記錄第幾次多向移動(dòng)(這個(gè)定義結(jié)合上面的分析) 多向移動(dòng)的次數(shù)
movie_times=1
#控制漫游方向變化
direction_index=0
while True:
for i in range(2):
#在這個(gè)方上已經(jīng)移動(dòng)的次數(shù)
direction_times=0
#定向漫游移動(dòng)次數(shù) 小于 多向移動(dòng)次數(shù)
while direction_times<movie_times:
#當(dāng)前漫游到的節(jié)點(diǎn)的值等于輸入的n則跳出
if current_n==n:
return result_dict
current_node=result_dict[current_n]
current_n+=1
result_dict[current_n]=Node(current_n) #創(chuàng)建漫游到的新節(jié)點(diǎn)
#新節(jié)點(diǎn)的x值 y值
x=current_node.position.x+direction_move_list[direction_index][0]
y=current_node.position.y+direction_move_list[direction_index][1]
result_dict[current_n].position=Position(x,y)
#定向移動(dòng)步數(shù)加1
direction_times+=1
#換向
direction_index=get_direction(direction_index)
#移動(dòng)次數(shù)加1
movie_times+=1
#測(cè)試輸出1
def main_01():
display_01=[[" " for _ in range(9)] for _ in range(9)]
test_result_01=generate_nodes(9)
print(test_result_01)
basic_position=Position(4,4)
for key in test_result_01:
x,y=test_result_01[key].position.x+basic_position.x,(-1)*test_result_01[key].position.y+basic_position.y
display_01[y][x]="%4d"%key
for item in display_01:
print(item)
#測(cè)試輸出2
def main_02():
display_01=[[" " for _ in range(9)] for _ in range(9)]
test_result_01=generate_nodes(23)
print(test_result_01)
basic_position=Position(4,4)
for key in test_result_01:
x,y=test_result_01[key].position.x+basic_position.x,(-1)*test_result_01[key].position.y+basic_position.y
display_01[y][x]="%4d"%key
for item in display_01:
print(item)
print('-*-'*100)
#測(cè)試輸出3
def main_03():
display_01=[[" " for _ in range(9)] for _ in range(9)]
test_result_01=generate_nodes(1)
print(test_result_01)
basic_position=Position(4,4)
for key in test_result_01:
x,y=test_result_01[key].position.x+basic_position.x,(-1)*test_result_01[key].position.y+basic_position.y
display_01[y][x]="%4d"%key
for item in display_01:
print(item)
print('-*-'*100)
#測(cè)試輸出3
def main_04():
display_01=[[" " for _ in range(9)] for _ in range(9)]
test_result_01=generate_nodes(78)
print(test_result_01)
basic_position=Position(4,4)
for key in test_result_01:
x,y=test_result_01[key].position.x+basic_position.x,(-1)*test_result_01[key].position.y+basic_position.y
display_01[y][x]="%4d"%key
for item in display_01:
print(item)
print('-*-'*100)
if __name__=="__main__":
main_01()
main_02()
main_03()
main_04()
'''
輸出結(jié)果:
{1: 1_(0,0), 2: 2_(1,0), 3: 3_(1,1), 4: 4_(0,1), 5: 5_(-1,1), 6: 6_(-1,0), 7: 7_(-1,-1), 8: 8_(0,-1), 9: 9_(1,-1)}
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' 5', ' 4', ' 3', ' ', ' ', ' ']
[' ', ' ', ' ', ' 6', ' 1', ' 2', ' ', ' ', ' ']
[' ', ' ', ' ', ' 7', ' 8', ' 9', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
{1: 1_(0,0), 2: 2_(1,0), 3: 3_(1,1), 4: 4_(0,1), 5: 5_(-1,1), 6: 6_(-1,0), 7: 7_(-1,-1), 8: 8_(0,-1), 9: 9_(1,-1), 10: 10_(2,-1), 11: 11_(2,0), 12: 12_(2,1), 13: 13_(2,2), 14: 14_(1,2), 15: 15_(0,2), 16: 16_(-1,2), 17: 17_(-2,2), 18: 18_(-2,1), 19: 19_(-2,0), 20: 20_(-2,-1), 21: 21_(-2,-2), 22: 22_(-1,-2), 23: 23_(0,-2)}
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' 17', ' 16', ' 15', ' 14', ' 13', ' ', ' ']
[' ', ' ', ' 18', ' 5', ' 4', ' 3', ' 12', ' ', ' ']
[' ', ' ', ' 19', ' 6', ' 1', ' 2', ' 11', ' ', ' ']
[' ', ' ', ' 20', ' 7', ' 8', ' 9', ' 10', ' ', ' ']
[' ', ' ', ' 21', ' 22', ' 23', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
-*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*-
{1: 1_(0,0)}
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' 1', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
-*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*-
{1: 1_(0,0), 2: 2_(1,0), 3: 3_(1,1), 4: 4_(0,1), 5: 5_(-1,1), 6: 6_(-1,0), 7: 7_(-1,-1), 8: 8_(0,-1), 9: 9_(1,-1), 10: 10_(2,-1), 11: 11_(2,0), 12: 12_(2,1), 13: 13_(2,2), 14: 14_(1,2), 15: 15_(0,2), 16: 16_(-1,2), 17: 17_(-2,2), 18: 18_(-2,1), 19: 19_(-2,0), 20: 20_(-2,-1), 21: 21_(-2,-2), 22: 22_(-1,-2), 23: 23_(0,-2), 24: 24_(1,-2), 25: 25_(2,-2), 26: 26_(3,-2), 27: 27_(3,-1), 28: 28_(3,0), 29: 29_(3,1), 30: 30_(3,2), 31: 31_(3,3), 32: 32_(2,3), 33: 33_(1,3), 34: 34_(0,3), 35: 35_(-1,3), 36: 36_(-2,3), 37: 37_(-3,3), 38: 38_(-3,2), 39: 39_(-3,1), 40: 40_(-3,0), 41: 41_(-3,-1), 42: 42_(-3,-2), 43: 43_(-3,-3), 44: 44_(-2,-3), 45: 45_(-1,-3), 46: 46_(0,-3), 47: 47_(1,-3), 48: 48_(2,-3), 49: 49_(3,-3), 50: 50_(4,-3), 51: 51_(4,-2), 52: 52_(4,-1), 53: 53_(4,0), 54: 54_(4,1), 55: 55_(4,2), 56: 56_(4,3), 57: 57_(4,4), 58: 58_(3,4), 59: 59_(2,4), 60: 60_(1,4), 61: 61_(0,4), 62: 62_(-1,4), 63: 63_(-2,4), 64: 64_(-3,4), 65: 65_(-4,4), 66: 66_(-4,3), 67: 67_(-4,2), 68: 68_(-4,1), 69: 69_(-4,0), 70: 70_(-4,-1), 71: 71_(-4,-2), 72: 72_(-4,-3), 73: 73_(-4,-4), 74: 74_(-3,-4), 75: 75_(-2,-4), 76: 76_(-1,-4), 77: 77_(0,-4), 78: 78_(1,-4)}
[' 65', ' 64', ' 63', ' 62', ' 61', ' 60', ' 59', ' 58', ' 57']
[' 66', ' 37', ' 36', ' 35', ' 34', ' 33', ' 32', ' 31', ' 56']
[' 67', ' 38', ' 17', ' 16', ' 15', ' 14', ' 13', ' 30', ' 55']
[' 68', ' 39', ' 18', ' 5', ' 4', ' 3', ' 12', ' 29', ' 54']
[' 69', ' 40', ' 19', ' 6', ' 1', ' 2', ' 11', ' 28', ' 53']
[' 70', ' 41', ' 20', ' 7', ' 8', ' 9', ' 10', ' 27', ' 52']
[' 71', ' 42', ' 21', ' 22', ' 23', ' 24', ' 25', ' 26', ' 51']
[' 72', ' 43', ' 44', ' 45', ' 46', ' 47', ' 48', ' 49', ' 50']
[' 73', ' 74', ' 75', ' 76', ' 77', ' 78', ' ', ' ', ' ']
-*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*-
Process finished with exit code 0
'''
