Ошибка индекса для случайной библиотеки в python. Работает для небольших входов, но не работает для больших входов

Question

Я должен создать самодостаточный путь решетки, который движется в 4 направлениях (север, восток, запад, юг). Я написал для этого функцию:

n=int(input())
edges = [[1, 0], [0, 1], [-1, 0], [0, -1]]
make_step = lambda point, edge: [x+y for x,y in zip(point, edge)]
path=[[0,0]]
x_coo=[0]
y_coo=[0]
for i in range(n):
    next_points = [make_step(path[-1], edge) for edge in edges]

    allowed_points = [point for point in next_points if point not in path]

    p=rand.choice(allowed_points)

    path.append(p)

    x_coo.append(p[0])

    y_coo.append(p[1])

plt.plot(x_coo,y_coo)

Работает хорошо до 60, но выдает ошибку, когда ввод больше 0.

IndexError                                Traceback (most recent call last)
<ipython-input-15-a4a59bcce6b0> in <module>
     10     allowed_points = [point for point in next_points if point not in path]
     11 
---> 12     p=rand.choice(allowed_points)
     13 
     14     path.append(p)

~\anaconda3\lib\random.py in choice(self, seq)
    259             i = self._randbelow(len(seq))
    260         except ValueError:
--> 261             raise IndexError('Cannot choose from an empty sequence') from None
    262         return seq[i]
    263 

IndexError: Cannot choose from an empty sequence

Кто-то, пожалуйста, помогите мне разрешить эта ошибка.

Answer 1

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

for i in range(n):
    next_points = [make_step(path[-1], edge) for edge in edges]
    allowed_points = [point for point in next_points if point not in path]
    if allowed_points!=[]:
        p=rand.choice(allowed_points)
        path.append(p)
        x_coo.append(p[0])
        y_coo.append(p[1])
    else:
        print ('dead end, stops when n=',i)
        break

В одном трейле, когда я установил input = 100 , он возвращает следующий путь и останавливается, когда n = 70:

Как вы можете видеть, указатель застрял в (4,12); любой шаг пересекается с одним из предыдущих путей [(3,12), (5,12), (4,11), (4,13)].