Square spiral

 1 def search_for_subsquare(number, sub_square_max_numbers): 2     mlen = len(sub_square_max_numbers) 3     for i in range(mlen): 4         if number <= sub_square_max_numbers[i]: 5             return i 6  7 def cal_relative_position(sub_square_line_number, max_number_in_sub_square, number): 8     pos = [0, 0] 9 10     itr_number = max_number_in_sub_square11 12     if itr_number == number:13         return pos14 15     direction = [1, 0, 1, 0] #up left down right16     move = [1, 1, -1, -1] #+ + - -17 18     for pos_mv, each_dir in enumerate(direction):19         for i in range(sub_square_line_number - 1): #range(4) means range(0, 4)20             itr_number -= 121             pos[each_dir] += move[pos_mv]22             if itr_number == number:23                 return pos24 25 26 def find_distance(first, second):27     sub_square_number_counts = [(8 * n + 4) for n in range(64)]28 29     sub_square_max_numbers = [4]30 31     len_count = len(sub_square_number_counts)32 33     for i in range(1, len_count):34         sub_square_max_numbers.append(sub_square_max_numbers[i - 1] + sub_square_number_counts[i])35 36     #search first and second in which sub_square37     first_square = search_for_subsquare(first, sub_square_max_numbers)38     second_square = search_for_subsquare(second, sub_square_max_numbers)39 40     #cal relative position in its sub_square41     pos_first = cal_relative_position((first_square + 1) * 2, sub_square_max_numbers[first_square], first)42     pos_second = cal_relative_position((second_square + 1) * 2, sub_square_max_numbers[second_square], second)43 44     #unify relative postition and cal manhatan dist45     if first_square > second_square:46         scale = first_square - second_square47         pos_second[0] += scale48         pos_second[1] += scale49     else:50         scale = second_square - first_square51         pos_first[0] += scale52         pos_first[1] += scale53 54     return abs(pos_first[0] - pos_second[0]) + abs(pos_first[1] - pos_second[1])

 1 from math import sqrt 2   3 # calculate the coordinate of n 4 def coord(n): 5     if n == 1: return (0, 0) 6     r = int(sqrt(n - 1) - 1) // 2 + 1 7     g, d = divmod(n - (2*r-1)**2 - 1, 2*r) 8     return [(-r+d+1, r), (r, r-d-1), (r-d-1, -r), (-r, -r+d+1)][g] 9  10 def find_distance(first, second):11     x1, y1 = coord(first)12     x2, y2 = coord(second)13     return abs(x2 - x1) + abs(y2 - y1)14  15     # At first, we determine ring which include n16     #   ring 0 : 117     #   ring 1 : 2,3,...,918     #   ring 2 : 10,11,...,2519     #   ring r : (2*r-1)**2+1,...,(2*r+1)**220     # Using following formula, we can calculate r from n.21     #   r = int((sqrt(n - 1) - 1) / 2) + 122     # Ring r have 8*r elements and start position is (-r+1, r).23     # And another interesting position is follows.24     #   (-r,  r) : left upper corner,  n = (2*r-1)**2 + 8*r = (2*r+1)**225     #   ( r,  r) : right upper corner, n = (2*r-1)**2 + 2*r26     #   ( r, -r) : right lower corner, n = (2*r-1)**2 + 4*r27     #   (-r, -r) : left lower corner,  n = (2*r-1)**2 + 6*r28     #29     # Second, I divide ring into 4 groups corresponding to the direction.30     # Each group size is 2*r. The group 0 is the first 2*r elements of the ring31     # and its direction is right, and so on.32     #   group 0 (dir = R) : n is from (2*r-1)**2    +1 to (2*r-1)**2+2*r33     #   group 1 (dir = D) : n is from (2*r-1)**2+2*r+1 to (2*r-1)**2+4*r34     #   group 2 (dir = L) : n is from (2*r-1)**2+4*r+1 to (2*r-1)**2+6*r35     #   group 3 (dir = U) : n is from (2*r-1)**2+6*r+1 to (2*r-1)**2+8*r36     # Using following formula, we can calculate group number g from n, r.37     #   g = int((n - (2*r-1)**2 - 1) / (2*r)38     #39     # Finally, using above information, we will calulate the coordinate of n.40     # When n belongs to group 0 of ring r, then the coordinate of n is41     # (-r+1 + d, r), where d means n is the d-th elements of the group.42     # As well, we can calculate for another groups.43     #   group 0 : (-r+1+d, r)44     #   group 1 : (r, r-1+d)45     #   group 2 : (r-1-d, r)46     #   group 3 : (-r, -r+d+1)