Pythonic способ выяснить прямые пути на квадратной решетке сетки?

Question

Я не совсем уверен, как описать мой вопрос здесь, поэтому, я думаю, я попытаюсь сначала объяснить ситуацию. У меня есть набор данных, который вытягивается из квадратной решетчатой ​​сетки из четырехгранных многоугольников. Размеры решетки не гарантируются, в частности. У меня есть доступ к данным, которые описывают соседи любой точки на сетке (т. Е. «Точка 236 имеет ребра к точкам 417, 872, 123 и 331»), и это о ней.

Что у меня есть это:

graph = [set([5, 9]), set([4, 11]), set([5, 6, 12]), set([6, 10, 2]), \ 
     set([1, 3, 8]), set([3, 7, 4]), set([6, 12, 10, 16]), \ 
     set([5, 9, 18, 12]), set([1, 8, 13]), set([4, 11, 7, 15]), \ 
     set([2, 10, 17]), set([3, 7, 8, 14]), set([9, 18]), \ 
     set([18, 12, 16]), set([16, 10, 17]), set([14, 7, 15]), \ 
     set([15, 11]), set([13, 8, 14])] 

Где graph[n] позволяет мне получить доступ к соседям любой заданной точке по индексу n ... Весь набор данных, которые могут быть визуализированы в 2D-графике, показанном ниже (которые не имеют доступа к другой, то с помощью данных, указанных выше):

*--------*--------*-------*-------*-------* 
| 1  | 5  | 3  | 6  | 4  | 2 
|  |  |  |  |  | 
|  |  |  |  |  | 
*--------*--------*-------*-------*-------* 
| 9  | 8  | 12 | 7  | 10 | 11 
|  |  |  |  |  | 
|  |  |  |  |  | 
*--------*--------*-------*-------*-------* 
    13  18  14  16  15  17 

И я пытаюсь, чтобы включить его в набор данных, который выглядит следующим образом:

u = [[1, 5, 3, 6, 4, 2], [9, 8, 12, 7, 10, 11], [13, 18, 14, 16, 15, 17]] 
v = [[1, 9, 13], [5, 8, 18], [3, 12, 14], [6, 7, 16], [4, 10, 15], [2, 11, 17]] 

Выходные данные описывают параллельные линии сетки (начиная с угла с наименьшим номером индекса). Гарантируется, что каждая точка имеет уникальный индекс, и сетка гарантированно будет иметь непрерывный набор индексов (в данном случае от 1 до 18), но порядок не гарантируется каким-либо образом. Размеры сетки не известны заранее. Каждая точка будет иметь только значение 2 (угловая точка), 3 (крайняя точка) или 4 (точка где-то в центре).

Теперь я написал подход грубой силы к этому, но он довольно неэффективен. Он состоит из вычисления первых двух горизонтальных и вертикальных краев (в данном случае [1, 5, 3, 6, 4, 2] и [1, 9, 13]), затем «сдвигая» каждое кромку, получая соединенных соседей каждой точки и вычитая из них уже посещенный набор (так 1 -> 5, 9 -> 8, 13 -> 18) и повторяя этот процесс, пока вы не нажмете на другую сторону сетки.

Что мне было интересно, если был более «питонический» способ справиться с этим. Мой собственный код разделен на несколько разных этапов, но я решил, что нужно сделать какой-то способ сделать это одним махом, а не повторять все так много раз (в настоящее время он принимает меня около 60 мс за ход, чтобы понять все это, и я пытаюсь довести это до 20 мс, если это возможно).

Answer 1

Я думаю, что вы можете построить свою сетку постепенно, по одному узлу за раз без особых проблем. Вот как бы я это сделал:

1. Начните с любого углового узла, который вы можете обнаружить у него только с двумя соседями.
2. Найдите один край (неважно, какой из них), выбрав один из ваших соседей вашего стартового узла, а затем многократно переходите к соседу с ровно тремя соседними соседями (а не с четырьмя), избегая возврата к предыдущему узлу , Конечный случай - это когда вы добираетесь до другого угла.
3. Петля над строкой, которую вы только что нашли, взяв оставшегося соседа каждого узла. Остался только один соседний узел (это еще не в сетке), поэтому здесь нет никакой сложности.
4. Повторите шаг 3, пока не дойдете до крайнего края.
5. Сделайте свой второй список (из столбцов), переставив списки (например,с zip(*rows))

Если ваш сосед данные в виде словаря отображения из каждого узла в список своих соседей, этот код должен работать:

def make_grid(neighbor_dict): 
    # step 1, find the first corner 
    for node, neighbors in neighbor_dict: 
     if len(neighbors) == 2: 
      break # node and neighbors will hold our start corner and its neighbors 

    # step 2, build the first edge 
    row = [node, neighbor[0]] # start with the corner, and an arbitrary neighbor 
    while len(neighbors_dict[row[-1]]) == 3: 
     for neighbor in neighbor_dict[row[-1]]: 
      if neighbor != row[-2] and len(neighbor_dict[neighbor]) <= 3: 
       row.append(neighbor) 
       break 

    # setup for steps 3 and 4 
    seen = set(row) # a set of all nodes we've added to the grid so far 
    rows = [] 
    done = False 

    while not done: # this loop is step 4, building all rows 
     rows.append(row) 
     new_row = [] 
     for node in row: # this is step 3, building a new row from the previous row 
      for neighbor in neighbor_dict[node]: 
       if neighbor not in seen: 
        new_row.append(neighbor) 
        seen.add(neighbor) 
        break 
      else: # no break hit in for loop, only happens if `row` is the far edge 
       done = True 
       break 
     row = new_row 

    # step 5, transpose to get columns from rows 
    columns = list(zip(*rows)) 

    return rows, columns 

Answer 2

Вы можете посмотреть по этому коду:

def lattice_paths_of_n(n): 
    list2 = [] 
    my_list = [] 
    for i in range(1, n+2): 
     list2.append(i) 
    for i in range(1, n+2): 
     my_list.append(list2) 
    for i in range(0,n+1): 
     for f in range(0,n+1): 
      if f == 0 or i == 0: 
       my_list[i][f] = 1 
      else: 
       my_list[i][f] = my_list[i-1][f]+my_list[i][f-1] 
    return my_list[n][n] 
import math 
start_time = time.time() 
print(lattice_paths_of_n(20)) 
print(time.time()-start_time) 

Хотя это довольно неэффективно, я надеюсь, вы сочтете это полезным.