Найти количество поворотов в пути (набор координат)

Question

a = [(24, 13), (23, 13), (22, 13), (21, 13), (20, 13), 
    (19, 13), (19, 14), (19, 15), (18, 15), (17, 15), 
    (16, 15), (15, 15), (14, 15), (13, 15), (13, 14), 
    (13, 13), (13, 12), (13, 11), (13, 10), (12, 10), 
    (11, 10), (10, 10), (9, 10), (8, 10), (7, 10), 
    (7, 9), (7, 8), (7, 7), (7, 6), (7, 5), (7, 4), 
    (6, 4), (5, 4), (4, 4)] 

Указанный путь (набор уникальных координат) имеет 6 оборотов.

Может кто-нибудь, пожалуйста, помогите мне написать код в python? Например, для вышеуказанного списка a выход должен быть 6.

length = len(a)-3 
print length 

for i in range(0,length): 
    x1,y1 = a[i] 
    x2,y2 = a[i+1] 
    x3,y3 = a[i+2] 

    if y1 is y2: 
     if y1 is y3: 
      x_flag = 1 
     else: 
      x_flag = 0 

    if x_flag is 0: 
     flag1 += 1 
     print 'Turn' 

print flag1 

Answer 1

Вы можете преобразовать кортежи в массив numpy и проверить, были ли вы перемещены по двум осям после двух ножек.

arr = np.array(a) 
((np.abs(arr[2:] - arr[:-2])>0).sum(axis=1)==2).sum() 

Answer 2

Вероятно, не симпатичным решение, но простым способом было бы это:

a = [(24, 13), (23, 13), (22, 13), (21, 13), (20, 13), 
    (19, 13), (19, 14), (19, 15), (18, 15), (17, 15), 
    (16, 15), (15, 15), (14, 15), (13, 15), (13, 14), 
    (13, 13), (13, 12), (13, 11), (13, 10), (12, 10), 
    (11, 10), (10, 10), (9, 10), (8, 10), (7, 10), 
    (7, 9), (7, 8), (7, 7), (7, 6), (7, 5), (7, 4), 
    (6, 4), (5, 4), (4, 4)] 

count = 0 
direction = -1 

for i in range(1,len(a)): 
    current_dir = 0 if a[i][0]-a[i-1][0] != 0 else 1 
    if direction != -1: 
     if current_dir != direction: 
      # print("changing direction") 
      count += 1 
    direction = current_dir 

print count 

Это предполагает, что вы только когда-либо изменения в одном направлении (т.е. никогда не движется по диагонали).

Answer 3

Вот что я предлагаю:

x0, y0 = a[0] 
previous_move_dir = '' 
turns_nb = -1 # start is not a turn 
for x1, y1 in a[1:]: 
    if x1 == x0 and abs(y1-y0) == 1: # move is 1 in Y direction 
     move_dir = 'Y' 
    elif y1 == y0 and abs(x1-x0) == 1: # move is 1 in X direction 
     move_dir = 'X' 
    else: # move is anything else 
     raise Exception('Bad coordinates definition') 

    if move_dir != previous_move_dir: # there is a direction change 
     turns_nb += 1 
    previous_move_dir = move_dir 
    x0, y0 = x1, y1 

print turns_nb